알고리즘8 백트래킹(Backtracking) 알고리즘 1.백트래킹이란? 해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다. 다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다. 쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다. 경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다. Backtracking(되추적) 해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법 2. DFS 깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로, 백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구.. 2024. 3. 24. 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) 버블정렬, Bubble Sort - 버블정렬 배열의 앞에서부터, 인접한 두 요소끼리 비교하여 자리를 교체하는 방식 이를 반복하다보면 배열의 마지막 자리에 가장 큰 요소가 위치하며 정렬되는데, 이것이 거품이 올라오는 듯 하다해서 '버블' 정렬 - 절차(오름차 기준) 길이 n의 배열의 0번부터 n-1번까지, 인접 요소끼리 비교, 자리를 적절히 교체 -> 가장 큰 요소가 마지막에 위치 0번부터 n-2번까지 인접 요소 비교, 교체 0번부터 n-3...반복 배열의 요소가 하나(0번)만 남을때 까지 수행한다. - 시간복잡도 최악,최선, 평균 모두 사이클 당 비교 횟수가 n-1번,n-2번... T(n) = (n-1)+(n-2)...2+1 = (n-1)*n/2 O(n) = n^2 - 특징 정렬에 사용하는 외부 메모리 X 이를 In-place sort.. 2024. 3. 2. 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 다음
