hyunjin

깊이 우선 탐색 (Depth - First Search) 개념 DFS(깊이 우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 현재 정점에서 다음 분기로 넘어가기 전에 해당 분기를 완변하기 탐색 노드를 깊게 탐색 DFS 장점 1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간 수요 비교적 적음 2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음 3. 구현이 BFS보다 간단 DFS 단점 1. 단순 검색 속도는 BFS 보다 느림 2. 사전에 임의의 깊이를 지정 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로 탐색하도록 하는 것이 좋음 3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로 , 구한 해가 최단 경로가 된다는 보장이 없음. (목표에 이르는 경로가 다수인 ..

너비 우선 탐색 (Breadth - First Search) 개념 BFS(너비우선탐색) : 현재 정점에서 연결된 가까운 점들 부터 탐색 가까운 정점 먼저 방문 후 멀리 떨어져 있는 정점 나중에 방문 노드를 넓게(wide) 탐색 주로 두 노드 사이 최단 경로 혹은 임의의 경로 찾고 싶을 때 사용 응용하면 미로찾기 같은 알고리즘도 구현 가능 BFS 장점 1. 노드 수 적고 깊이 얕은 경우 빠름 2. 단순 검색 속도가 DFS 보다 빠름 3. 너비 우선 탐색하기 때문에 답이 되는 경로가 여러 개인 경우라도 최단 경로임을 보장 4. 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어져도 반드시 최단 경로 찾을 수 있음 BFS 단점 1. 재귀 호출의 DFS 와 달리 큐에 다음에 탐색할 정점들을 저장해야해 저장 공간..

유클리드 호제법이란? 두 수의 최대 공약수를 구하는 알고리즘의 하나. 2개 자연수 a, b ( a > b )에 대해 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 또 다시 b , r 에 대해 b를 r로 나눈 나머지 r' 을 가지고 위의 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수. ( a , b ) = ( b , r (=a%b) ) = ( r , r' ) ( 1071 , 1029 ) = ( 1029 , 42 ) = ( 42 , 21 ) = ( 21 , 0 ) = 21 21은 1071과 1029의 최대 공약수 GCD 관련 법칙 GCD( u , v ) = GCD( u - v, v ) if u < v GCD( u, v ) = GCD(..

데이터 정렬 이유 : 탐색을 위해서 (정렬이 탐색보다 시간이 덜 걸린다 했나?..) 1. 삽입 정렬(Insertion Sort) 두 번째 원소부터 맨 마지막 원소까지 각 원소가 왼쪽에 있는 모든 원소 보다 크거나 같을 때 까지 왼쪽으로 이동 현재 위치보다 아래쪽 순회하며 알맞은 위치에 넣는 정렬 //insertion sort #include using namespace std; template void insertSort( Vector* v, const int l, const int r){ for(int i = l+1 ; i left && v[j] < v[j-1] ; j--){ swap(v[j-1],v[j]); } } } 이미 정렬되어 있는 자료 구조에선..

1. Dynamic Programming(동적 계획법) 이란? 큰 문제를 작은 문제로 나누어 푸는 문제 1.1 Divide&Conquer(분할정복) 과 다른 점은? 거의 비슷하지만 결정적 차이가 있다. 작은 문제가 중복이 일어나나는 아닌지 분할 정복 큰 문제를 해결하기 어려워 단순히 작은 문제로 나누어 푸는 방법 작은 문제에서 반복이 일어나는 부분이 없다 DP 작은 부분 문제들이 반복되는 것(답이 바뀌지 않는다.)을 이용해 풀어나는 것 1.2 Dynamic Programming 방법 모든 작은 문제들은 한 번만 풀어야함. 정답을 구한 작은 문제들을 어딘가에 메모해놓고 다시 그보다 큰 문제 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결과값 이용 1.3 Dynamic Programm..