일지 & 개발

문제 요약 알고리즘 분류: 백트레킹, DFS, 위상정렬 난이도: Medium 문제내용: 강의 수 numCourse와 prerequisites 배열을 준다. prerequisites[i]는 [a, b]가 들어 있다. b 수강 하기 위해서는 a수강을 먼저 들어아한다. 수강 들을수 있는지 참/거짓으로 반환 하여라. 사이트 주소: https://leetcode.com/problems/course-schedule/ 문제풀이 이번 문제는 깊이우선탐색, 백트레킹, 위상정렬을 활용한 문제이다. 두개에 관련 설명은 아래 글에서 확인하면 된다. 깊이우선탐색(DFS): https://jih3508.tistory.com/94 백트레킹: https://jih3508.tistory.com/84 위상 정렬: https://namu..

문제 요약 알고리즘 분류: bfs, 구현, 시물레이션 난이도:Silver1 문제내용: 가로, 세로 크기가 n, m인 지도가 있다 2는 시작점 1은 갈수 있는 길, 0은 갈수 없는 곳 시작점 부터 각 지점 목적지를 출력해라 그리고 목적지 도달 하지 못하는 곳은 -1로 출력해라 사이트: https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제풀이 이번 문제는 BFS 탐색 문제이다. BFS 탐색 알고리즘에 관..

문제 요약 알고리즘 분류: dfs 난이도: Silver2 문제내용: 아래와 같이 2가지 연산이 가능하다. ×2 1을 오른쪽추가한다. A, 에서 B까지 최소 몇번 연산가능한지 구해라. 사이트: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제풀이 이번 문제는 dfs 응용하는 문제이다. dfs 대한설명은 여기에서 확인 해보면 된다. 문제 접근 방법 bfs를 응용하는 것인데 위 그림 처럼 queue에 현재 값을 연산후 B보다 작거나 같을때 queue에 저장하면 하고 현재 값 연산 횟수에 +1을 더하면 끝이다. from collections import deque A, B..

문제 요약 알고리즘 분류:DFS, 트리 난이도: Gold2 문제내용: 길이가 가장 긴 트리의 지름을 구해라 노드개수 V, 그 다음 줄은 맨 앞에 노드 번호, 그 뒤는 -1 까지 노드와 연결된 노드 길이 여러개 준다. 사이트: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제풀이 이번에는 문제 유형은 트리와 DFS 탐색 유형인 문제이다. 트리와 DFS관한 자세한 설명은 아래의 사이트에서 확인 해보면된다. 트리: https://..

이론 이번에 볼 자료구조는 그래프이다. 트리는 노드간에 부모-자식, 형제 이런 개념이 있지만 그래프는 노드하나 이상이 사이클을 가진 개념이다. 사이클이란 간선 한번만 이동 가능할때 노드가 자기 자신 노드로 돌아 올수 있다는 개념이다. 그래프에 대한 자세한 내용알고 싶으면 아래 사이트에서 확인 해보면된다. https://namu.wiki/w/%EA%B7%B8%EB%9E%98%ED%94%84(%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99) 그래프(이산수학) - 나무위키 그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프 이론의 초기에는 그래프가 한 종류였지만, 현대에 들어 전산학, 전자공학 등의 발전으로 인해 여러 변형이 생겼다. 무향 그래프의 꼭 namu.wiki

문제 요약 알고리즘 분류: 플로이드 워셜 난이도: Gold4 문제내용: 각 노드간의 최단 거리를 구해라 시작과 도착점은 같은 거리는 없다. 시작점에서 도착점까지 갈수 없으면 0으로 표시한다. 사이트: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색 관련 문제이다. 모든 노드간의 최단 거리를 구하라는 문제가 나와있고 데이터가 최대 100으로 봤을때 플로이드 워셜 알고리즘으로 해결 할 수가 있다. 시간복잡..

이론 이번에 볼 자료구조는 깊이 우선 탐색(DFS)이다. 깊이 우선 탐색은 영어로 Depth First Search이고 줄어서 DFS라고 많이 부른다. 그래프 탐색 알고리즘 중 하나인데 그래프 말고도 트리에서도 적용이 된다. 반대로 넓이 우선 탐색(BFS)도 있는데 코드 테스트에서는 DFS 보다 BFS가 많이 나오지만 그래도 공부를 해야 되는 기본적인 알고리즘이다. DFS알고리즘을 알기위해서는 트리, 그래프, Stack 자료구조를 알아야 이해가 되는데 이 부분은 우선 공부한 뒤로 이 알고리즘을 공부하는 것을 추천한다. 안 그러면 이 뒤에 내용이 이해가 안 될수가 있기 때문이다. 자세한 설명은 아래의 사이트에 참조하면된다. https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9..