Hee's Story

Index 1. Selection Sort 2. Insertion Sort 3. Bubble Sort 4. Quick Sort 5. Merge Sort 6. Heap Sort 7. Radix Sort 1. Selection Sort (선택 정렬) 데이터를 처음부터 끝가지 훑어가면서 가장 작은 값을 찾아 그 값을 바꾼다. 각 루프마다 최소의 원소를 찾는다. 최소값을 맨 왼쪽(앞)의 원소와 교환한다. 맨 왼쪽 원소를 제외하고 하나의 원소가 남을 때까지 반복한다. 출처 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC* 시간복잡도 : O(n^2) 장점 데이터 양이 적을 때 좋은 성능을 낸다. 작은 갑슬 선택하기 위해서 비교는 여러번이지..

Backtracking (백 트래킹) 모든 경우의 수를 전부 고려하는 알고리즘이다. 즉, 조합 알고리즘 문제에 대해 어떤 조건을 만족할 때 모든 가능한 해를 나열한 것이다. 일종의 트리 탐색 알고리즘으로 DFS, BFS 등의 방식을 사용한다. DFS 모든 경우의 수를 고려해야 하는 문제일 때 주로 사용한다. 하지만 트리의 깊이가 무한대가 될 때는 절대 사용하면 안된다. (무한루프에 빠짐) -> 이 때, 중복검사를 따로 해야 함 BFS 최단거리를 구할 때 주로 사용한다. Backtraking의 대표적인 예제로 N-Queen이 있다.

보호되어 있는 글입니다.

깊이 우선 탐색이란? - 루트 노드 혹은 다른 임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 깊이 우선 탐색과정 0에서 부터 시작해서 노드 번호가 작은 순서로 간다. 먼저 0 부터 시작해서 인접한 노드 중 작은 것 먼저 방문한다. 즉 1을 방문한다. 그 다음 1과 인접한 노드 중 작은 것을 방문한다. 즉 3을 방문한다. 다음과 같이 진행하면 탐색 순서는 0 -> 1 -> 3 -> 4 -> 2 -> 5 가 된다. 깊이 우선 탐색 장점 - 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 깊이 우선 탐색 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서..

동적 계획법이란? - 큰 문제를 작게 최소화해서 푸는 알고리즘이다. - 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결한다. - 시간 복잡도를 줄이기 위해 공간을 늘린다. - 즉, DP는 이전 정보를 가지고 있어서 공간을 많이 사용한다. 풀이 순서 1. 구하고자 하는 큰 문제에서 작은 부분 문제를 정의한다. 2. 가장 작은 부분 문제부터 풀어 문제에 대한 점화식을 구한다. - 가장 작은 부분 문제의 답을 저장한다. - 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다. 3. 문제를 해결한다. 주의할 점 - 초기화