0. 탐욕 알고리즘이란?탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.각 선택 시점에서 이루어지는 결정은 그 순간에는 최적이지만, 그 선택이 모인 최종적인 해답이 최적이라는 보장은 없다.1. 배낭 짐싸기(Knapsack)배낭에 담을 수 있는 물건의 총 무게(W)가 정해져 있다.이 때, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건을 담는 경우, 그리디 알고리즘을 생각해볼 수 있다.1-1. 0-1 Knapsak배낭에 물건을 통째로 담아야 하는 문제 ➡ 물건을 쪼갤 수 없는 경우이 방식은 그리디 알고리즘을 적용하기 어렵다. 아래에는 총무게가 30kg인 배낭에 0-1Knaps..
0. Next Permutation현 순열에서 사전 순으로 다음 순열을 생성하는 것 이를 이용하여 순열과 조합을 표현할 수 있다.재귀를 통해 구현한 순열, 조합보다 빠르다는 장점을 가지고 있다.하지만 nPn만 가능하다는 단점을 가지고 있다.1. 알고리즘배열을 오름차순으로 정렬한다.아래 과정을 반복하여 사전 순으로 다음을 큰 순열을 생성한다.(가장 큰 순열을 만들 때까지 반복)뒤에서부터 탐색하며 교환 위치(pivot) 찾기 → 최초로 pivot 뒤에서부터 탐색하며 교환 위치(pivot)와 교환할 위치(successor) 찾기 → pivot 두 위치(pivot, successor) 값 교환교환 위치(pivot)의 뒷 부분을 오름차순으로 정렬NextPermutation 사용 전에 숫자배열을 오름차순으로 정렬한..
0. 순열, 조합, 부분집합알고리즘 문제를 풀다 보면, 특정 원소에서 몇개를 뽑아 써야 하는 경우가 종종 있다.이 때, 알고 있어야 하는 순열과 조합 그리고 부분집합을 구현하는 방식을 작성했다.1. 순열서로 다른 n개 중 r개를 뽑아서 한 줄로 나열하는 것 2. 조합서로 다른 n개 중 r개를 순서 없이 골라내는 것 3. 부분집합집합에 포함된 원소들을 선택하는 것 → n개의 원소에는 공집합을 포함하여 2^n개이다.
0. 비선형 자료구조 완전탐색비선형 자료구조는 1:1이 아니기 때문에 일반적인 방식으론 탐색하기 어렵다.따라서 비선형 자료구조를 탐색하기 위한 방식인 BFS와 DFS를 알아보도록 하자.코드 구현은 간단하게 트리 형태를 2중 리스트를 통해 구현할 예정이다. 해당 알고리즘은 방문 여부를 체크하면 그래프, 2차원 배열 등에서도 사용된다.1. 너비 우선 탐색(Breadth First Search, BFS)루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용한다.2. 깊이 우선 탐색(Depth First..
