Code in

Graph 그래프는 Vertices 정점과 이들을 연결하는 Edge 간선으로 이루어집니다. 정점 u, v를 연결하는 간선은 (u, v)로 표현됩니다. 정점은 Vertex, Node로 부를 수 있습니다. 무방향에서는 (u, v)와 (v, u)가 동일합니다. 두 정점을 가장 적은 수의 Edge로 연결하는 경로를 Shortest Path라고 합니다. 어떤 정점에서 시작하여 다시 자신에게 돌아오는 경로가 있을 경우 이를 Cycle이라고 합니다. 각 간선 Edge마다 가중치 Weight 가 존재하는 경우에는 가중 그래프 Weighted Graph라고 부릅니다. 가중 그래프에서는 가중치의 합이 가장 적은 경로를 Shortest Path라고 합니다. 방향이 있는 그래프는 방향 그래프 Directed Graph라고 합..

이진 탐색 Binary Search 이진 탐색은 한번 비교를 할 때마다 탐색 범위가 절반으로 줄어든다. 정렬된 배열을 전제로 탐색한다. 1 3 5 7 9 11 13 위와 같은 정렬된 배열에서 Binary Search 이진 탐색을 적용하여 9 를 탐색하는 경우를 생각할 수 있다. 정렬된 배열의 중앙 요소를 선택한다. 선택된 값과 찾고자 하는 값을 비교하여 왼쪽 혹은 오른쪽 중 어느 방향으로 탐색을 진행할지를 정한다. 위의 과정을 반복한다. 남은 탐색 값은 9가 남고, 찾고자 하는 값과 일치하므로 탐색을 끝마친다. 이진 탐색 성..

해시 함수는 어떤 길이의 데이터를 입력해도 정해진 길이의 결괏값을 준다. 데이터를 저장하는 방식으로 볼 때, 해시 함수에는 다양한 방식이 있다. Direct-address tables Direct-address tables는 크기가 U인 테이블 T를 생성하고 key K를 slot K에 저장하는 방식이다. 이때 중복되는 key는 없다고 가정한다. 전체 크기가 U인 곳에서 actual key K가 존재한다고 생각한다. 해당되는 데이터를 table에 저장하고 필요한 key값과 그에 해당하는 data를 확인하는 자료구조이다. 해당 방식은 수행 시간이 매우 짧다는 장점이 있다. key값을 알고 있으면 table에서 바로 data를 찾을 수 있기 때문이다. 하지만 공간 복잡도 측면에서는 실제 사용 공간이 적어 공간..

깊이 우선 탐색 DFS, 너비 우선 탐색 BFS에 앞서서 사용되는 자료구조인 그래프에 대해서 알아보겠습니다. 그래프 노드 Node와 노드를 연결하는 간선 Edge을 하나로 모아놓은 비선형 자료구조 연결된 객체 간의 관계를 표현하는 자료구조 정점 vertex와 간선 edge로 이루어진 자료구조 G = (V, E) 흔히 이야기하는 트리 구조는 조건들이 추가된 그래프의 일종입니다. 그림과 같이 표시된 방향이 없는 무방향 그래프도 있지만, 방향이 표기된 방향 그래프도 존재합니다. 그래프 탐색 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 깊이 우선 탐색 DFS와 너비 우선 탐색 BFS도 그래프 탐색의 한 종류입니다. 두 방식 모두 그래프 G = (V, E)의 모든 간선을 조회하..

동적 계획법 (DP - Dynamic Programming) 동적 계획법 (DP - Dynamic Programming) 은 큰 문제를 작은 문제로 나누어서 풀이하는 방식의 알고리즘입니다. Dynamic Programming이라는 이름은, 1953년, 수학자인 리처드 벨만이 큰 문제 안에 작은 문제가 중첩되어 있는 문제를 해결하면서 동적 계획법 Dynamic Programming이라는 이름을 사용했습니다. Dynamic은 벨만이 알고리즘의 시가변적Time-varing이고 다단계적인multistage 특성을 나타내기 위해 사용되었습니다. Programming은 그 당시 근무하던 회사의 소속인 공군 내에서 워드 프로세스 교육이나 군수 물자 운송 등에 사용되던 단어였기 때문에 사용되었습니다. 분할 정복과의 차..

