알고리즘

[알고리즘] 9. 해 탐색 알고리즘

9. 해 탐색 알고리즘 종류 백트래킹 기법 분기 한정 기법 유전자 알고리즘 모의 담금질 기법 9.1 백트래킹 기법 백트래킹 기법이란? 기본적으로 DFS(깊이우선탐색)를 통해 해를 찾는 도중에 ‘막히면’ (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다 최적화 문제(최솟값, 최댓값 찾는 문제)와 결정 문제(해가 존재하는지 yes or no)를 해결 가능 여행자 문제(Traveling Salesman Problem, TSP) 를 위한 백트래킹 알고리즘 ❑Line 1~3 – 현재 tour가 완전한 해이면서 현재까지 찾은 가장 우수한 해인 bestSolution의 거리보다 짧으면 현재 tour로 bestSolution을 갱신한다. – bestSolution의 거리보다 길거나 같은 경우에는 갱신 없이..

[알고리즘] 7. NP-완전 문제

P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) X에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 X∈P입니다. NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의 집합으로, 어떤 결정 문제 X에 대해, 주어지는 입력이 참인지 거짓인지를 다항 시간에 비결정론적으로 해결하는 알고리즘이 존재하면 X∈NP입니다. NP의 또 다른 정의는 다항 시간에 결정론적으로 검증 가능한(verifiable) 문제들의 집합입니다. 자세히 살펴보자면, 어떤 결정 문제..

[알고리즘]4. 그리디 알고리즘(2)

4.4 집합 커버 문제 1. 문제 n개의 원소를 가진 집합인 U가 있고, U의 부분 집합들을 원소로 하는 집합 F가 주어질 때, F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가? 집합 커버(Set Cover) 문제는 F에서 선택하는 집합들의 수를 최소화하는 문제이다. 예시 - 신도시를 계획함에 있어서 학교를 배치하는 문제 위 그림과 같이 신도시에 10개의 마을이 만들어질 계획이다. 이 때, 아래의 2가지 조건이 만족되도록 학교의 위치를 선정하여야 한다고 가정한다 학교는 마을에 위치한다. 등교 거리는 걸어서 15분 이내여야 한다. 어느 마을에 학교를 신설해야 학교의 수가 최소로 될 것인가? 2번 마을에 학교를 만들면 마을 1, 2, 3, 4, 8이 커버된다. 또한, 6번 마..

[알고리즘] 4. 그리디 알고리즘 (1)

그리디 알고리즘 탐욕법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법입니다. 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 정당성 분석이 중요합니다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 일반적으로 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다. 하지만 코테에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀도록 출제됩니다. 4.1 동전 거스름돈 CoinChange 알고리즘은 항상 최적의 답을 주지 못함 • 따라서 실제로는 거스름돈에 대한 그리디 알고리즘이 적용되도록 동전이 발행됩니다. 실제 문제) 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원,..

[알고리즘] 3. 최근접 점의 쌍 찾기 알고리즘 (3)

▶ 최근점 점의 쌍을 찾는 문제? 최근접 점의 쌍(Closest Pair)을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제입니다. 바로 그 문제를 해결하기 위한 방법은 효율적인 분할 정복을 이용하는 것입니다. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 쌍을 찾고, 2개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾습니다. 여기서 주의할 점! 취합할 때 중간 영역을 고려해야합니다. 이게 무슨 말이냐면, 분할된 왼쪽 점 중에 하나, 오른쪽 점 중에 하나가 최근접점 쌍이 될 수 있습니다. 그래서 중간 영역도 왼쪽 부분과 오른쪽 부분의 최단 거리인 10과 15중에 더 짧은 거리 10이내에 있는 각각 왼쪽과 오른쪽 점들만 거리 ..

[알고리즘] 3. 선택 문제 알고리즘 (2)

▶ 선택문제(Selection)란? ※ 선택 정렬(Selection Sort)과는 다른 알고리즘입니다. 선택(Selection) 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제입니다. 이 문제를 해결하기 위한 단순한 방법은 다음과 같습니다. 1) 최소 숫자를 k번 찾는다. → 숫자 n개가 들어있는 배열 중에서 최소 숫자를 찾고, 찾을 때마다 입력에서 그 숫자를 제거합니다. 시간복잡도는 O(kn), k번째 숫자를 찾을 때까지 반복하는 과정마다 항상 n, n-1, n-2....(최소 숫자는 제거되므로) 개의 숫자들을 탐색하기 때문입니다. 2) 숫자들을 정렬한 후, k번째 숫자를 찾는다. → 시간복잡도는 O(nlogn), 즉 정렬하는 과정에서 걸리는 시간에 따라 다를 것입니다. (k번째 숫자를 찾..

[알고리즘] 3. 분할 정복 알고리즘 (1)

1. 분할 정복 알고리즘 분할정복알고리즘이란? 분할과 정복이라는 이름에 걸맞게, 해결하려고 하는 문제를 작은 문제로 분할하여 큰 문제를 정복하는 알고리즘이다. 분할정복의 3단계 1. Divide -> 기존 문제를 작은 부분 문제들로 나눈다. 2. Conquer -> 각 부분 문제를 해결(정복) 3. Combine -> 부분문제들의 솔루션을 통해 기존 문제를 해결 이 때 2. Conquer 과정은 다시 Divide, Conquer, Combine의 과정을 거쳐 풀기도 한다. -> 재귀적 Base Case vs Recursive Case Divide 단계에서 기존 문제를 작은 부분으로 나눌 때 무조건 나누는 것이 아니라, Base Case인지, Recursive Case 인지를 판단해야 한다. - Base ..

기하 알고리즘

기하학 좌표를 사용하여 점, 선, 다각형, 다면체 등의 기본 요소를 어떻게 표현할 것인가 결정 기하학의 문제 - 간단한 문제: 선분 교차, 직각 삼각형, 내접 다각형 - 복잡한 문제: 순환 외판원, CAD, 최소 신장 나무 1. 선분 교차 - 두 선분이 주어졌을 때, 이 둘이 서로 교차하는지 아닌지 검사하는 알고리즘 - 두 선분이 교차한다는 것은 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다. 두 선분의 교차 여부를 검사하는 방법 - 각 선분의 무한 연장선을 긋고 두 연장선의 일차방정식을 구한 후 교점을 계싼한다. 2. 단순 폐쇄경로 찾기 임의의 기준점으로부터 다른 각각의 점까지의 각도를 구한 후, 올림차순으로 정렬한 다음 기준점부터 정렬한 순서대로 이으면 그것이 단순 폐쇄 경로가 된다. 기준점..