Week 8-1 : Binary Tree 2
<180605>
0) 트리에서 노드의 갯수 구하기
1 2 3 4 5 | int getNodeCnt(TreeNode *root) { if(root == NULL) return 0; return 1+getNodeCnt(root->left)+getNodeCnt(root->right); } | cs |
>> 트리의 노드의 갯수 = 자기 자신 + 왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수
1) 단말노드의 갯수 구하기
1 2 3 4 5 6 | int getLeafNode(TreeNode *root) { if(root == NULL) return 0; if(root->left == NULL && root->right == NULL) return 1; return getLeafNode(root->left) + getLeafNode(root->right); } | cs |
>> 트리에서 단말노드의 갯수 = 왼쪽 서브트리에서의 단말노드의 갯수 + 오른쪽 서브트리에서의 단말노드의 갯수
>> 3 라인에서의 탈출조건이 필요하다. 이 코드가 없다면, root == NULL 인 경우 에러가 발생한다.
>> root 가 NULL 이라는 것은 root 가 가리키는 트리노드가 없다는 뜻이다. 그런데 root->left 가 의미하는 것은 root가 가리키는 변수의 멤버 left 가 된다.
가리키는 변수가 없는데, 가리키는 변수의 멤버를 찾는 셈이 된다.
2) 전위순회, 중위순회의 순서가 주어졌을 때, 후위순회의 순서 구하기
전위순회 순서 : 0 1 3 6 7 4 2 5 8 9
중위순회 순서 : 6 3 7 1 4 0 2 8 5 9
1. 전위순회의 경우, 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 맨 왼쪽에 있는 0 이 루트라는 사실을 알 수 있다.
2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.
그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며, 2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.
전위순회 순서 : [0] [1 3 6 7 4] [2 5 8 9]
중위순회 순서 : [6 3 7 1 4] [0] [2 8 5 9]
위와 같이 생각할 수 있다.
3. 이젠 왼쪽 서브트리에 대해 생각해보자.
전위순회 순서 : [1 3 6 7 4]
중위순회 순서 : [6 3 7 1 4]
위와 마찬가지로 전위 순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 1 이 this 서브트리의 루트라는 사실을 알 수 있다.
4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.
그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.
5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 후위순회를 구하면 된다...!!
>> 프로그래밍 해보고 싶다면 도전!! (http://boj.kr/4256)
>> 내가 푼 코드 (https://github.com/YongHoonJJo/BOJ/blob/master/4256.cpp)
3) 중위순회, 후위순회의 순서가 주어졌을 때, 전위순회의 순서 구하기.
중위순회 순서 : 6 3 7 1 4 0 2 8 5 9
후위순회 순서 : 6 7 3 4 1 8 9 5 2 0
1. 후위순회의 경우, 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 순회를 한다. 그렇기 때문에 맨 오른쪽에 있는 0 이 루트라는 사실을 알 수 있다.
2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.
그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며, 2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.
3. 후위순회의 순서에서는 [6 7 3 4 1][8 9 5 2][0] 으로 생각할 수 있다.
여기서도 왼쪽 서브트리인 [6 7 3 4 1] 에 대해서 생각해보자. 후위순회는 왼쪽 서브트리에 대해서도 후위순회를 한다.
그렇기 때문에 1이 왼쪽 서브트리의 루트라는 것을 알 수 있다.
4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.
그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.
5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 전위순회를 구하면 된다...!!
4) 트리의 삭제
1 2 3 4 5 6 7 | int removeTree(TreeNode *root) { if(root == NULL) return ; removeTree(root->left); removeTree(root->right); free(root); } | cs |
>> 전위순회를 하면 왼쪽 서브트리와 오른쪽 서브트리의 루트를 찾아갈 수 없다.
>> 중위순회를 해도 오른쪽 서브트리의 루트를 찾아갈 수 없게 된다.
>> 그래서 후위순회로 삭제를 진행해야 한다.
5) 트리에서 데이터의 값이 홀수인 노드의 갯수를 구하기
1 2 3 4 5 6 7 | \int getOddNode(TreeNode *root) { int cnt=0; if(root == NULL) return 0; if(root->data & 1) cnt++; return cnt + getOddNode(root->left) + getOddNode(root->right); } | cs |
>> 트리에서 테이터의 값이 홀수인 노드의 갯수 = 자신(1 or 0) + 왼쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수 + 오른쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수
6) 디렉토리 용량 구하기.
>> 왼쪽 서브트리의 디렉토리의 용량 + 오른쪽 서브트리의 디렉토리의 용량 + 자기 자신의 용량
7) 수식트리
>> 단말노드에 피연산자가 들어있고, 그 외 노드에는 연산자가 들어있다.
>> 후위순회로 계산할 수 있다. 왼쪽 서브트리에서 계산한 결과와 오른쪽 서브트리에서 계산한 결과를 루트에 있는 연산자에 의한 연산을 하면 된다.
8) 레벨순회
- 큐 라는 자료구조를 사용하며, 나중에 배울 그래프에서의 너비우선탐색(BFS) 알고리즘과 완전히 동일하다.
- 또한 TreeNode의 포인터를 담아야 하므로, 23 라인에서 보는 것 처럼 큐의 데이터 타입을 TreeNode* 로 변경하였다.
(typedef element int 였다면 int를 TreeNode* 로 바꾸면 됬을텐데.. typedef element int 를 쓰는 이유를 다시한번 되새겨보자..!!)
- 알고리즘은 다음과 같다.
1) 우선 루트를 큐에 담는다.
2) 큐가 비어 있지 않다면,
3) 큐에 있는 노드 하나를 꺼내 해당 데이터를 출력한다.
4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다(노드가 존재할 경우). 그리고 2)로 돌아간다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <stdio.h> #include <stdlib.h> #define MAX 100 // Tree typedef struct TreeNode { int data; struct TreeNode * left; struct TreeNode * right; } TreeNode; TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) { TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode)); tmp->data = data; tmp->left = left; tmp->right = right; return tmp; } // Queue typedef struct queue { TreeNode * data[MAX]; int front; int rear; } Queue; void init(Queue * q) { q->front = 0; q->rear = 0; } int isEmpty(Queue * q) { return (q->front == q->rear); } int isFull(Queue * q) { return (q->rear + 1) % MAX == q->front; } void enqueue(Queue * q, TreeNode * data) { if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n"); else { q->rear = (q->rear + 1) % MAX; q->data[q->rear] = data; } } TreeNode* peek(Queue * q) { if (isEmpty(q)) { printf("(peek)큐가 비어있습니다. : "); return NULL; } return q->data[(q->front + 1) % MAX]; } void dequeue(Queue * q) { if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n"); else { q->front = (q->front + 1) % MAX; } } void level(TreeNode * root) { Queue q; init(&q); if (root) enqueue(&q, root); while (!isEmpty(&q)) { TreeNode * tmp = peek(&q); dequeue(&q); printf("%d ", tmp->data); if (tmp->left) enqueue(&q, tmp->left); if (tmp->right) enqueue(&q, tmp->right); } } int main() { TreeNode * t8 = makeTreeNode(8, NULL, NULL); TreeNode * t4 = makeTreeNode(4, t8, NULL); TreeNode * t5 = makeTreeNode(5, NULL, NULL); TreeNode * t6 = makeTreeNode(6, NULL, NULL); TreeNode * t7 = makeTreeNode(7, NULL, NULL); TreeNode * t2 = makeTreeNode(2, t4, t5); TreeNode * t3 = makeTreeNode(3, t6, t7); TreeNode * t1 = makeTreeNode(1, t2, t3); TreeNode * root = t1; level(root); } | cs |
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 8-2 : Binary Search Tree (종강) (추가:180814) (0) | 2018.06.08 |
|---|---|
| Week 7-2 : Tree, Binary Tree (0) | 2018.05.27 |
| Week 7-1 : Stack, Queue by Linked List (0) | 2018.05.19 |
| Week 6 : Maze(with stack) / Circular Queue (0) | 2018.05.16 |
| Week 5-2 : infix to postfix, exp(postfix) (0) | 2018.05.08 |
[1021] 회전하는 큐
[1021] 회전하는 큐 : http://boj.kr/1021
### 시뮬레이션 ###
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); vector<int> v; for(int i=1; i<=n; i++) v.push_back(i); int cur=0, ans=0; for(int i=0; i<m; i++) { int target, tmp = 0; int size = v.size(); scanf("%d", &target); for(int j=0; j<size; j++) { if(v[cur] == target) { v.erase(v.begin()+cur); if(cur == size-1) cur = 0; break; } cur = (cur+1)%size; tmp++; } ans += min(tmp, size-tmp); } printf("%d\n", ans); } | cs |
>> 24 라인이 중요한 것 같다. 중간에 있는 벡터를 삭제하면 자동으로 앞당겨져 cur 에 저장되어 있는 인덱스를 변경할 필요가 없지만,
맨 마지막 데이터가 삭제되면 cur 의 인덱스를 0으로 변경해야 한다.
비트 연산을 이용한 정수의 산술연산 (분석은 아직..)
- 출처 : http://blog.naver.com/PostView.nhn?blogId=kimsung9k&logNo=110121881497
<비트 연산을 이용한 정수의 산술연산 >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <cstdio> #include <vector> using namespace std; long long plus( long long a, long long b ) { long long xor1 = a^b; long long and1 = a&b; and1 = and1 << 1; while( ( and1&xor1 ) != 0 ) { long long txor = and1^xor1; long long tand = and1&xor1; long long uand = tand << 1; and1 = uand; xor1 = txor; } return xor1^and1; } long long minus( long long a, long long b ) { long long first = a^b; long long second = a^(a|b); first = first^second; return plus( first, plus( (~second), 1 ) ); } long long mult( long long a, long long b ) { bool a_is_minus = false; bool b_is_minus = false; bool is_odd = false; if( a < 0 ){ a_is_minus = true; a = ~minus( a,1 ); } if( b < 0 ){ b_is_minus = true; b = ~minus( b,1 ); } if( (b&1) == 1 ) is_odd = true; long long mult_a = 0LL; for( int i=1; i < 32; i=plus( i,1 ) ){ b = b >> 1; if( (b & 1) == 1 ) mult_a = plus( mult_a, (a << i) ); } if( is_odd ) mult_a = plus( mult_a, a ); if( a_is_minus^b_is_minus ) mult_a = plus( ~mult_a, 1 ); return mult_a; } int main() { int a, b; scanf("%d%d", &a, &b); printf("%lld\n", mult(a, b)); return 0; } | cs |
>> 매개변수와 리턴타입을 모두 long long 으로 변경하고, 46라인을 i < 32 로 변경하니, long long 까지 처리가 가능하였다.
>> a = 100000000, b = 100000000 을 입력으로 주면 10000000000000000 이 출력된다.
'Language > C' 카테고리의 다른 글
| scanf() 에서 공백을 포함한 문자열 입력받기 (0) | 2018.04.05 |
|---|---|
| printf() 서식문자 %g (0) | 2018.03.07 |
| 배열에서 배열의 크기 이상의 인덱스를 사용하게 되면... (0) | 2018.02.27 |
Week 11
<180530>
1) 1 ~ 7 사이의 데이터를 10번 입력 받았을 때, 1~7사이의 값들이 각각 몇 번씩 입력받았는지 프로그래밍
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <stdio.h> int main() { int cnt[8]={0}; for(int i=0; i<10; i++) { int k; scanf("%d", &k); cnt[k]++; } for(int i=1; i<8; i++) { printf("%d : ", i); for(int j=0; j<cnt[i]; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> 배열의 크기를 왜 8로 설정했는지 생각해보기.
>> 11번 라인이 끝났을 때, cnt[i] 에는 i 가 몇 번 입력이 들어왔는지에 대한 빈도수가 저장되어 있다..!!
>> input : 1 2 2 3 3 3 6 7 7 7
>> output
1 : *
2 : **
3 : ***
4 :
5 :
6 : *
7 : ***
2) -7 ~ 7 사이의 데이터를 10번 입력 받았을 때, 1~7사이의 값들이 각각 몇 번씩 입력받았는지 프로그래밍
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <stdio.h> int main() { int cnt[15]={0}; for(int i=0; i<10; i++) { int k; scanf("%d", &k); cnt[k+7]++; } for(int i=0; i<15; i++) { printf("%d : ", i-7); for(int j=0; j<cnt[i]; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> 1번 문제와 무엇이 달라졌는지 살펴보자.
>> 배열의 인덱스는 0부터 사용이 가능하다. 즉 -7을 처리하기 위해 1번 문제와 같이 해서는 안된다.
>> 하지만, -7을 0으로 생각하고 다른 숫자들도 +7 한 값으로 생각을 하면 이를 해결할 수 있다.
>> 10번 라인과 14번 라인처럼 하면 된다.
>> 13번 라인에서 for문의 횟수는 [-7, 7] 까지이르로 총 15개의 정수에 대해 다루므로..
3) 로또번호 생성하기 (보너스 번호 제외)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <stdio.h> #include <stdlib.h> #include <time.h> int main() { int lotto[46]={0}; int cnt=0; srand(time(NULL)); while(cnt < 6) { int k = rand()%45+1; if(lotto[k]==0) { lotto[k] = 1; cnt++; } } for(int i=1; i<=45; i++) if(lotto[i] == 1) printf("%d ", i); printf("\n"); return 0; } | cs |
>> 랜덤함수는 스스로 학습해보기.
>> 1~ 45사이의 숫자를 랜덤으로 추출해야 한다. 임의의 값을 45로 나눈 나머지는 0~44사이의 값이 된다. 1을 더하면 1~45 사이의 값이 된다.
>> 11번를 while(cnt < 6) 으로 한 이유를 잘 생각해보자. for(int i=0; i<6; i++) 로 하면 딱 6번 값을 추출한다.
>> 하지만 이렇게 되면 중복된 숫자가 나온경우를 처리할 수 없다.
>> lotto[i] == 1 이라는 것은 i라는 숫자가 한번 나왔었다는 뜻. 그렇기 때문에 13번 라인의 조건식을 만족하지 않아, 카운트도 되지 않는다. 이로써 중복된 숫자를 해결할 수 있다.
>> 배열의 인덱스를 가지고 놀 줄 알아야 한다
4) 2차원 배열 개념
- 2차원 배열의 선언 : int arr[4][5]; // 8x10 크기의 사각형으로 된 방을 만들었다고 생각하면 된다. 8개의 층으로 된 건물(0에서 7층, 각 층마다 10개의 방)
- 참고로 배열의 이름은 배열의 시작주소 이다...!! (중요)
5) 전치행렬 (전치행렬 개념은 모르면 검색해보기..!!)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <stdio.h> int main() { int matrix[3][4]; for(int i=0; i<3; i++) for(int j=0; j<4; j++) scanf("%d", &matrix[i][j]); for(int i=0; i<3; i++) { for(int j=0; j<4; j++) { printf("%d ", matrix[i][j]); } printf("\n"); } for(int i=0; i<4; i++) { for(int j=0; j<3; j++) { printf("%d ", matrix[j][i]); } printf("\n"); } return 0; } | cs |
>> 12-17 : 행(i)를 고정시키고 열 들을 한줄씩 출력
>> 19-24 : 열(i)를 고정시키고 행 들을 한줄씩 출력
>> 행렬의 합, 행렬의 곱 연산방법 확인 후 문제가 주어졌을 때, 어떻게 하면 될지 고민해보기..!
6) 3차원 배열 개념
7) 포인터 (변수)
1 2 3 4 5 6 7 8 9 10 11 | #include <stdio.h> int main() { int n; int *p; n = 10; p = &n; *p = 20; printf("%d %d\n", n, *p); } | cs |
8) 주소 개념잡기
- (1)은 위의 코드에서 5번 라인.
- (2)은 위의 코드에서 6번 라인.
- (3)은 위의 코드에서 7번 라인.
- (4)은 위의 코드에서 8번 라인.
- (5)은 위의 코드에서 9번 라인을 수행했을때의 결과를 그림으로 표기한 것임.
>> 포인터(변수)도 포인터이다. 다면 변수의 주소를 저장하는 공간이고,
변수의 주소를 저장하고 있다는 것은 일반적으로 4, 5그림과 같이 화살표로 표기하며, p라는 포인터(변수)를 통해 변수 n에 접근을 할 수 있다.
>> 8번 라인에서 &는 피연산자인 변수의 주소를 알려주는 연산자 이다. 그렇다면 scanf() 에서 "", 다음 주소가 필요하다는 것을 생각해볼 수 있다.
>> 9번 라인에서 *는 참조 연산다. 포인터 변수 p가 가리키는 변수를 참조하여 값을 저장하거나 읽어올 수 있다.
9) 문자열
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <stdio.h> int main() { char str[]="Hello World!"; printf("%s\n", str); str[6] = 'w'; printf("%s\n", str); str[5] = '\0'; printf("%s\n", str); return 0; } | cs |
>> 실행결과
Hello World!
Hello world!
Hello
>> 5 라인 : 배열의 크기를 지정하지 않고 초기화시 자동으로 초기화 한 만큼 크기가 설정된다.
>> 8 라인 : 문자열의 일부 문자를 수정했다. (변수형태의 문자열)
>> 문자열의 끝은 널문자이다. 11번 라인의 경우 중간에 널문자를 삽입했기 때문에 그 중간이 문자열의 끝으로 인식이 된 것이다
- 문자열의 입력
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> int main() { int n; char str[100]; scanf("%d", &n); scanf("%s", str); printf("%d : %s\n", n, str); return 0; } | cs |
- scanf() 를 통해 입력을 받을수 있으며, 공백을 포함하지 않는 문자열(일종의 한 단어)를 입력받을 수 있다.
>> 스캔에프 함수는 공백을 기준으로 입력을 받기 때문이다.
- 8번 라인 : & 연산자는 피연산자(변수)의 주소를 알려주는 연산자이다. 즉 저자리는 주소를 전달하는 자리이다.
- 9번 라인 : 여기서는 &가 없고 배열의 이름만 썼다. 배열의 이름은 배열의 시작주소 이기 때문이다.
'Tutoring > 18-1 C Lang' 카테고리의 다른 글
| Week 12 - 종강 (0) | 2018.06.06 |
|---|---|
| Week 10 (0) | 2018.05.23 |
| Week 09 (0) | 2018.05.16 |
| Week 08 (0) | 2018.05.09 |
| Week 07 (0) | 2018.05.05 |
Week 7-2 : Tree, Binary Tree
< 180517 >
1) 트리
- 계층구조를 표현하기 위한 비선형 자료구조. ex) 디렉토리
- 노드(형제, 부모, 자식, 루트, 단말)
- 서브트리의 개념 설명. 트리의 자식노드를 루트로 하는 트리.
- 레벨 : 루트노드 기준 노드까지의 거리. 루트의 레벨을 0 으로 두기도 하고, 1로 두기도 한다.
- 높이 : 최대레벨
- 트리의 예시 (그림 출처 : http://wwst.tistory.com/2)
- 트리의 종류 : 일반트리, 이진트리
2) 이진트리 (Binary Tree)
- 정의 : 각 노드별 자식노드가 두개 이하로 구성된 트리..(최대 두개의 자식노드)
- 성질 : 노드의 갯수 -1 = 간선의 수
- n 개의 노드로 최대 n 레벨을 만들수 있으며, 최소 ceil(log(n+1))의 레벨을 만들 수 있다. 로그의 밑은 2.
- 이진트리의 종류(일반 이진트리, 완전이진트리, 포화 이진트리)
- 포화이진트리 : 마지막 레벨까지 모든 레벨에 노드가 가득 차 있는 트리.
- 완전이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리.
- 일반이진트리 : 완전도 포화도 아닌 트리 (아래 그림에서 TreeA 는 일반 이진트리)
- 이진트리의 서브트리 (그림출처 : https://kks227.blog.me/221028710658)
>> 서브트리는 부모노드를 기준으로, 한 자식노드를 루트로 하는 트리
< 180529 >
- 이진 트리의 표현
1) 배열을 이용한 표션
>> 주로 힙(Heap)/우선순위 큐에서 사용
>> 구현의 편의상 0번째 인덱스를 사용하지 않는 경우가 많은 것 같다.
>> 현재노드 기준, 부모노드의 인덱스는 현재노드의 인덱스 / 2
>> 현재노드 기준, 왼쪽 자식의 인덱스는 현재노드의 인덱스 * 2
>> 현재노드 기준, 오른쪽 자식의 인덱스는 현재노드의 인덱스 * 2 + 1
2) 링크 표현
1 2 3 4 5 | typedef struct TreeNode { int data; struct TreeNode * left; struct TreeNode * right; } TreeNode; | cs |
>> 노드는 이런식으로 디자인을 한다.
- 트리의 순회 (그림출처 : https://kks227.blog.me/221028710658)
전위순회 : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 탐색
중위순회 : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 탐색
후위순회 : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 탐색
레벨순회 : 큐를 이용, 구현은 다음 시간에..!
>> 전위순회의 경우, 왼쪽 서브트리를 순회할때, 재귀적으로 왼쪽 서브트리의 루트를 기준으로 전위순회를 한다.
Preorder : ( 0 ) ( 1 3 6 7 4 ) ( 2 5 8 9 ) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리)
왼쪽 서브트리의 경우 1 3 6 7 4 인데 마찬가지로 (1) (3 6 7) (4) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.
위에서 왼쪽 서브트리는 3 6 7 인데, 마찬가지로 (3) (6) (7) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.
>> 중위순회, 후위순회도 마찬가지..!!
>> 왼쪽 ,오른쪽이 아니다. 왼쪽 서브트리, 오른쪽 서브트리. 개념 확실히 잡고 넘어가자.
>> 루트 기준 왼쪽 자식 노드는 왼쪽 서브트리의 루트가 되며, 루트 기준 오른쪽 자식노드는 오른쪽 서브트리의 루트가 된다..!!
>> 트리를 삭제할 때에는 후위순회를 사용해야 한다.
- 구현
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int data; struct TreeNode * left; struct TreeNode * right; } TreeNode; TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) { TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode)); tmp->data = data; tmp->left = left; tmp->right = right; return tmp; } void preorderPrint(TreeNode * root) { if (root) { printf("%d ", root->data); preorderPrint(root->left); preorderPrint(root->right); } } void inorderPrint(TreeNode * root) { if(root){ inorderPrint(root->left); printf("%d ", root->data); inorderPrint(root->right); } } void postorderPrint(TreeNode * root) { if(root) { postorderPrint(root->left); postorderPrint(root->right); printf("%d ", root->data); } } int nodeCount(TreeNode * root) { int count = 0; if (root) count = nodeCount(root->left) + nodeCount(root->right) + 1; return count; } int height(TreeNode * root) { int count=0; if (root) { int L = height(root->left); int R = height(root->right); count = (L > R ? L : R) + 1; } return count; } void clear(TreeNode * root) { if (root) { clear(root->left); clear(root->right); free(root); } } int main() { TreeNode * t8 = makeTreeNode(8, NULL, NULL); TreeNode * t4 = makeTreeNode(4, t8, NULL); TreeNode * t5 = makeTreeNode(5, NULL, NULL); TreeNode * t6 = makeTreeNode(6, NULL, NULL); TreeNode * t7 = makeTreeNode(7, NULL, NULL); TreeNode * t2 = makeTreeNode(2, t4, t5); TreeNode * t3 = makeTreeNode(3, t6, t7); TreeNode * t1 = makeTreeNode(1, t2, t3); TreeNode * root = t1; preorderPrint(root); printf("\n"); inorderPrint(root); printf("\n"); postorderPrint(root); printf("\n"); printf("노드 갯수 : %d\n", nodeCount(root)); printf("Tree의 높이 : %d\n", height(root)); level(root); } | cs |
>> 42 라인 : 트리에서 노드의 갯수는 왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 1(기준 트리의 루트노드) 이다.
>> preorderPrint() 라는 함수는 한 트리의 루트를 매개변수로 전달 받는다.
그리고 이 트리는 매개변수로 전달받은 루트를 기준으로 하는 트리에 대해 전위순회를 하는 함수이다.
전위순호는 루트를 방문하고, 왼쪽 서브트리에 대해 전위순회를 하고, 오른쪽 서브트리에 대해 전위순회를 진행하면 된다.
왼쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 왼쪽 서브트리의 루트를 매개변수로 전달하면 된다.
마찬가지로 오른쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 오른쪽 서브트리의 루트를 매개변수로 전달하면 된다.
>> 48 라인 : 트리의 높이는 max(왼쪽 서브트리의 높이, 오른쪽 서브트리의 높이)+1 이 된다.
>> 58 라인 : 트리의 삭제, 후위순회 방식으로 진행한다.
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 8-2 : Binary Search Tree (종강) (추가:180814) (0) | 2018.06.08 |
|---|---|
| Week 8-1 : Binary Tree 2 (0) | 2018.06.05 |
| Week 7-1 : Stack, Queue by Linked List (0) | 2018.05.19 |
| Week 6 : Maze(with stack) / Circular Queue (0) | 2018.05.16 |
| Week 5-2 : infix to postfix, exp(postfix) (0) | 2018.05.08 |
Week 10
<180523>
1) 지역변수
- 사용 간능한 범위는 중괄호 내부.
- 함수의 매개변수도 지역변수이다. >> 함수 내에서 사용 가능.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <stdio.h> void f() { int k=0; printf("%d\n", k); k += 1; } int main() { int n=5; f(); f(); if(n == 5) { int k = 10; printf("%d\n", k); } //printf("%d\n", k); return 0; } | cs |
>> 13라인 실행결과 : 0
>> 14라인 실행결과 : 0
>> 18라인 실행결과 : 10
>> 20라인은 주석을 해제하면 오류. K는 if문의 중괄호 내에서만 사용 가능하다..!!
2) 전역변수
- 프로그램이 실행될 때 생성, 프로그램이 종료될 때 소멸.
- 별도로 초기화 하지 않으면 자동으로 0으로 초기화된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int k; void f() { printf("%d\n", k); k += 1; } int main() { f(); f(); return 0; } | cs |
>> 13라인 실행결과 : 0
>> 14라인 실행결과 : 1
>> 14 라인이 끝났을 때 k에는 2가 저장되어있다.
3) 정적(static)변수
- 지역변수와 전역변수의 특징을 동시에 갖는 변수라고 생각하면 된다
- 전역변수처럼 프로그램이 시작될 때 생성되어, 프로그램이 종료될 때 소멸되고, 자동으로 0으로 초기화 된다.
- 지역변수처름 중괄호 내에서 사용가능하다. 즉 아래의 정적변수 k는 f() 함수 내에서만 사용가능한 전역변수라고 생각하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <stdio.h> void f() { static int k; printf("%d\n", k); k += 1; } int main() { f(); f(); return 0; } | cs |
>> 13라인 실행결과 : 0
>> 14라인 실행결과 : 1
>> f() 함수가 두번째로 실행되었을 땐 5번 라인은 생략된 상태로 실행된다고 생각하면 된다.
4) 외부변수, 자동변수, 레지스터 변수
참고 : http://jeongchul.tistory.com/342
5) 배열 선언 및 초기화
- 자료형 배열의이름[배열의크기]; 라는 형태로 선언.
- int arr[10]; // 크기가 10인 정수 데이터를 담을 수 있는 배열 arr
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include <stdio.h> int main() { int arr[10]; int arr2[5] = {1, 2, 3, 4, 5}; int arr3[5] = {0}; for(int i=0; i<5; i++) printf("%d\n", arr3[i]); return 0; } | cs |
>> 7 라인 : 배열의 모든 요소를 0으로 초기화 하는 방법.
>> arr3 이란 배열의 요소들은 0으로 채워져있다.
6) 최대값, 최소값,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <stdio.h> int main() { int arr[10]; int max, min; for(int i=0; i<10; i++) scanf("%d", &arr[i]); max = min = arr[0]; for(int i=1; i<10; i++) { if(max < arr[i]) max = arr[i]; if(min > arr[i]) min = arr[i]; } printf("max: %d\n", max); printf("min: %d\n", min); return 0; } | cs |
>> i번째 배열요소 값이 최대값일 때, 그때의 값을 갱신
7) 최대값의 인덱스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include <stdio.h> int main() { int arr[10]; int max, min; int maxI, minI; for(int i=0; i<10; i++) scanf("%d", &arr[i]); max = min = arr[0]; maxI = minI = 0; for(int i=1; i<10; i++) { if(max < arr[i]) { max = arr[i]; maxI = i; } if(min > arr[i]) { min = arr[i]; minI = i; } } printf("maxI: %d\n", maxI); printf("minI: %d\n", minI); return 0; } | cs |
>> i번째 배열요소 값이 최대값일 때, 그때의 인덱스 i도 갱신
8) 재귀함수 호출 과정
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> void f(int n) { if(n < 1) return ; f(n-1); printf("%d\n", n); } int main() { f(5); return 0; } | cs |
>> f(0) 이 호출되었을 때, 5번 라인의 조건을 만족하므로 함수가 종료된다.
>> f(1) 에서 아직 실행되지 않은 7번 라인이 실행(1출력)되고, 더이상 실행할 것이 없으므로 f(1) 은 종료된다. 종료 후 f(1)을 호출한 곳으로 돌아간다.
>> f(2) 에서 아직 실행되지 않은 7번 라인이 실행(2출력)되고, 더이상 실행할 것이 없으므로 f(2) 은 종료된다. 종료 후 f(2)을 호출한 곳으로 돌아간다.
>> f(3) 에서 아직 실행되지 않은 7번 라인이 실행(3출력)되고, 더이상 실행할 것이 없으므로 f(3) 은 종료된다. 종료 후 f(3)을 호출한 곳으로 돌아간다.
>> f(4) 에서 아직 실행되지 않은 7번 라인이 실행(4출력)되고, 더이상 실행할 것이 없으므로 f(4) 은 종료된다. 종료 후 f(4)을 호출한 곳으로 돌아간다.
>> f(5) 에서 아직 실행되지 않은 7번 라인이 실행(5출력)되고, 더이상 실행할 것이 없으므로 f(5) 은 종료된다. 종료 후 f(5)을 호출한 곳(여기서는 main() 함수의 12번 라인)으로 돌아간다.
9) 빈도수
- 다음주..!!
'Tutoring > 18-1 C Lang' 카테고리의 다른 글
| Week 12 - 종강 (0) | 2018.06.06 |
|---|---|
| Week 11 (0) | 2018.05.30 |
| Week 09 (0) | 2018.05.16 |
| Week 08 (0) | 2018.05.09 |
| Week 07 (0) | 2018.05.05 |
[9177] 단어 섞기
[9177] 단어 섞기 : http://boj.kr/9177
### DP ###
d[i][j] : 문자열 a의 i번째, 문자열 b의 j번째 인덱스에서 시작해서 단어를 섞어 세번째 문자열을 만들 수 있는지 여부.
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include <stdio.h> #include <string.h> int aLen, bLen; char a[201], b[201], c[401]; int d[201][201]; int word(int aIdx, int bIdx, int cIdx) { int *ret = &d[aIdx][bIdx]; if(aIdx == aLen && bIdx == bLen) return 1; if(*ret != -1) return *ret; *ret = 0; if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1); if(*ret) return *ret; if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1); return *ret; } int main() { int n; scanf("%d", &n); for(int tc=1; tc<=n; tc++) { scanf("%s%s%s", a, b, c); printf("Data set %d: ", tc); aLen = strlen(a); bLen = strlen(b); memset(d, -1, sizeof(d)); word(0, 0, 0) ? puts("yes") : puts("no"); } return 0; } | cs |
>> 처음에는 그리디방식으로 햇는데, 두번째 테케가 반례가 되어버렸다.
>> 유형이 DP 라고 되어 있어서 생각을 바꿔보았다...
<시간초과 코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <stdio.h> #include <string.h> int aLen, bLen; char a[201], b[201], c[401]; int d[201][201][401]; int word(int aIdx, int bIdx, int cIdx) { int *ret = &d[aIdx][bIdx][cIdx]; if(aIdx == aLen && bIdx == bLen) return 1; if(*ret != -1) return *ret; *ret = 0; if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1); if(*ret) return *ret; if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1); return *ret; } int main() { int n; scanf("%d", &n); for(int tc=1; tc<=n; tc++) { int ai=0, bi=0, ci=0; scanf("%s%s%s", a, b, c); printf("Data set %d: ", tc); aLen = strlen(a); bLen = strlen(b); memset(d, -1, sizeof(d)); word(0, 0, 0) ? puts("yes") : puts("no"); } return 0; } | cs |
>> AC 받은 코드와 차이가 있다면 cache 역할을 하는 배열을 3차원으로 잡은것. 생각해보면 2차원으로 충분하단 생각이 들었다.
>> 그리고 시간초과 난 이유를 곰곰히 생각해보니, 매 테케마다(n*200*200*400에 해당하는) memset() 을 돌려 그런 것 같아.
'BOJ > DP' 카테고리의 다른 글
| [11985] 오렌지 출하 (0) | 2018.06.21 |
|---|---|
| [2602] 돌다리 건너기 (0) | 2018.05.17 |
| [9252] LCS2 (0) | 2018.04.22 |
| [9251] LCS (0) | 2018.04.21 |
| [14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[DICTIONARY] 고대어 사전
[DICTIONARY] 고대어 사전 : https://algospot.com/judge/problem/read/DICTIONARY
### 위상정렬 ###
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include <cstdio> #include <iostream> #include <string> #include <vector> #include <queue> using namespace std; int main() { int tc; scanf("%d", &tc); while(tc--) { int n; scanf("%d", &n); vector<string> v; for(int i=0; i<n; i++) { string s; cin >> s; v.push_back(s); } int ind[26]={0}; vector<int> g[26]; for(int i=1; i<n; i++) { int idx=0; while(v[i-1][idx] != 0 && v[i][idx] != 0) { if(v[i-1][idx] == v[i][idx]) idx++; else break; } if(v[i-1][idx] != 0 && v[i][idx] != 0) { g[v[i-1][idx]-'a'].push_back(v[i][idx]-'a'); ind[v[i][idx]-'a']++; } } queue<int> q; for(int i=0; i<26; i++) { if(!ind[i]) q.push(i); } vector<char> ans; while(!q.empty()) { int cur = q.front(); q.pop(); ans.push_back('a'+cur); for(int i=0; i<g[cur].size(); i++) { int next = g[cur][i]; ind[next]--; if(!ind[next]) { q.push(next); } } } if(ans.size() != 26) puts("INVALID HYPOTHESIS"); else { for(int i=0; i<ans.size(); i++) printf("%c", ans[i]); puts(""); } } return 0; } | cs |
<예전에 AC 받은 코드> - 코드를 보면 종만북 솔루션으로 있는 코드같아 보인다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> order; vector<bool> visited; vector<vector<int> > v; void makeGraph(const vector<string> &words) { v = vector<vector<int> >(26, vector<int>(26, 0)); for(int i=1; i<words.size(); i++) { int len = min(words[i-1].size(), words[i].size()); for(int k=0; k<len; k++) { int a = words[i-1][k]-'a'; int b = words[i][k]-'a'; if(a != b) { v[a][b] = 1; break; } } } } void dfs(int s) { visited[s] = 1; for(int i=0; i<v.size(); i++) if(v[s][i] && !visited[i]) dfs(i); order.push_back(s); } vector<int> topologicalSort() { int i, j, n=v.size(); visited = vector<bool>(n, 0); order.clear(); for(i=0; i<n; i++) if(!visited[i]) dfs(i); reverse(order.begin(), order.end()); for(i=0; i<n; i++) for(j=i+1; j<n; j++) if(v[order[j]][order[i]]) return vector<int>(); return order; } int main() { int tc; scanf("%d", &tc); while(tc--) { int n; vector<string> words; scanf("%d", &n); while(n--) { string s; cin >> s; words.push_back(s); } makeGraph(words); vector<int> ans = topologicalSort(); n = ans.size(); if(!n) puts("INVALID HYPOTHESIS"); else { for(int i=0; i<n; i++) { printf("%c", ans[i]+'a'); } puts(""); } } } | cs |
'PS > 종만북' 카테고리의 다른 글
| [RUNNINGMEDIAN] 변화하는 중간 값 (0) | 2018.07.20 |
|---|---|
| [BOGGLE] 보글게임 (0) | 2018.04.30 |
| [MATCHORDER] 출전 순서 정하기 (0) | 2018.04.20 |
| [NUMBERGAME] 숫자게임 (0) | 2018.04.17 |
| [POLY] 폴리오미노 (0) | 2018.04.16 |
[4803] 트리 : http://boj.kr/4803
- 정점의 갯수를 세고, 간선의 갯수를 센다.
- 트리는 정점의 갯수-1 이 간선의 갯수라는 성질을 만족한다.
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <cstdio> #include <cstring> #include <vector> using namespace std; int n, m; bool visited[501]; bool check[501]; int dfsV(vector<int> v[], int s) { int ret = 1; visited[s] = 1; for(int i=0; i<v[s].size(); i++) { int next = v[s][i]; if(!visited[next]) ret += dfsV(v, next); } return ret; } int dfsE(vector<int> v[], int s) { int ret=v[s].size(); check[s] = 1; for(int i=0; i<v[s].size(); i++) { int next = v[s][i]; if(!check[next]) ret += dfsE(v, next); } return ret; } int main() { int tc=0; while(1) { int ans=0; scanf("%d%d", &n, &m); if(!n && !m) break; vector<int> v[501]; while(m--) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } memset(visited, 0, sizeof(visited)); memset(check, 0, sizeof(check)); for(int i=1; i<=n; i++) { if(!visited[i]) { int vertex = dfsV(v, i); int edge = dfsE(v, i); if(vertex-1 == edge/2) ans++; } } tc++; printf("Case %d: ", tc); if(ans == 0) puts("No trees."); else if(ans == 1) puts("There is one tree."); else printf("A forest of %d trees.\n", ans); } return 0; } | cs |
<예전코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <cstdio> #include <vector> using namespace std; int v, e; void dfs(vector<int> g[], bool visited[], int cur) { visited[cur] = true; v++; for(int i=0; i<g[cur].size(); i++) { int next = g[cur][i]; e++; if(!visited[next]) { dfs(g, visited, next); } } } int main() { int tc=1; while(1) { int n, m; scanf("%d %d", &n, &m); if(!n && !m) break; vector<int> g[501]; while(m--) { int a, b; scanf("%d %d", &a, &b); g[a].push_back(b); g[b].push_back(a); } int ans=0; bool visited[501]={0}; for(int i=1; i<=n; i++) { if(!visited[i]) { v = e = 0; dfs(g, visited, i); if(v-1 == e/2) ans++; } } printf("Case %d: ", tc++); if(!ans) puts("No trees."); else ans > 1 ? printf("A forest of %d trees.\n", ans) : puts("There is one tree."); } return 0; } | cs |
>> dfs 를 한번만 호출해서 정점의 수와 간선의 수를 카운트했다.
'BOJ > Tree' 카테고리의 다른 글
| [11725] 트리의 부모 찾기 (0) | 2018.05.20 |
|---|---|
| [1991] 트리 순회 (0) | 2018.05.20 |
[Java] String 의 split() 메서드
< About split() 메서드 (String) >
토큰 문자열을 주면 그거대로 쪼개져 스트링의 배열을 리턴한다고만 알고 있었다.
그런데 "(123x456)" 이란 문자열이 있는데, 123 과 456 문자열만 따로 취하고 싶어서 split("x") 를 하는데 안쪼개진다.
split("(") 도 안쪼개진다...
당황스러웠다. 그래서 구글링...!!
알고보니 토큰 문자열은 정규식으로 이루어진 문자열이였다. 어쩐지 미리보기로 보이는 파라미터가 regex 였다 싶었는데...
String[] s = imgSize.split("[^0-9]");
위와 같이 스플릿을 하면,
s[1] 에는 123이, s[2] 에는 456 이 저장되게 된다.
