[11725] 트리의 부모 찾기
[11725] 트리의 부모 찾기 : http://boj.kr/11725
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; int main() { int n; scanf("%d", &n); vector<int> v[100001]; for(int i=1; i<n; i++) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } vector<int> p(n+1, 0); queue<int> q; q.push(1); p[1] = -1; while(!q.empty()) { int parent = q.front(); q.pop(); for(int i=0; i<v[parent].size(); i++) { int child = v[parent][i]; if(!p[child]) { q.push(child); p[child] = parent; } } } for(int i=2; i<=n; i++) printf("%d\n", p[i]); return 0; } | cs |
>> 부모를 찾지 못했다면 큐에 넣고 부모 저장. BFS.
'BOJ > Tree' 카테고리의 다른 글
| [4803] 트리 (0) | 2018.05.21 |
|---|---|
| [1991] 트리 순회 (0) | 2018.05.20 |
[1991] 트리 순회
[1991] 트리 순회 : http://boj.kr/1991
<소스코드>
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 | #include <stdio.h> char tree[26][2]; void pre(int root) { if(root == '.') return ; printf("%c", root+'A'); pre(tree[root][0]); pre(tree[root][1]); } void in(int root) { if(root == '.') return ; in(tree[root][0]); printf("%c", root+'A'); in(tree[root][1]); } void post(int root) { if(root == '.') return ; post(tree[root][0]); post(tree[root][1]); printf("%c", root+'A'); } int main() { int n; scanf("%d", &n); while(n--) { char p, lc, rc; scanf(" %c %c %c", &p, &lc, &rc); tree[p-'A'][0] = lc == '.' ? lc : lc-'A'; tree[p-'A'][1] = rc == '.' ? rc : rc-'A'; } pre(0); puts(""); in(0); puts(""); post(0); puts(""); return 0; } | cs |
'BOJ > Tree' 카테고리의 다른 글
| [4803] 트리 (0) | 2018.05.21 |
|---|---|
| [11725] 트리의 부모 찾기 (0) | 2018.05.20 |
보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.
Week 7-1 : Stack, Queue by Linked List
<180517>
- 연결리스트로 구현한 스택
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 | #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *link; } Node; typedef struct stack { Node *top; } Stack; void init(Stack *ps) { ps->top = NULL; } int isEmpty(Stack *ps) { return ps->top == NULL; } void push(Stack *ps, int data) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->link = NULL; if(!isEmpty(ps)) newNode->link = ps->top; ps->top = newNode; } int peek(Stack *ps) { return ps->top->data; } int pop(Stack *ps) { Node *delNode = ps->top; int ret = delNode->data; ps->top = ps->top->link; free(delNode); return ret; } int main() { Stack s; init(&s); isEmpty(&s) ? puts("Empty") : puts("No"); push(&s, 10); push(&s, 20); if(!isEmpty(&s)) printf("%d\n", peek(&s)); if(!isEmpty(&s)) printf("%d\n", pop(&s)); if(!isEmpty(&s)) printf("%d\n", peek(&s)); return 0; } | cs |
>> 실행결과
Empty
20
20
10
- 연결리스트로 구현한 큐
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 | #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *link; } Node; typedef struct queue { Node *f, *r; } Queue; void init(Queue *pq) { pq->f = pq->r = NULL; } int isEmpty(Queue *pq) { return pq->f == NULL; } void enqueue(Queue *pq, int data) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->link = NULL; if(isEmpty(pq)) pq->f = newNode; else pq->r->link = newNode; pq->r = newNode; } int peek(Queue *pq) { return pq->f->data; } int dequeue(Queue *pq) { Node *delNode = pq->f; int ret = delNode->data; pq->f = pq->f->link; free(delNode); return ret; } int main() { Queue q; init(&q); isEmpty(&q) ? puts("Empty") : puts("No"); enqueue(&q, 10); enqueue(&q, 20); if(!isEmpty(&q)) printf("%d\n", peek(&q)); if(!isEmpty(&q)) printf("%d\n", dequeue(&q)); if(!isEmpty(&q)) printf("%d\n", peek(&q)); return 0; } | cs |
>> 실행결과
Empty
10
10
20
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 8-1 : Binary Tree 2 (0) | 2018.06.05 |
|---|---|
| Week 7-2 : Tree, Binary Tree (0) | 2018.05.27 |
| Week 6 : Maze(with stack) / Circular Queue (0) | 2018.05.16 |
| Week 5-2 : infix to postfix, exp(postfix) (0) | 2018.05.08 |
| Week 5-1 : Circular Doubly Linked List / Stack ADT (0) | 2018.05.08 |
[2602] 돌다리 건너기
[2602] 돌다리 건너기 : http://boj.kr/2602
- 난 3차원으로 풀었는데, 다른 사람들은 2차원으로 풀었다.
d[bidx][ad][sidx] : 상태가 ad(0은 천사차례, 1은 악마차례) 일때,
bidx번째 돌다리에서, sidx 번째 문자부터 시작하는 문자열에 적힌 순서대로 다리를 건널 수 있는 방법의 수
<소스코드>
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 | #include <stdio.h> char str[21]; char ang[101], dev[101]; int d[101][2][21]; int bridge(int bidx, int ad, int sidx) { int *ret = &d[bidx][ad][sidx]; if(!str[sidx]) return 1; if(ad == 0 && !ang[bidx]) return 0; if(ad == 1 && !dev[bidx]) return 0; if(*ret) return *ret; if(ad == 0) { if(ang[bidx] == str[sidx]) *ret = bridge(bidx+1, !ad, sidx+1); *ret += bridge(bidx+1, ad, sidx); } else { if(dev[bidx] == str[sidx]) *ret = bridge(bidx+1, !ad, sidx+1); *ret += bridge(bidx+1, ad, sidx); } return *ret; } int main() { scanf("%s%s%s", str, ang, dev); printf("%d\n", bridge(0, 0, 0)+bridge(0, 1, 0)); return 0; } | cs |
>> 천사다리를 먼저 택한 경우 + 악마다리를 먼저 택한 경우
'BOJ > DP' 카테고리의 다른 글
| [11985] 오렌지 출하 (0) | 2018.06.21 |
|---|---|
| [9177] 단어 섞기 (0) | 2018.05.22 |
| [9252] LCS2 (0) | 2018.04.22 |
| [9251] LCS (0) | 2018.04.21 |
| [14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
Week 6 : Maze(with stack) / Circular Queue
< 180515 >
- 스택의 응용 : 미로탐색
<미로탈출 초기상태>
- 시작좌표는 (1, 0)
- 도착좌표는 (4, 5)
- 알고리즘
1) 시작좌표를 현재좌표로 설정
2) 현재좌표가 도착좌표가 아니면
2-1) 현재좌표를 방문체크.
2-2) 현재좌표 기준 상하좌우의 좌표를 스택에 넣음.
2-2-1) 스택에 넣기전, 미로의 영역을 벗어나거나, 이미 방문한 좌표는 스택에 넣지 않는다. (예외처리)
2-3) 스택이 비어 있는지 확인. 비어있다면, 탈출 불가능한 미로
2-4) 스택에서 좌표 하나를 꺼내어 현재 좌표로 변경 후 2)로 돌아간다.
3) 탈출성공.
- 현재좌표 기준 상하좌우 좌표
- 미로 탈출 과정 (현재 위치 : H, 방문체크 : -, 방문체크한 곳 기준 상하좌우의 좌표를 스택에 담음.)
>> 이러한 과정으로 진행이 된다.
- Queue 정의 : 먼저 들어온 데이터가 먼저 꺼내지는 자료구조
- 예시 : 버스에서 줄서기(앞에 선 사람이 먼저 탐),
스타크래프트 게이트웨이(질럿, 드라군, 다크 순으로 찍으면 질럿, 드라군, 다크 순으로 나온다.)
- 기본 큐
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 | #include <stdio.h> #include <stdlib.h> #define MAX 100 typedef struct queue { int q[MAX]; int f, r; } Queue; void init(Queue * q) { q->f = q->r = 0; } int isEmpty(Queue * q) { return (q->f == q->r); } void enqueue(Queue * q, int data) { q->q[(q->r)++] = data; } int peek(Queue * q) { return q->q[q->f]; } int dequeue(Queue * q) { return q->q[q->f++]; } int main() { Queue q; init(&q); enqueue(&q, 1); enqueue(&q, 9); enqueue(&q, 9); enqueue(&q, 8); if(!isEmpty(&q)) printf("%d\n", dequeue(&q)); if(!isEmpty(&q)) printf("%d\n", peek(&q)); return 0; } | cs |
>> 데이터의 삽입은 rear 가, 데이터의 삭제(꺼내기)는 front 를 이용한다.
>> 위와 같이 코드를 작성하면, 배열 앞 공간에 낭비가 발생한다. >> 원형 큐로 대체..!!
- 원형 큐
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 | #include <stdio.h> #include <stdlib.h> #define MAX 100 typedef struct queue { int q[MAX]; int f, r; } Queue; void init(Queue * q) { q->f = q->r = 0; } int isEmpty(Queue * q) { return (q->f == q->r); } void enqueue(Queue * q, int data) { q->r = (q->r+1)%MAX; q->q[(q->r)] = data; } int peek(Queue * q) { return q->q[(q->f+1)%MAX]; } int dequeue(Queue * q) { q->f = (q->f+1)%MAX; return q->q[q->f]; } int main() { Queue q; init(&q); enqueue(&q, 1); enqueue(&q, 9); enqueue(&q, 9); enqueue(&q, 8); if(!isEmpty(&q)) printf("%d\n", dequeue(&q)); if(!isEmpty(&q)) printf("%d\n", peek(&q)); return 0; } | cs |
>> 처음 비어있는 상태는 f와 r이 같은 곳을 가리킬때..!!
>> 원형큐는 한칸을 비워둔다. 그렇지 않으면 비어있는 상태와 가득차있는 상태를 구분할 수 없게 된다.
>> f가 가리키는 곳는 마지막으로 데이터를 꺼낸 곳이라고 생각하면 된다. 즉 비어있는 곳.
>> 마찬가지로 데이터의 삽입은 r 로, 데이터를 꺼내는 작업은 f 를 이용한다.
>> 원형큐이기 때문에 배열의 마지막 인덱스 다음에 0번째 인덱스로 와야 한다.
이를 해결해주는 방법이 배열의 다음 인덱스를 항상 배열의 크기로 나눈 나머지로 처리하면 된다.
모듈러 연산을 하면, 배열이 크기보다 작은 인덱스들은 자기 자신이 되지만,
마지막인덱스에서 다음으로 넘어가면 배열의 크기가 되는데, 이는 크기로 나눈 나머지를 계산하면 0이 된다.
- 원형큐에서의 문제.
1) 배열의 크기가 8이고, f가 3을, r이 5을 가리킬 때, 삽입되어 있는 데이터의 갯수는?? 2개
2) 배열의 크기가 8이고, f가 5을, r이 3을 가리킬 때, 삽입되어 있는 데이터의 갯수는?? 6개
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 7-2 : Tree, Binary Tree (0) | 2018.05.27 |
|---|---|
| Week 7-1 : Stack, Queue by Linked List (0) | 2018.05.19 |
| Week 5-2 : infix to postfix, exp(postfix) (0) | 2018.05.08 |
| Week 5-1 : Circular Doubly Linked List / Stack ADT (0) | 2018.05.08 |
| Week 4-2 : Circular Linked List (0) | 2018.04.20 |
Week 09
< 180516 >
0)
- break : 가장 가까이에 있는 반복문 하나를 빠져나간다.
- continue : 가장 가까이에 있는 반복문으로 돌아간다.
>> 보통 continue 문을 사용하지 않고 코딩이 가능하다..!!
1) 라이브러리 함수 vs 사용자 정의 함수
- 라이브러리 함수 : 이미 누군가가 만들어 놓은 함수
>> 우리는 가져다 쓰면 된다. 보통 어딘가의 헤더파일에 들어있다.
>> printf() 도 함수이다. stdio.h 라는 헤더파일에 들어있다. 문자열의 갯수를 리턴한다.
>> scanf() 도 함수이다. 어떤 값을 리턴하는지 검색해보길 바람..^^
- 사용자 정의 함수는 우리가 직접 만들어서 사용하는 함수..!!
2) 사용자 정의 함수의 종류는 크게 네종료
1 2 3 4 5 6 7 | void f1(void); void f2(int a); int f3(void); int f4(int a); | cs |
>> f1 함수는 함수의 결과로 아무것도 돌려주지 않고, 어떤 값도 전달 받지 않는 함수.
>> f2 함수는 함수의 결과로 아무것도 돌려주지 않고, 함수가 호출될 때 정수 데이터 한개를 전달받는 함수
>> f3 함수는 함수의 결과로 정수값을 리턴하고, 함수가 호출될 때 어떤 값도 전달받지 않는 함수
>> f4 함수는 함수의 결과로 정수값을 리턴하고, 함수가 호출될 때 정수 데이터 한개를 전달받는 함수
>> f1, f2 함수는 매개변수를 받지 않는 함수이다. 이런경우 void 를 쓰지만, 매개변수자리의 void 는 생략 가능하다.
>> 여기서 f2, f4 의 경우 변수 a를 매개변수라고 하며, 매개변수를 필요시 여러개를 설정할 수 있다.
>> f3, f4 는 리턴타입이 있는 함수로, 필요에 따라 우리가 알고 있는 자료형으로 대체해서 정의할 수 있다.
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 25 26 27 28 29 30 31 32 33 34 35 | #include <stdio.h> void f1(void) { printf("Hello world\n"); } void f2(int a) { for(int i=1; i<=a; i++) printf("%d\n", i); } int f3(void) { int k; scanf("%d", &k); return k; } int f4(int a) { int sum=0; for(int i=1; i<=a; i++) sum += i; return sum; } int main() { f1(); f2(10); printf("%d\n", f3()); printf("%d\n", f4(10)); } | cs |
>> f1 함수는 "Hello world" 를 출력하는 함수
>> f2 함수는 1부터 전달받은 값까지 출력하는 함수
>> f3 함수는 값 하나를 입력한 다음 그 값을 리턴하는 함수
>> f4 함수는 1부터 전달받은 값까지의 합을 리턴하는 함수
4) 함수의 원형(프로토타입) 선언
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 | #include <stdio.h> void f1(void); void f2(int a); int f3(void); int f4(int a); int main() { f1(); f2(10); printf("%d\n", f3()); printf("%d\n", f4(10)); } void f1(void) { printf("Hello world\n"); } void f2(int a) { for(int i=1; i<=a; i++) printf("%d\n", i); } int f3(void) { int k; scanf("%d", &k); return k; } int f4(int a) { int sum=0; for(int i=1; i<=a; i++) sum += i; return sum; } | cs |
>> 이런식으로 함수를 main함수 아래에 적어도 된다.
하지만 이럴경우 함수의 원형을 위에 미리 선언을 해둬야 한다. (뒤에 세미콜론 주의!!)
5) 절대값을 출력하는 함수 vs 절대값을 리턴하는 함수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> int myAbs(int n) { return n > 0 ? n : -n; } void printAbs(int n) { int k = n > 0 ? n : -n; printf("%d\n", k); } int main() { int n; scanf("%d", &n); printAbs(n); printf("%d\n", myAbs(n)); } | cs |
6) 정수를 거꾸로 뒤집는 결과를 리턴하는 함수
ex) 1234 를 입력하면 4321 을 리턴한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <stdio.h> int reverseDigit(int n) { int ret=0; while(n) { ret *= 10; ret += n%10; n /= 10; } return ret; } int main() { int n; scanf("%d", &n); printf("%d\n", reverseDigit(n)); } | cs |
### 재귀함수 ###
- 자기가 자기 자신을 호출 하는 함수
- 탈출조건이 필요하다. 없으면 무한루프.
- 함수는 함수 고유의 기능이 있다. 그 기능을 어떻게 쪼개서 생각할지가 중요하다.
- 점화식을 알고 있으면 그대로 표현하면 된다.
1) fac(n) : n! 을 구하는 함수
1 2 3 4 5 | int fac(int n) { if(n == 0) return 1; return n * fac(n-1); } | cs |
>> n! = n * (n-1)! 이다
>> 0! = 1
2) Sum(n) : 1부터 n까지의 합을 구하는 함수.
1 2 3 4 5 | int Sum(int n) { if(n < 1) return 0; return n + Sum(n-1); } | cs |
>> 1부터 n까지의 합은 1부터 n-1까지의 합에 n을 더하면 된다.
>> 1보다 작은 수가 들어오면 0을 리턴하면 될 것 같다.
3) Pow(a, n) : a의 n승을 구한ㄴ 함수
1 2 3 4 5 | int Pow(int a, int n) { if(n == 0) return 1; return a * Pow(a, n-1); } | cs |
>> a의 n승은 a*(a의 n-1승)과 동일하다.
>> a의 0승은 1..!!
4) print1(n) : 1부터 n까지 출력하는 함수
1 2 3 4 5 6 | void print1(int n) { if(n < 1) return ; print1(n-1); printf("%d\n", n); } | cs |
>> 1부터 n까지 출력하는 것은 1부터 n-1까지 출력한 다음에 n만 출력하는 것과 같다.
5) print2(n) : n부터 1까지 거꾸로 출력하는 함수.
1 2 3 4 5 6 | void print2(int n) { if(n < 1) return ; printf("%d\n", n); print1(n-1); } | cs |
>> n부터 1까지 거꾸려 출력하는 것은 n을 먼저 출력하고 n-1부터 1까지 거꾸로 출력하는 것과 같다.
[5883] 아이폰 9S
[5883] 아이폰 9S : http://boj.kr/5883
- 입력으로 들어오는 수를 체크해 놓고, 큐에 저장.
- 큐에서 꺼낸 다음, 이미 사용한 적이 있으면 continue
- 큐에서 꺼낸 값을 제외하고, 가장 길게 연속하는 수를 세가며 갱신.
<소스코드>
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> int a[1001]; int check[1000001]; int q[1001], f, r; int main() { int n, ans=1; scanf("%d", &n); for(int i=0; i<n; i++) { scanf("%d", a+i); check[a[i]] = 1; q[r++] = a[i]; } while(f != r) { int cnt = 1; int cur = a[0]; int exp = q[f++]; if(!check[exp]) continue; check[exp] = 0; for(int i=1; i<n; i++) { if(a[i] == exp) continue; if(cur == a[i]) cnt++; else { if(ans < cnt) ans = cnt; cur = a[i]; cnt = 1; } } if(ans < cnt) ans = cnt; } printf("%d\n", ans); return 0; } | cs |
Week 08
< 180509 >
1. 구구단 출력하기. (한행에 하나의 단이 출력되도록)
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include <stdio.h> int main() { for(int dan=2; dan<=9; dan++) { printf("%d단 : ", dan); for(int i=1; i<=9; i++) { printf("%d*%d=%2d ", dan, i, dan*i); } printf("\n"); } return 0; } | cs |
>> 실행결과
2단 : 2*1= 2 2*2= 4 2*3= 6 2*4= 8 2*5=10 2*6=12 2*7=14 2*8=16 2*9=18
3단 : 3*1= 3 3*2= 6 3*3= 9 3*4=12 3*5=15 3*6=18 3*7=21 3*8=24 3*9=27
4단 : 4*1= 4 4*2= 8 4*3=12 4*4=16 4*5=20 4*6=24 4*7=28 4*8=32 4*9=36
5단 : 5*1= 5 5*2=10 5*3=15 5*4=20 5*5=25 5*6=30 5*7=35 5*8=40 5*9=45
6단 : 6*1= 6 6*2=12 6*3=18 6*4=24 6*5=30 6*6=36 6*7=42 6*8=48 6*9=54
7단 : 7*1= 7 7*2=14 7*3=21 7*4=28 7*5=35 7*6=42 7*7=49 7*8=56 7*9=63
8단 : 8*1= 8 8*2=16 8*3=24 8*4=32 8*5=40 8*6=48 8*7=56 8*8=64 8*9=72
9단 : 9*1= 9 9*2=18 9*3=27 9*4=36 9*5=45 9*6=54 9*7=63 9*8=72 9*9=81
2. 구구단 출력하기. (한열에 하나의 단이 출력되도록)
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> int main() { for(int i=1; i<=9; i++) { for(int j=2; j<=9; j++) { printf("%d*%d=%2d ", j, i, j*i); } printf("\n"); } return 0; } | cs |
>> 실행결과
2*1= 2 3*1= 3 4*1= 4 5*1= 5 6*1= 6 7*1= 7 8*1= 8 9*1= 9
2*2= 4 3*2= 6 4*2= 8 5*2=10 6*2=12 7*2=14 8*2=16 9*2=18
2*3= 6 3*3= 9 4*3=12 5*3=15 6*3=18 7*3=21 8*3=24 9*3=27
2*4= 8 3*4=12 4*4=16 5*4=20 6*4=24 7*4=28 8*4=32 9*4=36
2*5=10 3*5=15 4*5=20 5*5=25 6*5=30 7*5=35 8*5=40 9*5=45
2*6=12 3*6=18 4*6=24 5*6=30 6*6=36 7*6=42 8*6=48 9*6=54
2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49 8*7=56 9*7=63
2*8=16 3*8=24 4*8=32 5*8=40 6*8=48 7*8=56 8*8=64 9*8=72
2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81
3. 구구단 while 문을 이용해서만 짜보기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <stdio.h> int main() { int dan = 2; while(dan <= 9) { int i=1; while(i<=9) { printf("%d*%d=%2d ", dan, i, dan*i); i++; } printf("\n"); dan++; } return 0; } | cs |
>> 8행에서 i를 다시 1로 만들어줘야 함에 주의하자..!!
>> for문은 초기식 이라는 곳이 있어서 당연하듯이 초기식을 작성하지만, while문은 명시적으로 해줘야함.
4. 별찍기1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <stdio.h> int main() { int i, j, n; scanf("%d", &n); for(i=1; i<=n; i++) { for(j=1; j<=i; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> n 이 5일대의 실행결과
*
**
***
****
*****
>> 첫째줄에 하나, 둘째줄에 두개, 셋째 줄에 세개...
5. 별찍기2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { for(int j=1; j<=n-i+1; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> n이 5일 때 실행결과
*****
****
***
**
*
6. 별찍기 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { for(int j=1; j<=n-i+1; j++) printf("*"); for(int j=1; j<i; j++) printf("@"); printf("\n"); } return 0; } | cs |
>> n이 5일 때 실행결과
*****
****@
***@@
**@@@
*@@@@
7. 별찍기4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { for(int j=1; j<=n-i; j++) printf(" "); for(int j=1; j<=i; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> n이 5일 때 실행결과
*
**
***
****
*****
.
>> 첫째줄에 공백 n-1개, 별 한개, 둘째줄에 공백 n-2개, 별 두개 ...
8. 별찍기 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { for(int j=1; j<=n-i; j++) printf(" "); for(int j=1; j<=(i*2)-1; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> n이 4일 때 실행결과
*
***
*****
*******
9. 별찍기 6
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> int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { for(int j=1; j<=n-i; j++) printf(" "); for(int j=1; j<=(i*2)-1; j++) printf("*"); printf("\n"); } for(int i=n-1; i>=1; i--) { for(int j=n-1; j>=i; j--) printf(" "); for(int j=1; j<=(i*2)-1; j++) printf("*"); printf("\n"); } return 0; } | cs |
>> n이 4일 때 실행결과
*
***
*****
*******
*****
***
*
Week 5-2 : infix to postfix, exp(postfix)
< 180508 >
1) 후위식의 계산
- 피연산자를 만나면 push
- 연산자를 만나면 스택에 담겨있는 두개의 피 연산자를 꺼낸 다음(pop) 연산 후 다시 push
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 | int exp(const char *eq) { int i; Stack s; init(&s); for(i=0; eq[i]; i++) { if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0'); else { int op2 = pop(&s); int op1 = pop(&s); switch(eq[i]) { case '+': push(&s, op1+op2); break; case '-': push(&s, op1-op2); break; case '*': push(&s, op1*op2); break; case '/': push(&s, op1/op2); break; } } } return peek(&s); } int main() { printf("%d\n", exp("234*+")); // 14 printf("%d\n", exp("82/3-32*+")); // 7 return 0; } | cs |
>> 10 : 오른쪽 피연산자가 먼저 꺼내짐에 주의.
>> 7 : 문자열의 끝은 널문자인데, 널문자의 아스키코드값은 0. 0은 조건식에서 거짓. 즉 널물자를 만나면 for 문을 탈출한다.
2) 중위식을 후위식으로.
- 연산자 우선순위
>> *, / : 제일 크다.
>> +, - : 두번째
>> ( : 제일 작다.
- 규칙
>> 피연산자를 만나면 그대로 출력
>> 연산자를 만나면 스택에 push.
>> 스택 위에 있는 연산자의 우선순위가 새로 추가되는 연산자의 우선순위보다 높거나 같다면 꺼내서 출력.
우선순위가 낮은 연산자를 만날 때 까지 반복 후 해당 연산자 push.
>> ( 가중치에 상관없이 스택에 쌓는다.
>> ) 가 나오면 스택에서 ( 위에 쌓여 있는 모든 연산자를 출력. 그리고 ( 는 꺼내서 버린다.
- 빠르게 계산하기.
>> 후위식을 계산하는 방식에서 연산자 앞에는 두개의 피연산자가 있어야 하는 원리를 이용.
a / (b-c+d) * (e-a) * c 에서 밑줄 친 수식들이 먼저 계산이 될 것이다.
a(_____)/ 가 될 것이며, 이 결과를 A 라고 하자. ______ 은 나중에 계산.
그렇다면 처음의 식은 A * (e-a) * c 가 되는데, 역시 여기서도 밑줄 친 수식들이 먼저 계산이 될 것이다.
A(___)* 가 될 것이며 이 결과를 B 라고 하자.
그럼 맨 처음 식은 B * c 가 되며 이것은 후위식으로 바꾸면 Bc* 가 될 것이다.
B를 풀어쓰면 A(___)*c* 가 되고,
A를 풀어쓰면 a(_____)/(___)*c* 이 된다.
이제 나중에 계산하기로 한 b-c+d 를 생각해보자. 생각할 필요도 없다. bc-d+ 이다.
그럼 위의 식은 abc-d+/(___)*c* 가 되고,
아직 계산하지 않은 나머지인 e-a 는 ea- 가 된다.
최종적으로 abc-d+/ea-*c* 이 된다.
Ex2) a + (b-c+d) * (e-a) * c 를 생각해보자.
a + (b-c+d) * (e-a) * c 에서는 a 와 밑줄친 식의 결과를 더하는 연산이 진행되어야 한다.
a(_____________)+ 의 형태가 나온 것이다.
(b-c+d) * (e-a) * c 에서는 역시 밑줄친 수식이 먼저 계산이 될 것이기 때문에
(__________)c* 라고 쓸 수 있다.
두 식을 결합하면 a(_____________)c*+ 이 되고,
(b-c+d) * (e-a) 에서 b-c+d 의 결과를 A, e-a 의 결과를 B라고 하면 후위식으로 AB* 가 될 것이다.
역시 위의 식을 다시 결합하면 aAB*c*+ 가 되고,
A를 풀어쓰면 bc-d+, B를 풀어쓰면 ea- 가 된다.
대입하면 최종적으로 abc-d+ea-*c*+ 가 된다.
<숙제>
- 중위식을 후위식으로 바꾸는 프로그래밍.
- 중위식을 후위식으로 바꾼 다음 그 후위식을 계산하는 프로그래밍.
'Tutoring > 18-1 DS' 카테고리의 다른 글
| 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-1 : Circular Doubly Linked List / Stack ADT (0) | 2018.05.08 |
| Week 4-2 : Circular Linked List (0) | 2018.04.20 |
| Week 4-1 : Linked List (0) | 2018.04.18 |
