재귀함수와 스택, 스택 프레임에 대한 개념 자연수 N이 주어지면 아래와 같이 출력 입력예제 3 출력예제 1 2 3 만약 코드를 이렇게 작성하면 #include #include #include using namespace std; void recur(int x) { if (x == 0) return; else { cout n; recur(n); return 0; } 결과가 3 2 1 로 출력된다. 그러면 1 2 3 으로 출력되게 하려면 어떻게 해야할까? 이렇게 두 코드의 위치를 서로 변경해주면 된다. 어떤 원리로 이렇게 되는 것일까? 그 이유는 재귀는 스택이라는 자료구조를 사용하면서 운영하기 때문이다. 그런데 위 그림은 대략 이런 원리로 돌아간다는 거지 재귀함수 스택 개념을 제대로 설명한 것은 아니다. 어..
top = -1로 시작 top = -1; void push(int x) { stack[++top] = x; } int pop() { return stack[top--]; } #include 하면 해당 함수를 사용할 수 있다. 문제 : K진수 출력 10진수 N이 입력되면 K진수로 변환하여 출력하는 프로그램 작성 (100) { s.push(n % k); n = n / k; } while(!s.empty()) { printf("%c", str[s.top()]); s.pop(); } return 0; } 문제 : 올바른 괄호 괄호가 입력되면 올바른 괄호이면 "YES", 올바르지 않으면 "NO"를 출력한다. (())()는 YES, (()()))는 NO 스택을 이용해서 문제풀이 #include #include #i..
삽입정렬 삽입정렬 이론 확실하게 짚고 넘어가야할 중요한 알고리즘이다. 삽입정렬의 시간복잡도는 최선일 경우 O(N) , 최악일 경우 O(N*N)이 된다. 앞서 살펴봤던 이중 반복문으로 모든 곳을 탐색하여 최선과 최악일 경우의 시간 복잡도가 모두 O(N*N)이였던 선택정렬과 버블정렬에 비하면 낫긴 하지만 삽입정렬 역시 비효율적인 정렬 알고리즘에 속한다. 대략적인 코드를 작성해보면 int i, j; for(i=1; i=0; j--) { if(a[j] > tmp) a[j+1] = a[j]; else break; } a[j+1] = tmp; } 이렇게 나타낼 수 있다. i가 1부터 돌고 j는 i-1에서 j=0까지 감소하는 for문을 돈다. 왼쪽의 수가 크면 오른쪽 수에 왼쪽 수를 넣고 그렇지 않은 경우(break..
선택정렬 선택정렬 이론 : 이렇게 정렬하는 알고리즘이다. for문 i 안에서 for문 j가 탐색을 하며 가장 작은 수를 찾아 현재 위치랑 교환(swap)하는 것을 반복한다. 이중 반복문이고, 끝까지 탐색을 해야 하기 때문에 O(N*N)인 시간복잡도를 가지고 있다. 비효율적인 정렬이라고 할 수 있다. O(NlogN)의 시간복잡도를 가진 sort함수를 나두고 이걸 사용할 필요가 있나 싶지만 알아두기로 하자 코드는 이런 느낌으로 작성된다. for(i= ..) { idx = i; for(j=i+1; j m; v.push_back(m); } for(i=0; i
그리디 알고리즘에 대해 그리디 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개됩니다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', 가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다. 지금 살펴볼 거스름돈 문제는 그리디 알고리즘을 대표하는 문제입니다. 그리디 알고리즘 문제 풀이 1번 - 거스름돈 문제 : 당신은 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정..
