백준 c++ 2447번 별찍기 - 10 문제 : 풀이 : 첫 번째 접근 : 모든 공백을 통해 규칙 살펴보기 ( X ) 이렇게 모든 공백을 가정해보면 규칙이 눈에 들어오지 않는다. 생각을 해야한다. 일반화된 규칙을 찾아 재귀함수를 이용해 별을 찍을 수 있지 않을까 두 번째 접근 : 재귀함수를 이용해 분할해서 생각하기 (i, j, n)을 재귀함수가 받아 처리한다고 생각해보자 재귀함수를 이용해서 9 x 9 (n=9)일 때 i,j 좌표가 중앙일 때 공백을 출력한다. 그 다음 3 x 3 (n=3)일 때 i,j 좌표가 중앙일 때 공백을 출력한다. n이 1이 되면 중단한다. 이렇게 n을 3으로 나누며 실행하는 재귀함수를 통해 원하는 별찍기 결과를 얻을 수 있다. 그런데 규칙은 어떻게 작성해야할까? 9x9 일 때(n=..
백준 c++ 17478번 문제 : 재귀함수가 뭔가요 소스코드 : #include using namespace std; int cnt = 0; void under_bar(int x) { if(x == 0) return; else { cout
재귀함수와 스택, 스택 프레임에 대한 개념 자연수 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
백준 문제풀이 4948번 문제 : 베르트랑 공준 문제 : 소스코드 : #include using namespace std; int primeNum(int n) { int size = 123456 * 2 + 1; int a[size] = {0,1}; int cnt = 0; for(int i=2; i
백준 문제풀이 1978번 문제 : 소수 찾기 문제 : 소스코드 : #include using namespace std; int primeNum(int num) { int sum = 0; for(int i=1; i> n; for(int i=0; i> m; k = primeNum(m); count += k; } cout m >> n; for(int i=m; i 0) && (firstPossible == true)) { firstPossible = false; firstNum = i; } } if (firstPossible == true) { cout
