극꼼이 이야기 (GG_Tales)

1. 백트래킹이란? 2. 백트래킹 예시(N-Queen) 1. 백트래킹이란? : 제약된 조건을 가진 문제에서 답을 찾기 위한 방법. - DFS 방식으로 확인(https://geukggom.tistory.com/66). - 모든 경우의 수를 상태 공간 트리를 통해 표현해 탐색. Promising : 해당 루트가 제약된 조건에 맞는지 확인 Pruning : 가지치기. Promising단계에서 조건에 맞지 않으면 바로 다른 루트로 가서 탐색 시간 절약. * 상태 공간 트리(State Space Tree) : 문제 해결 과정의 중간 상태를 Node로 나타낸 트리 2. 백트래킹 예시 백트래킹의 대표적인 문제 예시로는 N-Queen 문제가 있습니다. * N-Queen : 크기가 N * N인 체스판 위에 퀸 N개를 서..

1. 퀵정렬이란? 데이터들 중 한 숫자를 기준점(pivot)으로 정하고, 기준점보다 작은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 분류하여 정렬합니다. 재귀용법을 이용해 작은 단위까지 쪼개어 정렬한 후 합치는 방식입니다. 2. 퀵정렬의 구현 병합정렬을 배우고 나니 퀵정렬은 조금 더 쉬웠습니다. public List quickSort(List list) { if (list.Count = list[i]) left_List.Add(list[i]); else right_List.Add(list[i]); } left_List = quickSort(left_List); right_List = quickSort(right_List); left_List.Add(pivot); left_List.AddRange(righ..

1. 삽입 정렬이란? : 두번째 인덱스부터 시작해서, 앞으로 이동하면서 다른 인덱스들과 값을 비교해서 자신의 위치에 맞는 곳에 삽입하는 방식의 정렬 알고리즘. 2. 삽입 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다. * 버블정렬, 선택정렬, 삽입 정렬 모두 동일한 시간복잡도를 가집니다.