이누의 개발성장기

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. String Matching 특정 문자열에서 특정 문자열을 찾는 것 ex) abababcabcabcdabccbaabdabcabcdabcd 에서 abcabcd를 찾는 방법 응용 : 워드 / 염기서열 분석 Naive, DFA, KMP 방법 Navie 알고리즘 int naivematch(char T[], int n, char P[], int m, int output[]) { int i, j, k; for (i=1; i

배열의 성능분석 같은 배열이라도 값이 모여있을 수 있고 흩어져 있을 수 있다. 또 값들이 순서대로 정렬되어 있을 수 있고 그렇지 않을 수 있다. 이런 특성은 배열의 성능을 결정짓는데에 크게 기여한다. 이를 Packed vs UnPacked (빈 자리를 한 쪽으로 모으느냐? 흩어져 있을 수 있느냐?) Sorted vs UnSorted (아이템들이 정렬된 상태를 유지하느냐? 그렇지 않느냐?) 라고 말할 수 있는데, 이를 기반으로 배열을 총 네가지 분류로 나누고 성능을 분석해보겠다. Packed, UnSorted 가장 간단한 방법 아이템의 개수를 표시하는 변수가 따로 필요하다 Search : O(N) Insert : [Search, O(N)], O(1) (넣기만 하면됨) Delete : [Search, O(N..

합병정렬 int sort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] sort(b, h); sort(b+h, n-h); // Merge two halves in b to a return 0; } 정렬된 두 가지 배열을 정렬되도록 합치는 것이 Merge(합병)이다. 배열을 가장 작게 쪼갠 뒤, 이들을 계속해서 Merge하면 최종적인 배열이 정렬될 것이다. 반복문으로도 구현할 수 있지만, 조금 복잡해져서 재귀를 활용했다. copy와 merge 코드 구현부는 제외하고 서술했다. 시간복잡도 O(N*logN) 합병정렬의 증명 입력 집합 a[0],a[1],...,a[n-1] 의 정수 집합에 대해 Sorting이 완료된 집합은 b[0],b[1],..

선택 정렬 int sort(int a[], int n) { int i,j,m,t; for (i=0;i k - 1 라면 a[x] > a[k-1] 가 성립한다. 4. Prove Invariant by induction Base : 'k = 0 일 경우 invariant가 성립한다.' -> invariant(1) null condition으로 true / invariant(2) null condition으로 true Step : 'k번째 루프가 끝났을 때 invariant가 성립한다면 k+1번째 루프가 끝났을 때도 invariant가 성립한다' -> k번째 루프가 끝났을 때 'a[0] k - 1 라면 a[x] > a[k-1]'가 성립한다고 가정하자. 그 후..

- 본격적인 자료구조에 대해 배우기 전에 자료구조를 익히기 위한 사전 지식을 배워보자. - 여러 부분을 다뤄야해서 다소 광범위한 느낌이 있다. - 모든 코드는 C++이 기준이다. 변수 int a = 129; 변수는 기본적으로 위와 같이 선언한다. 변수는 a와 같은 이름과 위 코드에서는 보이지 않지만 해당 값이 저장된 메모리 상의 주소, int와 같은 자료의 타입으로 구성된다고 할 수 있다. 이 중 특히 타입은 해당 값의 '크기'와 '해석 방법'을 정의하기 때문에 중요하다. (int는 4바이트의 크기를 가지고 숫자로 해석되지만, char는 1바이트의 크기를 가지고 아스키 코드를 통해 문자로 해석된다.) 포인터 int a, x; int *p, *r; int **q; x = a + *p; // 가능 q = p..

특정 리스트를 정렬하는 방법에는 여러 가지가 있다. 그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다. 그 중 합병 정렬에 대해 알아보자. 합병 정렬은 병합 정렬이라고도 불린다. 정렬된 두 리스트의 합 정렬 먼저 알아야 할 것이 있다. 합병 정렬은 정렬된 임의의 두 리스트가 있을 때, 두 리스트를 합치면서 정렬하기 위해서는 두 리스트의 성분을 처음부터 하나씩 비교해면서 새로운 리스트에 넣어주다가 둘 중 어느 한 리스트의 성분 모두 없어지면, 나머지는 그냥 새로운 리스트의 뒤에 들어가면 된다. ex. [1,2,3,5] [4,6,7,8]이 있을 때 이를 합치면서 정렬하려 한다. 처음부터 성분을 비교하면서 넣다 보면 어느 순간 새로운 리스트에 [1,2,3,4,5]까지 ..

비트연산자를 활용하여 부분집합 만들기 n이 어떤 집합의 원소 갯수라고 하자. - 특정 부분집합에 대한 특정 원소의 포함여부는 각 원소마다 2가지 경우를 가진다. (들어간다 or 들어가지 않는다.) - 이를 원소의 갯수만큼 반복하여 생각하면, 모든 부분집합의 경우의 수를 알 수 있다. - 즉, 어떤 집합의 부분집합은 2의 n승 만큼 존재한다고 할 수 있다. 이를 활용하여 특정 집합의 부분집합들을 찾을 수 있다. - 우선 부분집합의 개수를 비트 형태로 생각해보자. 배열 arr이 6개의 원소를 가진다면, - 000000~111111의 숫자로 대변할 수 있는 부분집합들을 가질 것이다. (2의 n승개) 이를 기반으로 각 부분집합을 한줄씩 출력해주는 코드를 작성해보았다. 1 2 3 4 5 6 7 8 9 arr = ..

완전검색 (Brute force) 완전검색은 Brute force라고 불리는 만큼 매우 무식한 알고리즘 기법이다. 가능한 경우의 수를 전부 확인하고 답을 그 중에서 답을 찾아내는 것이다. 어떤 리스트에서 숫자 100을 찾을 때 해당 리스트를 전부 돌면서 숫자 100과 일치하는 값을 찾는 것이 그 예시이다. 사실 나는 이것을 알고리즘이라 불러도 되는지도 잘 모르겠다. 하지만 오류없이 답을 확실하게 찾아낼 수 있고, 가능한 경우의 수가 적을 때는 상당히 유용하게 사용된다고 한다. 자격 검정 시험 등에서도 우선 완전검색 방법으로 답을 도출해낸 다음, 성능 개선을 위해 다른 알고리즘을 도입하는 것이 바람직하다고 할 수 있겠다.

Greedy Algorithm Greedy Algorithm은 말그대로 탐욕적인 알고리즘이다. 목표를 이루기 위해 큰 그림을 바라보지 않고, 현재 가장 좋아보이는 것으로 이동해나간다. 예를 들어, 더 높은 산을 가기위한 알고리즘을 구현한다고 할때 A산은 현재 30도의 경사를 보이고, B산은 현재 40도의 경사를 보인다고 하자. B산이 현재 경사가 더 높다고 해서 더 높은 산이 되는 것은 아닐 것이다. 하지만 Greedy Algorithm은 해당 정보를 기반으로 B산을 선택하고 올라간다. 이렇듯, Greedy Algorithm은 완벽한 결과를 보장해주지는 않는다. 하지만 간혹 Greedy Algorithm이 완벽한 결과를 도출해내는 경우도 있고, 속도가 매우 빨라 다른 느린 알고리즘을 대신하여 많이 사용된..

다이나믹 프로그래밍 다이나믹 프로그래밍이란 어떤 문제를 해결하는 것에 있어, 중복적인 계산을 최대한 피하는 방법이다. (2*5) + (2*6)의 문제를 해결할 때를 생각해보자. (2*5)만 알면 (2*6)은 (2*5 + 2)로 해결할 수 있다. 따로 (2*5)를 또 계산할 필요가 없이 미리 해결한 (2*5)의 결과값을 이용한 것이다. 이것이 다이나믹 프로그램의 핵심이다. 문제가 더더욱 복잡하고 중복되는 계산이 많은 상황에서는 여러 계산과정을 생략할 수 있어 유용할 것이다. 좀 더 자세히 살펴보자. 다이내믹 프로그래밍의 조건 1. 최적 부분 구조 : 부분 문제의 최적의 답을 통해 상위문제(기존문제)의 최적의 답을 구할 수 있다. ex. 피보나치 수, fib(n) = fib(n -1) + fib(n - 2)..