본문 바로가기

전체 글

 (131)
59. 부분집합(DFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★ #include int n; int a[11]; void DFS(int x) { if(x == n+1) { for(int i = 1; i
58. 이진트리 깊이우선탐색(DFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★ #include void D(int x) { if(x < 8) { //printf("%d", x); 전위순회 D(x*2); //printf("%d", x); 중위순회 D(x*2+1); printf("%d", x); } } int main() { int n; scanf("%d", &n); D(n); return 0; } 1. 이진트리 깊이우선탐색(DFS) 는 부모노드, 좌/우 자식노드를 기본 구성으로 하는 이진트리를 이용한 탐색방법으로, 미로를 한 방향으로 길이 없을 때까지 갔다가 길이 막히면 다시 최근 갈림길로 돌아와 다른 방향으로 진행하는 느낌과 같다. 2. 전위순회는 부모노드 출력, 왼쪽 자식노드 출력, 오른쪽 자식노드 출력 순이다. 3. 중위순회는 왼쪽 자식노드 출력, 부모노드 출력, 오른쪽 자식노..
57. 재귀함수 이진수 출력 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★☆☆☆☆ #include void ToBinary(int x) { if(x > 0) { ToBinary(x/2); printf("%d", x%2); } } int main() { int n; scanf("%d", &n); ToBinary(n); return 0; } 1. ToBinary() 함수는 자연수 n을 2진수로 바꿔 출력하는 함수이다. 매개변수로 들어오는 int 형 변수 x를 0이 될 때까지 나누고 나눌 때마다 남는 나머지를 출력하는 방식이다.
56. 재귀함수 분석(스택 사용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆ #include using namespace std; void recur(int x) { if(x>0) { recur(x-1); printf("%d ", x); } } int main() { int n; scanf("%d", &n); recur(n); return 0; } 1. 재귀함수는 기본적으로 stack을 사용한다. 위 코드로 예시를 들어보겠다. - main() 메서드에서 recur()를 호출한다. - recur() 에서 매개변수로 받은 int x가 0이 아니라면 자기 자신을 한 번 더 호출하고, printf()로 x를 출력한다. - 여기서 잘못 생각하기 쉬운데, 바로 printf()가 실행되지 않는다는 점이다. - n = 3 일 때 예로 들어보겠다. recur(3) 의 스택 프레임(매개변수로 받은..
55. 기차운행(stack 응용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include #include using namespace std; int a[31]; int b[31]; int main() { int n, i = 1, j = 1; scanf("%d", &n); for(int i = 1; i
54. 올바른 괄호(stack) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆ #include #include using namespace std; int main() { stack s; char a[30]; scanf("%s", &a); for(int i = 0; a[i] != '\0'; i++) { if(a[i] == '(') s.push(a[i]); else if(a[i] == ')') { if(s.empty()) { printf("NO"); return 0; } else s.pop(); } } if(s.empty()) printf("YES"); else printf("NO"); return 0; } 1. string 입력을 저장할 char 배열 a, stack s 를 선언한다. 2. char a 의 원소를 확인하면서 '(' 라면 push, ')' 라면 pop을 한다. 3. ..
53. K진수 출력 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆ #include #include using namespace std; int top = -1; int a[1000]; void push(int x) { a[++top] = x; } int pop() { return a[top--]; } int main() { int n, k; scanf("%d %d", &n, &k); char b[20] = "0123456789ABCDEF"; while(n > 0) { push(n%k); n /= k; } while(top > -1) { printf("%c", b[pop()]); } return 0; } 1. 숫자를 변환해서 저장할 배열 a(스택으로서 사용될 것임), stack의 pop()과 push() 역할을 해줄 top, 변환할 숫자 n과 진수 k를 선언하고 입력받는..
52. Ugly Numbers (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆ #include #include #include using namespace std; int main() { int n, min = 2147000000, p2, p3, p5; scanf("%d", &n); vector a(1501, 0); vector b; a[1] = 1; p2 = 1; p3 = 1; p5 = 1; for(int i = 2; i

티스토리툴바