algorithm

포인터 한 학기 동안 안썼더니 또 까먹어버렸다... 자료구조에 관한 과목 수강하다가, 기초 지식인 포인터를 확실히 알아야겠다 싶어서 정리한다! - 포인터/ 포인터를 가리키는 포인터 #define _CRT_SECURE_NO_WARNINGS #include int main(void) { double num = 3.14; double* ptr = # double** dptr = &ptr; printf("%p %p %p\n", ptr, *dptr, dptr); //ptr ptr &ptr (ptr=&num) printf("%f %f %f %f\n", num, *ptr, **dptr, *(*dptr)); //3.14 3.14 3.14 3.14 return 0; } double* ptr = &num doubl..

- 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..

정렬 알고리즘의 종류는 다음과 같다. - Simple, slow Bubble sort Insertion sort Selection sort - Fast Quick sort Merge sort Heap sort - O(N) Radix sort 오늘은 Simple하고 slow한 특성을 갖는 selection sort와 bubble sort, Insertion sort에 대해 다뤄본다. 1. Selection sort - 가장 큰수와 자리를 바꿔가면서 정렬하는 방법이다. SelectionSort(A[],n)//배열 A[1...n]을 정렬한다. { for last

멱집합이란? - 집합의 모든 부분집합으로 이루어진 집합을 말한다. - 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를 포함하는가..

queens problem이란? - 체스판에서 대각선, 상하좌우에 말이 없도록 겹치지 않게 놓는 문제를 말한다. - 문제를 해결하기 위해서 '상태공간트리'를 활용해보자. 상태공간트리란? - 위와 같이 해를 찾기 위해 정답을 향해 나아가는 트리를 말한다. - 즉, 해가 존재한다면 그것은 반드시 이 트리의 어느 한 노드에 해당한다. - 따라서 이 트리를 체계적으로 탐색한다면 해를 구할 수 있다!- 하지만 상태공간트리의 모든 노드를 탐색할 필요는 없다. - 다음과 같이 깊이 우선으로 탐색하여 해를 찾는 알고리즘도 있다.- 이번 문제를 해결 할 때엔 "그 노드가 이미 infeasible한지, 즉 non-promising (꽝)인지"를 확인하면 된다. 코드를 구성해보자. 1. 변수 정하기 - 매개변수는 내가 현재..

Blob에 대한 이해를 해보자. - 각 픽셀은 background pixel이거나, image pixel이다. - 서로 연결된 image pixel을 blob이라 한다. (이때 상하좌우, 대각방향으로 연결된 것을 모두 셈한다.) 만들 함수의 입,출력을 정하자. - 입력: N*N 크기의 2차원 그리드와 하나의 좌표 (x,y) - 출력: 픽셀 (x,y)가 포함된 blob의 크기. (이때, (x,y)가 어떤 blob에도 포함되지 않는 경우는 0을 반환한다.) recursion thinking 하면서 코드 대략 정하기 현재 픽셀이 이 속한 blob의 크기를 카운트하려면 현재 픽셀이 image colour이 아니라면 0을 반환한다 현재 픽셀이 image colour라면 먼저 현재 픽셀을 카운트한다 (count=1..

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로 다시 갈 수 있기 때문에, 무한루..

순환적 알고리즘을 설계하기 위해선 2가지가 필요하다. 1. 적어도 하나의 base case(종료되는 case)가 있어야 한다. 2. 모든 case는 결국 base case로 수렴한다. * 추가로, 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔야한다! ->이번 포스팅은 명시적 매개변수로 표현하는 법에 대한 것이다. "순차 탐색"을 통해 두 매개변수의 차이점과 recursion의 응용을 알아보자. 암시적 매개변수? data[0]에서 data[n-1] 사이에서 target을 검색하는 코드이다. #define _CRT_SECURE_NO_WARNINGS #include int main(void) { int data[6] = { 1,2,3,4,5,6 }; printf("%d", sea..