기록기록 우는 갈매기

n-Queens 문제란, nxn의 체스판에 n개의 퀸을 서로 충돌하지 않게 놓는 방법을 구하는 문제이다. 즉 서로 상대방을 위협하지 않도록 같은 행이나 같은 열, 또는 같은 대각선 상에 위치하지 않아야한다. 모든 경우를 따져가며 방법을 찾기에는 n이 커질수록 매우 다양한 경우를 따져야하므로 우리는 n-Queens문제에 backtracking 알고리즘을 적용하여 상태공간트리를 만들고, 유망한 노드들의 자식만 검사함으로써 검사해야 할 경우를 줄일 수 있다. n-Queens문제에 backtracking 알고리즘을 어떻게 적용하여 문제를 해결할 수 있는지 알아보자. 이전 글에서도 설명했다시피, backtracking 문제를 풀기위해 결정되어야 할 사항은 다음과 같다. ① 상태공간트리의 구조를 결정 ② 유망한지 ..

플로이드 알고리즘이란? 한 도시에서 다른 도시로 가는 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 shortest path 문제들 중 하나이다. 플로이드 알고리즘은 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단 거리를 구한다. 플로이드 알고리즘이 shortest path 문제들 중 한 유형이므로, 플로이드 알고리즘을 살펴보기 전에 shortest path의 특징을 먼저 알아볼 필요가 있다. ① W : 그래프의 인접행렬 W[i][j] = 이음선의 가중치 (vi에서 vj로의 이음선이 있는 경우) = ∞ (vi에서 vj로의 이음선이 없는 경우) = 0 ( i = j인 경우 ) ② D(k) : 각 정점들 사이의 최단거리 (floyd 알고리즘에서 고안) k : 중간에 거쳐갈 수 있는 정점..

퀵 정렬 알고리즘이란? 선정된 pivot값을 기준으로 배열을 나누어가면서 재귀적으로 정렬하는 알고리즘 알고리즘 설계 전략 pivot을 선정한다. pivot 보다 작은 값은 왼쪽, 더 큰 값은 오른쪽에 배치한다. 양쪽 배열에 대해 다시 같은 과정을 반복함으로써 최종적으로 배열을 정렬한다. 알고리즘 수도코드 void quicksort(index low, index high) { index pivotpoint; if(high > low) { partition(low, high, pivotpoint); //배열을 pivot 값을 기준으로 반으로 나눈다. quicksort(low, pivotpoint-1); // 왼쪽 배열에 대해 재귀적으로 정렬 quicksort(pivotpoint+1,high); // 오른쪽 ..

합병 정렬 알고리즘이란? 크기가 n인 배열을 원소가 하나 밖에 남지 않을 때까지 계속 반으로 쪼갠 후 다시 크기 순으로 정렬 하면서 원래 크기의 배열로 합치는 정렬 알고리즘 알고리즘 설계 전략 배열 원소가 하나 남을 때 까지 배열을 재귀적으로 쪼갠다. (Divide) 쪼개진 배열들을 정렬하면서 다시 합친다. (Conquer) 알고리즘 수도코드 void mergesort(int n, keytype S[]) { if (n > 1) { const int h = ⌊n/2⌋, m= n - h; keytype U[1..h], v[1..m]; //S를 반으로 쪼개 왼쪽은 U에 오른쪽은 V에 저장 copy S[1] through S[h] to U[1] through U[h]; copy S[h+1] through S[n..

이진탐색 알고리즘이란? 크기가 n인 정렬된 배열 s에 x가 있는지 결정하는 재귀 알고리즘 알고리즘 설계 전략 배열의 중간에 위치하고 있는 값이 x와 같은 경우 성공을 리턴, 그렇지 않으면 분할(Divide) 분할(Divide) : 배열을 반으로 나누고, x가 배열의 중간에 있는 값보다 작으면 왼쪽 배열을 선택(오른쪽 배열은 버림), 크면 오른쪽 배열을 선택(왼쪽 배열은 버림). 정복(Conquer) : 선택한 배열을 갖고 다시 x를 찾는다. 알고리즘 수도 코드 index location (index low, index high) { index mid; if(low > high) return 0; else { mid = ⌊(low+high) / 2⌋; //배열 가운데 값을 구함 if (x == s[mid]..