개발/알고리즘8 백트래킹(Backtracking) 알고리즘 1.백트래킹이란? 해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다. 다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다. 쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다. 경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다. Backtracking(되추적) 해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법 2. DFS 깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로, 백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구.. 2024. 3. 24. c++ 하노이의 탑, 재귀함수, 백준 11729 1. 하노이의 탑 재귀함수 문제로 가장 유명하면서도, 재귀함수에 대한 이해를 위해 아주 기초적인 문제이다. 하노이의 탑은 1883년 프랑스 수학자 에두아르 뤼카가 제시한 문제로 그림과 같이, 주어진 크기가 다른 N개의 원판과 3개의 막대(A,B,C)에 대하여 A의 모든 원판을 C로 옮기는 것인데 조건이 있다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 문제는 보통 이같은 조건을 지키며 A에서 C로 모든 원판을 옮기는 최소 실행수 또는 그 순서를 요구한다. 해결에 들어가기 전에 하노이의 탑 (Tower of Hanoi) - 플래시게임 | 와플래시 게임 아카이브 (tistory.com) 하노이의 탑 (Tower of Hanoi) 하노.. 2024. 3. 22. C++) 백준 10816 숫자 카드 2 입력받은 N개의 수 중에서 또 다른 입력받은 M개의 수가 각각 몇개 존재하는지 찾는 문제이다. 입력 개수와 찾는 수 50만 개에 대해 선형탐색을 사용하면 시간초과가 난다. C++에서 Map은 O(log n)의 레드블랙트리로 구현되어있으므로, 이를 이용하면 시간 내로 문제를 해결 할 수 있다. 물론 다른 방법, 이분탐색을 사용할 수 있지만 여기선 Map을 이용한 방법을 다루겠다. 실제 사용함으로 STL 자료구조에 더 친숙해지기 위함이다. map 로 key는 각 수(중복X), value값으론 그 개수를 기록한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,inp.. 2024. 3. 13. cpp) 삽입 정렬, insertion sort - 삽입정렬 배열의 각 요소를, 앞에서부터 하나씩 자신의 자리를 찾아 삽입 - 절차(오름차 기준) i) 배열의 1번 요소를 0번째 원소와 비교. 더 작다면 0번째 요소를 뒤로 옮기고, 그 앞에 1번 요소를 삽입 ii) 배열의 2번 요소를, 1번부터 0번 원소를 비교해 자리 설정 iii) 배열의 n번 요소를, n-1번부터 0번 원소와 비교해 자리 설정 - 시간복잡도 최악의 경우 = 모든 원소가 역순으로 정렬되어 있는 경우 외부 루프를 N-1번 도는 동안 비교연산은 1, 2, ... , (N-1)번 수행된다. T(n) = 1+2+...+(N-1) = (N-1)*N/2 O(n) = n^2 - 특징 정렬에 사용하는 외부 메모리 X 이를 In-place sort라고 한다. #include using namespa.. 2024. 3. 1. 이전 1 2 다음