탐욕 알고리즘 Greedy Algorithm 그리디 알고리즘은 동적 프로그래밍을 할 때 지나치게 많은 일을 하는 것을 보다 효율적으로 바꾸기 위해서 생겨난 알고리즘입니다. 따라서 동적 프로그래밍과 함께 쓰였을 때 서로 보완할 수 있습니다. Greedy Algorithm은 탐욕 알고리즘, 욕심쟁이 알고리즘으로 불립니다. 매 순간 최선의 선택을 하여 최종적으로 최선이 되도록 하는 알고리즘입니다. 매 순간 해당 순간을 위한 최선의 선택만을 하기 때문에 미래에 어떤 영향을 줄지는 생각하지 않습니다. 모든 경우에 그리디 알고리즘이 적합하진 않지만, 몇몇 케이스에서는 그리디 알고리즘으로 최종적으로 최선인 답을 보다 효율적으로 구할 수 있습니다. 요약하면, 1. 동적 계획법과 마찬가지로 최적화 문제를 푸는 데 사용되..

완전 탐색 알고리즘 - Brute Force : 모든 경우의 수를 확인하여 답을 찾아내는 알고리즘. BF는, 모든 경우의 수를 확인하기 때문에 성공하면 100% 정확한 답을 찾아낼 수 있다. 만들기가 비교적 쉽고 병렬 작업이 가능하다는 장점을 가지고 있지만, 시간적인 측면에서는 비효율적이라는 단점을 가지고 있다. 탐색해야 할 요소들이 많은 경우에는 보다 효율적인 방법을 찾아서 사용하는 것이 좋겠지만, 개수가 정해져 있거나 적은 경우에는 완전 탐색을 사용하여 보다 쉽고 정확하게 답을 구할 수 있다. 완전 탐색을 구현하기 위해서는, 1. 반복문을 사용하거나 (for, while) 2. 재귀 함수를 사용할 수 있다. (return function / 같은 함수 호출의 반복) 재귀 함수의 경우, 더 이상 함수를..

스택, 큐, 힙 정적인 메모리: 컴파일할 때 메모리를 할당 받고 시작한다. ex) 기본형 자료형 동적인 메모리: 실행하는 런 타임에 메모리를 할당 받는다. ex) 참조형 자료형, malloc, calloc 스택 Stack LIFO, Last in First out으로 후입선출의 구조이다. 백 트래킹, 인터넷 사용기록 보관 등이 스택을 사용하는 LIFO 구조를 갖고 있다. 한쪽(TOP)에서만 데이터를 넣고 꺼낼 수 있다. * 스택오버플로우: 정해진 크기의 스택에 계속해서 PUSH하다 스택의 크기를 초과하여 더이상 데이터를 추가할 수 없게 된 것으로, 흔히 스택을 사용하는 재귀함수 호출 시 많이 경험한다. 컴퓨터의 사칙 연산 계산에서 후위 표기법을 사용할 때도 스택을 활용한다. PUSH: 스택의 TOP에 데..

Sorting 정렬 알고리즘 : N개의 숫자를 입력받아서 오름차순ASC 혹은 내림차순DESC으로 정렬하여 출력하는 알고리즘이다. * 오름차순: ASC, Ascending **내림차순: DESC, Descending 간략하게는, Swap을 주로 사용하는 선택 정렬과 버블 정렬, 중간에 데이터를 삽입하여 그 뒤의 데이터들의 위치를 바꾸는 삽입 정렬과 쉘 정렬 분할 정복을 사용하는 합병 정렬과 퀵 정렬, Tim Sort, Intro Sort 버킷을 사용하는 기수 정렬과 버킷 정렬, Counting Sort 최대 힙을 사용하는 힙 정렬 등이 있다. *임의로 크게 나누었을 때이므로 세부적으로는 차이가 있다. 이 때, 입력 데이터들 중 같은 값들이 존재할 때 정렬 과정에서 이들의 위치가 바뀌지 않을 경우 안정 정렬..