알고리즘

- Simple, slow Bubble sort Insertion sort Selection sort - Fast Quick sort Merge sort Heap sort - O(N) Radix sort 정렬 중 이번엔 Merge sort에 대해 다뤄본다. 3단계를 거쳐 정렬이 이루어진다. 1) 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다. ex) 최대값을 구할 때, 리스트를 반으로 나누어 각각의 최대값을 구하여, 전체리스트의 최대값을 구하는 것과 비슷하다. 2) 정복: 각각의 작은 문제를 순환적으로 해결한다. 3) 합병: 작은 문제의 해를 합하여 (merge) 원래 문제에 대한 해를 구한다. 늘은 Simple하고 slow한 특성을 갖는 selection sort와 bubbl me..

멱집합이란? - 집합의 모든 부분집합으로 이루어진 집합을 말한다. - n개의 원소를 가진 집합이 멱집합을 이루는 경우의 수는 2^n이다. (각각의 원소를 포함하는가/ 안하는가) - 멱집합을 만드는 예시) {a,b,c,d,e,f}의 모든 부분집합을 나열하려면 - 1) a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열한다. 2) {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. - >a를 포함하는가? 포함하지 않는가? 2가지 {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면- 1) {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고 2) {c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열한다. ->b를 포함하는가..

recursion을 응용하여 "미로찾기" class와 코드를 짜보자. 현재 위치에서 출구까지의 경로가 있기 위한 IDEA 1. 현재 위치가 출구여야 한다. 또는 2. 이웃한 셀들 중 하나에서 현재위치를 지나지 않고 출구까지 간다. 1. Decision Problem 답이 yes or no인 문제로 표현해보자. bool findPath(x, y) { if (x, y) is the exit return true; else for each neighbouring cell(X, Y) of(x, y) do if (X, Y) is on the pathway if findPath(X, Y) return true; return false; } -> 이 코드는 X,Y에서 인접한 x,y로 다시 갈 수 있기 때문에, 무한루..

resursion은 흔히 순환, 재귀로 불린다. - 무한루프에 빠지지 않으려면? 1. Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재 -> 실제로 무한루프에 빠진 코드는 범위를 안 정해서 그런 경우가 많았다 2. Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 함 ->recursion은 범위의 기준이 되는 곳으로 가서 코드가 마무리되기 때문 - recursion의 예제를 알아보자. (1) 1~n까지의 합 #define _CRT_SECURE_NO_WANRNINGS #include int main(void) { printf("%d",func(4)); } int func(int n) { if (n == 0) return 0; else..