Week 4 - BFS
<180324>
Week4 - BFS
[1260] DFS와 BFS
[1012] 유기농 배추
[2178] 미로탐색 (http://boj.kr/2178)
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 <cstdio> #include <queue> using namespace std; struct P { int r, c; }; int r, c; int g[102][102]; int dr[] = {1, 0, -1, 0}; int dc[] = {0, 1, 0, -1}; int main() { scanf("%d%d", &r, &c); for(int i=1; i<=r; i++) for(int j=1; j<=c; j++) scanf("%1d", &g[i][j]); queue<P> q; q.push((P){1, 1}); while(!q.empty()) { int curR = q.front().r; int curC = q.front().c; q.pop(); for(int k=0; k<4; k++) { int nr = curR + dr[k]; int nc = curC + dc[k]; if(g[nr][nc] == 1) { q.push((P){nr, nc}); g[nr][nc] = g[curR][curC]+1; } } } printf("%d\n", g[r][c]); } | cs |
>> input data 특성상 visited[r][c] 배열을 만들 필요가 없다.
>> 32 라인이 이 문제의 핵심인 것 같다.
>> 21, 31 : 구조체 변수의 경우 저런식으로 캐스팅 해서 바로 넣을 수 있다.
[2644] 촌수계산 (http://boj.kr/2644)
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, m; int s, e; scanf("%d%d%d%d", &n, &s, &e, &m); vector<int> v[101]; while(m--) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } queue<int> q; q.push(s); int visited[101]={0}; visited[s] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); if(cur == e) break; for(int i=0; i<v[cur].size(); i++) { int next = v[cur][i]; if(!visited[next]) { visited[next] = visited[cur]+1; q.push(next); } } } printf("%d\n", visited[e]-1); } | cs |
>> 알고리즘은 위 문제와 다를게 없음.
- 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 | #include <stdio.h> int n, a, b, m, g[101], ck[101], ans; int getPidx(int idx) { if(idx == g[idx]) return idx; return getPidx(g[idx]); } int main() { int i, x, y, p; scanf("%d %d %d %d", &n, &a, &b, &m); for(i=1; i<=n; i++) g[i] = i; while(m--) { scanf("%d %d", &x, &y); g[y] = x; } x = getPidx(a); y = getPidx(b); if(x != y) puts("-1"); else { p = a; ck[a] = 1; do { p = g[p]; ck[p] = 1; } while(p != x); p = b; while(!ck[p]) { p = g[p]; } while(p != a) { ans++; a = g[a]; } while(p != b) { ans++; b = g[b]; } printf("%d\n", ans); } return 0; } | cs |
>> 2년전에는 위와 같이 풀었다. 공통 조상이 같으면 촌수를 구할 수 있고, 그렇지 않으면 불가능.
>> ...
[7562] 나이트의 이동 (http://boj.kr/7562)
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 | #include <cstdio> #include <queue> using namespace std; struct P { int i, j; }; int n; int di[]={1, 1, 2, 2, -1, -1, -2, -2}; int dj[]={2, -2, 1, -1, 2, -2, 1, -1}; bool safe(int i, int j) { return (0 <= i && i < n) && (0 <= j && j < n); } int main() { int tc; scanf("%d", &tc); while(tc--) { int curI, curJ; int tI, tJ; int visited[305][305]={0}; scanf("%d%d%d%d%d", &n, &curI, &curJ, &tI, &tJ); queue<P> q; q.push((P){curI, curJ}); visited[curI][curJ] = 1; while(!q.empty()) { curI = q.front().i; curJ = q.front().j; q.pop(); if(curI == tI && curJ == tJ) break; for(int k=0; k<8; k++) { int ni = curI+di[k]; int nj = curJ+dj[k]; if(safe(ni, nj) && !visited[ni][nj]) { q.push((P){ni, nj}); visited[ni][nj] = visited[curI][curJ]+1; } } } printf("%d\n", visited[tI][tJ]-1); } } | cs |
>> 알고리즘은 미로탐색과 일치한다. 탐색 방범만 조금 다를뿐.
[1697] 숨박꼭질 (http://boj.kr/1697)
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; bool safe(int k) { return (0 <= k && k <= 100000); } int main() { int n, k; scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[100001]={0}; visited[n] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); if(cur == k) break; int next = cur+1; if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } next = cur-1; if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } next = cur*2; if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } } printf("%d\n", visited[k]-1); } | cs |
>> 동일한 알고리즘이다.
'Tutoring > PS' 카테고리의 다른 글
| Week 6 - BFS (숨박꼭질) (0) | 2018.03.30 |
|---|---|
| Week 5 - BFS (0) | 2018.03.24 |
| Week3 - DFS (0) | 2018.03.07 |
| Week 2 - DFS (0) | 2018.02.21 |
| Week 1 - DFS (0) | 2018.02.20 |
<180310> 삼성 S/W 테스트 A형 후기(합격)
- 완탐 with DFS 유형의 문제인 것 같다.
- n제한은 작았다.
- 시간에 따라 좌표에 들어있는 값이 바뀌는게 독특했다.
RIGHT = 1
DOWN = 2
LEFT = 3
UP = 4
>> 4시간 주기라 모델 4가지를 모두 만들어 3차원 배열을 만들어 컨트롤 했다. int g[4][10][10];
>> void dfs(int y, int x, int ey, int ex, int time, int pos);
- 좌표가... 2차원 배열 기준 (2, 1)의 좌표를 (1, 2) 라고 표기가 되어있다. (이런 함정 제일 짜증난다...ㅜㅜ)
>> (x, y) 에서 y, x값만 바꾸면 되는데, 배열에 들어갈 값을 통채로 바꿔서 처리할려고 하느라 시간을 많이 썻다.
- 문제 특성상 테케만 다 맞아도 틀릴수가 없는 문제라고 생각되었다.
>> 근데 테케를 자꾸 통과하지 못하고 있었다.........
- 아무리 봐도 오류가 없어보이는데, 직접 테스트 할 수 없는 테케 4개의 정답이 틀리게 나온다....
- 시간은 흘러만 가고, 자괴감이 들기 시작했지만, 아직 시간이 많이 남아서 침착하게 뇌컴파일을 하고 있었다.(디버깅 할줄 모른다. 재귀함수라 별 의미도 없어 보인다..)
- 종료 20분전 예외처리를 잘못한 것을 찾아서..!! 고쳤더니 테케가 다 맞게 나왔다.
>> 단순히 해당 상태에 해당 좌표를 방문했을 경우 더이상 방문하지 않게 했었는데,
해당 상태에 대한 좌표를 현재 시간보다 빨리 방문했었다면, 볼필요가 없는 것으로(종료조건) 변경 하였다.
- 제자리 있는 경우도 처리를 해야하므로 가지 치기 필수..!!
>> if(ans < time) return ;
>> 잠정적 으로 정해진 답보다 현재 진행 시간이 크면 볼 필요가 없기 때문..!!
- 테케가 맞게 나오고 난 다음 여유가 좀 생겼던것 같다. 화장실도 다녀옴.
- 테케들의 특성을 잘 살펴보니 절대값의 차이가 2인 칸에 대해서만 이동을 할 수 있었던 것 같았다.
- 최근에 후배들 ps 입문시키느라 못풀면 어쩌지 하는 걱정이 산더미 같았는데, 이젠 맘놓고 결과만 기다리면 될 것 같다.
>> 진짜 시험은 B 형부터..ㅜ
- 또한 최근 후배들에게 dfs를 알려주고 있어서 그런지, dfs 에 대한 감만 있어 당연하게 dfs 로 풀었는데,
끝나고 버스타고 가면서 문제푼 학생들이 하는 얘기를 들어보면 bfs 도 많이 활용했던 것 같다.
안될 건 없겠지만, 좌표값, 상태값, 그 상태에 대한 좌표를 몇번만에 왔는지, 이러한 정보를 큐에 담아야 하지 않을까란 생각이 들었다.
>> 3/16 합격 확인..!! 이제부터가 진짜..!!
'Etc.' 카테고리의 다른 글
| <181020> LG CNS CODE MONSTER 2018 본선 후기(Off-line TEST) (0) | 2018.10.20 |
|---|---|
| <180518> 배민 코테 1차 (0) | 2018.05.19 |
| [교양] 링크 소프트웨어 세상 (Link Software) (0) | 2018.03.22 |
<3-4> __name__, 리스트 슬라이싱
동영상 강좌 : http://pythonkim.tistory.com/notice/77
# Day_03_05_slicing.py
- 다른 파일의 어떤 내용을 사용하고 싶을 때.
1 | import Day_03_05_import | cs |
>> Day_02_02_list.py 파일을 불러오기. (.py 는 생략)
>> 위 파일에서 선언한 변수, 함수를 모두 사용할 수 있다. 해당 파일의 내용을 복붙한것과 같은 효과..!!
>> 하지만 우리는 makeRandoms() 의 사용만 원한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | import random def makeRandoms(): a = [] for i in range(10): a.append(random.randrange(100)) return a s = "unused" def a(): pass def b(): pass def c(): pass | cs |
>> 우리가 불러올 파일이 이런식으로 구성되어 있다고 가정하자.
>> makeRandoms() 함수만을 가져다 쓰고 싶다.
>> 하지만 위와 같이 해당 파일을 통채로 import 하면 복붙의 효과이기 때문에
변수 s, a(), b(), c() 도 가져오게 된다.
- 원하지 않는 내용들을 블럭지정 후 Edit - Indent Selection 을 통해 블럭 내용들을 한번에 탭키 처리 한다.
- 그리고 이것들을 사용하지 않기 위해 아래의 1번 라인을 추가 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | if __name__ == '__main__': s = "unused" def a(): pass def b(): pass def c(): pass | cs |
>> 파이썬에는 main() 가 존재하지 않는다. 그래서 이를 흉내낼 필요가 있다.
>> 위와 같이 여러개의 파일이 같이 사용될 때 특히..!!
>> 그것을 흉내내는 변수가 __name__ 이다.
### __main__ 은 첫번째 실행되는 파일을 의미한다.
### __name__ : 파일별로 존재하는 파일 이름
- 현재 파일에 print(__name__) 을 추가하고, import 한 파일에도 print(__name__) 을 추가한 다음 내용을 확인해보자.
1 2 3 | import Day_03_05_import print(__name__) | cs |
>> 실행결과
1 2 | Day_03_05_import : Day_03_05_import __main__ | cs |
>> 1 : import 한 파일에서 실행된 print(__name__)
>> 2 : 현재 파일에서 실행된 print(__name__), 즉 첫 번째로 실행된 파일이다.
- import 한 파일의 함수 사용하기
1 2 3 | Day_03_05_import.random.seed(1) a = Day_03_05_import.makeRandoms() print(a) # [17, 72, 97, 8, 32, 15, 63, 97, 57, 60] | cs |
- 슬라이싱
1 | print(a[0:5]) # [17, 72, 97, 8, 32] | cs |
>> [0, 5) 까지의 데이터들을 의미한다.
>> : 을 이용한 문법을 슬라이싱 이라고 한다.
# 문제
# 뒤쪽 절반 출력하기.
1 | print(a[len(a)//2:]) | cs |
>> print(a[len(a)//2:len(a)]) 도 가능하다.
- 생략
1 | print(a[:]) # [17, 72, 97, 8, 32, 15, 63, 97, 57, 60] | cs |
>> 이런식으로 생략이 가능하다.
>> : 앞의 생략은 맨 앞부터, : 뒤의 생략은 맨 마지막 까지를 의미한다.
- 슬라이싱을 range() 처럼 사용할 수 있다.
1 2 | print(a[::2]) # [17, 97, 32, 63, 57] print(a[::3]) # [17, 8, 63, 60] | cs |
>> 1 : 2칸씩 건너뛴 요소
>> 2 : 3칸씩 건너뛴 요소
- 홀수번째, 짝수번째 요소 출력하기
1 2 3 4 5 | # 짝수번째 요소만 출력 print(a[::2]) # [17, 97, 32, 63, 57] # 홀수번째 요소만 출력 print(a[1::2]) # [72, 8, 15, 97, 60] | cs |
>> 5 : 1번째 요소부터 2칸씩 건너뛰기..!!
- 거꾸로 출력하기
1 | print(a[::-1]) # [60, 57, 97, 63, 15, 32, 8, 97, 72, 17] | cs |
-
1 2 3 4 5 | print(a[len(a)-1:0:-1]) # [60, 57, 97, 63, 15, 32, 8, 97, 72] print(a[len(a)-1:-1:-1]) # [] print(a[-1:-1:-1]) # [] | cs |
>> 1 : 마지막 요소만 제외하고 출력이 된다.
>> 3, 5 라인은 같은 코드이다.
- 거꾸로 홀수번째, 짝수번째 요소만 출력하기
1 2 3 4 | # 거꾸로 홀수번째 요소만 출력하기 print(a[:]) # [17, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(a[::-2]) # [60, 97, 15, 8, 72] print(a[-2::-2]) # [57, 63, 32, 97, 17] | cs |
- 얕은복사 review
1 2 3 4 5 6 7 | b = a c = a a[0] = -1 print(a) # [-1, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(b) # [-1, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(c) # [-1, 72, 97, 8, 32, 15, 63, 97, 57, 60] | cs |
>> a[0] 를 변경했는데, b와 c도 변경됨
- 깊은복사 review
1 2 3 4 5 6 7 8 9 10 11 12 | b = a c = a d = a.copy() e = a[:] a[0] = -1 print(a) # [-1, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(b) # [-1, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(c) # [-1, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(d) # [17, 72, 97, 8, 32, 15, 63, 97, 57, 60] print(e) # [17, 72, 97, 8, 32, 15, 63, 97, 57, 60] | cs |
>> 3 : 이전에 공부한 깊은복사 방법
>> 4 : 슬라이싱을 이용한 깊은복사 // 슬라이싱은 안쪽에 있는 것을 뽑아내는 과정이기 때문에 항상 복사본을 만든다.
- 짝수번째 요소 출력하기
1 2 3 4 5 6 7 | for i in range(0, len(a), 2): print(a[i], end=' ') # -1 97 32 63 57 print() for i in a[::2]: print(i, end=' ') # -1 97 32 63 57 print() | cs |
>> 예전에는 1-3과 같이 하였으나, 이젠 5-7과 같이 하면 된다.
'Language > Python' 카테고리의 다른 글
| <3-3> JSON (0) | 2018.03.05 |
|---|---|
| <3-2> Set 과 Dictionary (0) | 2018.03.02 |
| <3-1> 파일 입출력 (0) | 2018.02.23 |
| <2-3> 기상청의 전국 날씨정보 파싱, 외부 모듈 추가 (0) | 2018.02.22 |
| <2-2> 리스트, 튜플 (0) | 2018.02.15 |
Week3 - DFS
<180310>
Week3 - DFS
[1743] 음식물 피하기 (http://boj.kr/1732)
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 | #include <stdio.h> int n, m; int g[101][101]; int dr[]={1, 0, -1, 0}; int dc[]={0, 1, 0, -1}; int safe(int a, int b) { return (0 < a && a <= n) && (0 < b && b <= m); } int max(int a, int b) { return a > b ? a : b; } int dfs(int r, int c) { int k, ret=1; g[r][c] = 0; for(k=0; k<4; k++) { int nr = r+dr[k]; int nc = c+dc[k]; if(safe(nr, nc) && g[nr][nc]) ret += dfs(nr, nc); } return ret; } int main() { int i, j, k; int ans=0; scanf("%d%d%d", &n, &m, &k); while(k--) { int a, b; scanf("%d%d", &a, &b); g[a][b] = 1; } for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { if(g[i][j]) { ans = max(ans, dfs(i, j)); } } } printf("%d\n", ans); return 0; } | cs |
[2468] 안전영역 (http://boj.kr/2468)
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 | #include <stdio.h> int n; int g[101][101]; int visited[101][101]; int di[]={0, 1, 0, -1}; int dj[]={1, 0, -1, 0}; int safe(int i, int j) { return (0 <= i && i < n) && (0 <= j && j < n); } void dfs(int i, int j, int k) { visited[i][j] = k; for(int a=0; a<4; a++) { int ni = i+di[a]; int nj = j+dj[a]; if(safe(ni, nj) && g[ni][nj] >= k && visited[ni][nj] != k) dfs(ni, nj, k); } } int main() { int i, j, k; int max=1, min=100; int ans=0; scanf("%d", &n); for(i=0; i<n; i++) { for(j=0; j<n; j++) { scanf("%d", &k); if(max < k) max = k; if(min > k) min = k; g[i][j] = k; } } for(k=min; k<=max; k++) { int tmp=0; for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(g[i][j] >= k && visited[i][j] != k) { tmp++; dfs(i, j, k); } } } if(ans < tmp) ans = tmp; } printf("%d\n", ans); return 0; } | cs |
>> 42 라인에서 k<max 로 해서 한번 틀렸음.
이렇게 할 경우
2
1 1
1 1
의 테케의 정답은 1인데 0이나옴.
2) 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 | #include <stdio.h> int n, ans, g[100][100], ck[100][100]; int safe(int x, int y) { return (0 <= x && x < n) && (0 <= y && y < n); } void dfs(int y, int x, int k) { int i, xx, yy, dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1}; ck[y][x] = 1; for(i=0; i<4; i++) { xx = x+dx[i]; yy = y+dy[i]; if(safe(xx, yy) && g[yy][xx] > k && !ck[yy][xx]) dfs(yy, xx, k); } } int main() { int i, j, k, max=0; scanf("%d", &n); for(i=0; i<n; i++) { for(j=0; j<n; j++) { scanf("%d", &g[i][j]); if(g[i][j] > max) max = g[i][j]; } } for(k=0; k<max; k++) { int cnt=0; for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(g[i][j] > k && !ck[i][j]) { dfs(i, j, k); cnt++; } } } if(ans < cnt) ans = cnt; for(i=0; i<n; i++) for(j=0; j<n; j++) ck[i][j] = 0; } printf("%d\n", ans); return 0; } | cs |
>> 거의 비슷하게 푼것 같다.
[11403] 경로찾기 (http://boj.kr/11403)
1) DFS 풀이
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> int n, g[101][101]; int visited[101]; int ans[101][101]; int dfs(int s, int e) { int ret=0; visited[s] = 1; for(int i=0; i<n; i++) { if(g[s][i]) { if(i == e) return 1; if(!visited[i]) ret = dfs(i, e); if(ret) return 1; } } return ret; } int main() { scanf("%d", &n); for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d", &g[i][j]); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { ans[i][j] = dfs(i, j); for(int k=0; k<n; k++) visited[k] = 0; } } for(int i=0; i<n; i++) { for(int j=0; j<n; j++) printf("%d ", ans[i][j]); puts(""); } return 0; } | cs |
>> dfs(i, j) : i 에서 j로 가는 길이 있는지 알려주는 함수.
>> 13, 14 : s 에서 i로 가는 길이 있는데, i가 e 라면, s에서 e로 가는 길이 있다는 뜻!!
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 | #include <stdio.h> int g[101][101]; int main() { int i, j, k, n; scanf("%d", &n); for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d", &g[i][j]); for(k=0; k<n; k++) for(i=0; i<n; i++) for(j=0; j<n; j++) if(g[i][k] && g[k][j]) g[i][j] = 1; for(i=0; i<n; i++) { for(j=0; j<n; j++) printf("%d ", g[i][j]); puts(""); } return 0; } | cs |
>> 플로이드 와샬 풀이가 좀더 직관적이긴 하다. 코드도 심플하고.
>> 하지만 DFS 로 풀수 있다고 해서 과제로 내주었다...얘들아 미안..ㅎㅎ
>> 18, 19 : i 에서 k로 가는 길이 있는데, k에서 j로 가는 길이 있으면 i 에서 j로 가는 길이 있다..!!
[9466] 텀 프로젝트
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> int ans; int p[100001]; int visited[100001], finished[100001]; void dfs(int s) { int next = p[s]; visited[s] = 1; if(!visited[next]) dfs(next); else { if(!finished[next]) { for(int i=next; !finished[i]; i=p[i]) { finished[i] = 1; ans++; } } } finished[s] = 1; } int main() { int tc; scanf("%d", &tc); while(tc--) { int n, k; scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d", &k); p[i] = k; visited[i] = finished[i] = 0; } ans = 0; for(int i=1; i<=n; i++) if(!visited[i]) dfs(i); printf("%d\n", n-ans); } return 0; } | cs |
>> 예전에 엄청 고통 받았던 문제..
>> 여전히 고통스럽다.
>> 결국 라이님의 블로그 설명을 보고 해결했었다. (https://kks227.blog.me/221028710658)
>> 사이클에 대한 처리를 배열하나를 더 만들어서 해야한다.
>> visited[next] = finished[next] = 0 : 아직 방문하지 않은 정점
>> visited[next] = 1 && finished[next] = 0 : 현재 정점과 next가 하나의 싸이클에 속함.
>> visited[next] = finished[next] = 1 : 이미 모든 탐색이 끝난 정점. 현재 정점은 next 가 그 싸이클 안에 있건 없건 절대 그 싸이클 안에 있을 수 없음.
[1707] 이분 그래프 (http://boj.kr/1707)
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 | #include <cstdio> #include <vector> using namespace std; int ans; void isBinaryGraph(vector<int> g[], vector<int> &visited, int s, int ck) { visited[s] = ck%2+1; for(int i=0; i<g[s].size() && ans; i++) { int next = g[s][i]; if(!visited[next]) { isBinaryGraph(g, visited, next, ck+1); } else { if(visited[s] == visited[next]) { ans = 0; return ; } } } } int main() { int tc; scanf("%d", &tc); while(tc--) { int v, e; scanf("%d%d", &v, &e); vector<int> g[20001]; vector<int> visited(v+1, 0); while(e--) { int a, b; scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); } ans = 1; for(int i=1; i<=v; i++) { if(!visited[i] && ans) isBinaryGraph(g, visited, i, 0); } ans ? puts("YES") : puts("NO"); } } | cs |
>> 방문체크를 1과 2로 처리하였다.
>> 다음에 방문할 정점이 이미 방문을 한 정점인데, 같은 번호로 방문체크가 되어 있으면 이분그래프가 아니다.
>> 46 : 컴퍼넌트는 여러개일 수 있다..
'Tutoring > PS' 카테고리의 다른 글
| Week 6 - BFS (숨박꼭질) (0) | 2018.03.30 |
|---|---|
| Week 5 - BFS (0) | 2018.03.24 |
| Week 4 - BFS (0) | 2018.03.11 |
| Week 2 - DFS (0) | 2018.02.21 |
| Week 1 - DFS (0) | 2018.02.20 |
printf() 서식문자 %g
- 실수형 값을 출력할 때, printf() 함수에서 서식문자를 %lf 혹은 %f 로 준다고 배었고,
기본적으로 소숫점 아래 6자리로 알고 있다. 소수점을 조정하려면 10 번 라인처럼 해야하는데,
%g 라는 서식문자를 사용하면 그럴 필요가 없다...!!!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <stdio.h> int main() { double f=3.14; printf("%lf\n", f); // 3.140000 printf("%.2lf\n", f); // 3.14 printf("%g\n", f); // 3.14 return 0; } | cs |
'Language > C' 카테고리의 다른 글
| 비트 연산을 이용한 정수의 산술연산 (분석은 아직..) (0) | 2018.06.04 |
|---|---|
| scanf() 에서 공백을 포함한 문자열 입력받기 (0) | 2018.04.05 |
| 배열에서 배열의 크기 이상의 인덱스를 사용하게 되면... (0) | 2018.02.27 |
[14890] 경사로
[14890] 경사로 (http://boj.kr/14890)
right() 에서 L = 2 인경우
3 2 2 2 3
3 2 2 1 1
x x 3 2 2 (마지막 위치)
2 2 3
3 3 3
위 경우에 대해서 잘 처리해주면 된다. down() 도 마찬가지.
< 소스코드 >
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 | #include <stdio.h> int N, L, ans=0; int g[101][101]; int down(int r, int c) { int curH; if(r == N-1) return 1; curH = g[r][c]; if(r+L < N && curH-g[r+L][c] == 1) { int flag = 1; for(int i=1; i<L; i++) { if(g[r+L][c] != g[r+i][c]) flag = 0; } if(flag){ if(r+L == N-1) return 1; if(g[r+L][c] == g[r+L+1][c]) return down(r+L+1, c); if(g[r+L][c] == g[r+L+1][c]+1) return down(r+L, c); } } if(r+L < N && g[r+L][c]-curH == 1) { int flag = 1; for(int i=1; i<L; i++) { if(curH != g[r+i][c]) flag = 0; } if(flag) return down(r+L, c); } if(g[r+1][c] == curH) return down(r+1, c); return 0; } int right(int r, int c) { int curH; if(c == N-1) return 1; curH = g[r][c]; if(c+L < N && g[r][c+L]-curH == 1) { int flag = 1; for(int i=1; i<L; i++) { if(curH != g[r][c+i]) flag = 0; } if(flag) return right(r, c+L); } if(c+L < N && curH-g[r][c+L] == 1) { int flag = 1; for(int i=1; i<L; i++) { if(g[r][c+L] != g[r][c+i]) flag = 0; } if(flag) { if(c+L == N-1) return 1; if(g[r][c+L] == g[r][c+L+1]) return right(r, c+L+1); if(g[r][c+L] == g[r][c+L+1]+1) return right(r, c+L); } } if(g[r][c+1] == curH) return right(r, c+1); return 0; } int main() { scanf("%d%d", &N, &L); for(int i=0; i<N; i++) for(int j=0; j<N; j++) scanf("%d", &g[i][j]); for(int i=0; i<N; i++) { if(down(0, i)) ans++; if(right(i, 0)) ans++; } printf("%d\n", ans); return 0; } | cs |
>> 깔끔하게 경우의 수를 펜으로 써가며 확인했으면 금방 했을텐데, 괜히 머릿속으로 한다고 하다가, 시간만 많이 썼다...
'BOJ > SWEA' 카테고리의 다른 글
| [14889] 스타트와 링크 (0) | 2018.02.28 |
|---|---|
| [14888] 연산자 끼워넣기 (0) | 2018.02.27 |
보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.
<3-3> JSON
동영상 강의 : http://pythonkim.tistory.com/notice/77
# Day_03_03_json.py
- 파이선에서는 json 모듈이 있다.
1 | import json | cs |
http://www.jsontest.com 에 접속해보자
- JSON : JavaScript Object Notation 의 약자.
>> Object 를 문자열로 변환하고, 그 문자열을 다시 Object 로 복원하는 방법.
-
1 | j1 = '{"ip": "8.8.8.8"}' |
>> dictionary 를 포장하고 있는 문자열.
>> 우리는 이것을 dictionary 로 변환할 수 있다. dictionary 가 들어있기 때문..!!
-
1 2 3 4 5 6 7 | import json j1 = '{"ip": "8.8.8.8"}' d1 = json.loads(j1) print(d1) # {'ip': '8.8.8.8'} print(type(d1)) # <class 'dict'> print(d1['ip']) # 8.8.8.8 | cs |
>> 4 : json.loads() 를 통해 json 형태의 문자열을 읽어올 수 있다.
>> json.load() 는 파일로부터 읽어올 때 사용한다.
# 문제
# j2를 해석해서 value 를 출력하기
1 2 3 4 5 6 7 8 9 10 11 12 | j2 = '''{ "Accept-Language": "en-US,en;q=0.8", "Host": "headers.jsontest.com", "Accept-Charset": "ISO-8859-1,utf-8;q=0.7,*;q=0.3", "Accept": "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8" }''' d2 = json.loads(j2) print(type(d2)) # <class 'dict'> for k, v in d2.items(): print(k, v) | cs |
>> 실행결과
1 2 3 4 | Accept-Language en-US,en;q=0.8 Host headers.jsontest.com Accept-Charset ISO-8859-1,utf-8;q=0.7,*;q=0.3 Accept text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8 | cs |
- json.dumps()
1 2 3 | j3 = json.dumps(d2) print(type(j3)) print(j3) | cs |
>> 실행결과
1 2 | <class 'str'> {"Accept-Language": "en-US,en;q=0.8", "Host": "headers.jsontest.com", "Accept-Charset": "ISO-8859-1,utf-8;q=0.7,*;q=0.3", "Accept": "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8"} | cs |
>> object 를 str 로 변환한다.
- 이전에 만든 kma.csv 파일을 열어보자. (기본적으로 엑셀과 연동이 된다.)
>> 인코딩 문제로 글자가 깨지는 경우
1 | f = open('Data/kma.cvs', 'w', encoding='utf-8') | cs |
>> 여기에서 인코딩을 지우면 된다고 하는데, 맥에서는 안된다...
...
# Day_03_04_json_kma.py
-
1 2 3 4 5 6 7 8 9 10 | import json import requests url = 'http://www.kma.go.kr/DFSROOT/POINT/DATA/top.json.txt' recvd = requests.get(url) print(recvd.text) text = bytes(recvd.text, 'iso-8859-1').decode('utf-8') print(text) | cs |
>> 실행결과
1 2 | [{"code":"11","value":"ìì¸í¹ë³ì"},{"code":"26","value":"ë¶ì°ê´ìì"},{"code":"27","value":"ë구ê´ìì"},{"code":"28","value":"ì¸ì²ê´ìì"},{"code":"29","value":"ê´ì£¼ê´ìì"},{"code":"30","value":"ëì ê´ìì"},{"code":"31","value":"ì¸ì°ê´ìì"},{"code":"41","value":"경기ë"},{"code":"42","value":"ê°ìë"},{"code":"43","value":"충ì²ë¶ë"},{"code":"44","value":"충ì²ë¨ë"},{"code":"45","value":"ì ë¼ë¶ë"},{"code":"46","value":"ì ë¼ë¨ë"},{"code":"47","value":"ê²½ìë¶ë"},{"code":"48","value":"ê²½ìë¨ë"},{"code":"50","value":"ì 주í¹ë³ìì¹ë"}] [{"code":"11","value":"서울특별시"},{"code":"26","value":"부산광역시"},{"code":"27","value":"대구광역시"},{"code":"28","value":"인천광역시"},{"code":"29","value":"광주광역시"},{"code":"30","value":"대전광역시"},{"code":"31","value":"울산광역시"},{"code":"41","value":"경기도"},{"code":"42","value":"강원도"},{"code":"43","value":"충청북도"},{"code":"44","value":"충청남도"},{"code":"45","value":"전라북도"},{"code":"46","value":"전라남도"},{"code":"47","value":"경상북도"},{"code":"48","value":"경상남도"},{"code":"50","value":"제주특별자치도"}] | cs |
>> text 데이터는 딕셔너리 리스트의 형태이다..!!
>> 인코딩이 깨지는 것에 대한 해결책은 9번 라인으로 해결.
>> 4 라인의 url 을 브라우저에서 직접 실행시 json 형식의 내용을 그대로 확인할 수 있다. (맥에서는 여전히 깨져서 나온다..ㅜ)
< JSON 에서의 기본 규칙 >
- 맨 처음 나오는 것은 최상위 객체로 배열(파이썬에서는 리스트) 아니면 사전의 형태.
- int 값을 json 으로 전달할 수 없다.
# 문제
# 코드와 도시 이름만 출력해 보기.
1 2 3 4 5 6 | items = json.loads(text) print(items) print(type(items)) # <class 'list'> for item in items: print(item['code'], item['value']) | cs |
>> 실행결과
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | [{'code': '11', 'value': '서울특별시'}, {'code': '26', 'value': '부산광역시'}, {'code': '27', 'value': '대구광역시'}, {'code': '28', 'value': '인천광역시'}, {'code': '29', 'value': '광주광역시'}, {'code': '30', 'value': '대전광역시'}, {'code': '31', 'value': '울산광역시'}, {'code': '41', 'value': '경기도'}, {'code': '42', 'value': '강원도'}, {'code': '43', 'value': '충청북도'}, {'code': '44', 'value': '충청남도'}, {'code': '45', 'value': '전라북도'}, {'code': '46', 'value': '전라남도'}, {'code': '47', 'value': '경상북도'}, {'code': '48', 'value': '경상남도'}, {'code': '50', 'value': '제주특별자치도'}] <class 'list'> 11 서울특별시 26 부산광역시 27 대구광역시 28 인천광역시 29 광주광역시 30 대전광역시 31 울산광역시 41 경기도 42 강원도 43 충청북도 44 충청남도 45 전라북도 46 전라남도 47 경상북도 48 경상남도 50 제주특별자치도 | cs |
'Language > Python' 카테고리의 다른 글
| <3-4> __name__, 리스트 슬라이싱 (0) | 2018.03.08 |
|---|---|
| <3-2> Set 과 Dictionary (0) | 2018.03.02 |
| <3-1> 파일 입출력 (0) | 2018.02.23 |
| <2-3> 기상청의 전국 날씨정보 파싱, 외부 모듈 추가 (0) | 2018.02.22 |
| <2-2> 리스트, 튜플 (0) | 2018.02.15 |
<3-2> Set 과 Dictionary
동영상 강의 : http://pythonkim.tistory.com/notice/77
# Day_03_02_dict.py
- set 과 dictionary
1 2 3 4 5 | a = {} print(type(a), a) # <class 'dict'> {} b = {1} print(type(b), b) # <class 'set'> {1} | cs |
>> 중괄호를 이용한 컬렉션은 두가지 : set 과 dictionary
>> dictionary 가 set 보다 백만배 중요하다고 한다.
- dictionary 의 초기화
1 2 | c = {1:2} print(type(c), c) # <class 'dict'> {1: 2} | cs |
- Set
1 2 3 4 5 | d = {1, 2, 3, 1, 2, 3, 1, 2, 3} print(type(d), d) # <class 'set'> {1, 2, 3} e = [1, 2, 3, 1, 2, 3, 1, 2, 3] print(type(e), e) # <class 'list'> [1, 2, 3, 1, 2, 3, 1, 2, 3] | cs |
>> set은 중복된 데이터를 허용하지 않는다.
>> 반면, list 는 중복된 데이터를 허용한다.
# 문제
# 리스트에 들어있는 중복된 데이터를 제거하기
1 2 3 4 5 | e = [1, 2, 3, 1, 2, 3, 1, 2, 3] print(type(e), e) # <class 'list'> [1, 2, 3, 1, 2, 3, 1, 2, 3] e = list(set(e)) print(e) # [1, 2, 3] | cs |
>> set(e) 의 결과는 set 이므로 list 로 캐스팅.
- Dictionary
- 초기화
1 2 | d = {'color': 'red', 'price': 100} print(d) # {'color': 'red', 'price': 100} | cs |
>> key: value 의 쌍으로 구성된다.
- 초기화 2
1 2 3 4 | d = dict(color='red', price=100) print(d) # {'color': 'red', 'price': 100} print(d['color']) # red print(d['price']) # 100 | cs |
>> 위와 아래의 차이점은 거의 없다고 보면 된다.
>> 아래의 방법으로 초기화 하는 것을 선호한다고 한다. dict() 함수를 이용해서 dictionary 만드는 방법
>> key 값에 ' ' 를 생략하면 자동으로 포함이 된다.
>> 리스트는 요소들의 순서가 보장되지만, 딕셔너리는 순서를 보장하지 않는다.
>> 3, 4 : dictionary 요소 접근
- dictionary 에서 데이터 삽입
1 2 3 4 5 6 | # 데이터 삽입 d['title'] = 'pen' print(d) # {'color': 'red', 'price': 100, 'title': 'pen'} d['title'] = 'bread' print(d) # {'color': 'red', 'price': 100, 'title': 'bread'} | cs |
>> 2 : insert
>> 4 : update (title 이란 키값이 이미 존재하므로..!!)
>> dictionary 는 키값의 중복을 허용하지 않는다..!!
-
1 2 3 | print(d.keys()) # dict_keys(['color', 'price', 'title']) print(d.values()) # dict_values(['red', 100, 'bread']) print(d.items()) # dict_items([('color', 'red'), ('price', 100), ('title', 'bread')]) | cs |
# 문제
# keys, values, items 를 for문과 연결해서 처리해보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | for k in d.keys(): print(k, d[k]) print('-'*10) for v in d.values(): print(v) print('-'*10) for i in d.items(): print(i, i[0], i[1]) print('-'*10) for k, v in d.items(): print(k, v) | cs |
>> 2 : 키값을 통해 value 를 알 수 있다.
>> 5 : value 만으로는 아무것도 할 수 없다.
>> 9 : i 의 결과는 튜플이다. 그렇기 때문데, 13-14와 같은 형태로 이용을 한다.
>> 실행결과
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | color red price 100 title bread ---------- red 100 bread ---------- ('color', 'red') color red ('price', 100) price 100 ('title', 'bread') title bread ---------- color red price 100 title bread | cs |
- enumerate()
1 2 | for i in enumerate(d.items()): print(i) | cs |
>> 인덱스를 포함시킨 튜플의 형태가 된다.
>> 실행결과
1 2 3 | (0, ('color', 'red')) (1, ('price', 100)) (2, ('title', 'bread')) | cs |
- 튜플의 괄호 없애기
1 2 | for i in enumerate(d.items()): print(i[0], i[1][0], i[1][1]) | cs |
>> 실행결과
1 2 3 | 0 color red 1 price 100 2 title bread | cs |
-
1 2 3 4 5 | # for i, k, v in enumerate(d.items()): # print(i, k, v) for i, (k, v) in enumerate(d.items()): print(i, k, v) | cs |
>> 1 은 에러 : 하나의 인덱스와 하나의 튜플을 던져주므로 4와 같이 받아야 한다. (튜플의 요소는 2개인 상태)
- 딕셔너리를 통채로 전달해서 키값을 출력하는 방법
1 2 | for k in d: print(k) | cs |
>> 실행결과
1 2 3 | color price title | cs |
>> 이러한 이유로 d.keys() 를 사용하지 않는다.
'Language > Python' 카테고리의 다른 글
| <3-4> __name__, 리스트 슬라이싱 (0) | 2018.03.08 |
|---|---|
| <3-3> JSON (0) | 2018.03.05 |
| <3-1> 파일 입출력 (0) | 2018.02.23 |
| <2-3> 기상청의 전국 날씨정보 파싱, 외부 모듈 추가 (0) | 2018.02.22 |
| <2-2> 리스트, 튜플 (0) | 2018.02.15 |
180301 튜터링 - 트리(Tree)
< 180301 >
- 트리 : 계층 구조를 표현하는 비선형 자료구조
- 용어 : 노드(부모, 자식, 형제), 공집합 노드, 단말노드(리프, 터미널), 루트, 서브트리, 레벨, 높이
- 트리의 종류 : 일반트리, 이진트리(Binary Tree)
- 이진트리의 정의 : 모든 노드가 2개의 서브트리를 가지고 있는 트리. (서브트리는 공집합일 수 있다.)
- 이진트리의 성질
>> 노드 수 = 간선 수 + 1
>> 레벨에 따른 최소, 최대 노드를 구할 수 있다.
>> 노드가 n개 일때, 최대 레벨은 n, 최소 레벨은 ceil(log(n+1))
- 이진트리의 종류 : 완전, 포화
>> 완전 이진트리 : 레벨에 따라 왼쪽에서 오른쪽으로 순차적으로 노드가 삽입된 트리
>> 포화 이진트리 : 각 레벨에 노드가 가득 차 있는 이진 트리.
- 이진 트리의 표현
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 |
>> 노드는 이런식으로 디자인을 한다.
- 트리의 구현 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | // Tree #include <stdio.h> #include <stdlib.h> #define MAX 100 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); } } // 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; preorderPrint(root); printf("\n"); inorderPrint(root); printf("\n"); postorderPrint(root); printf("\n"); printf("노드 갯수 : %d개\n", nodeCount(root)); printf("depth : %d\n", height(root)); level(root); } | cs |
>> makeTreeNode() : 첫번째 인자로는 데이터를,
두번째 인자는 왼쪽 서브트리의 루트가 될 노드(의 주소)를,
세번째 인자로는 오른쪽 서브트리의 루트가 될 노드(의 주소)를 전달한다.
>> 21-27 : 전위순회 코드이다. 전위순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 탐색을 한다.
>> 29-35 : 중위순회 코드이다. 중위순회는 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 탐색을 한다.
>> 37-43 : 후외순회 코드이다. 후위순회는 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 탐색을 한다.
>> 45-49 : 노드의 갯수를 구하는 함수로
왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 자기 자신의 갯수를 포함한 것이 트리의 노드의 갯수가 된다
>> 51-60 : 트리의 높이를 구하는 함수로
왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 중 큰 값에 자기 자신이 높이(1)를 더한 것의 트리의 높이가 된다.
>> 62-68 : 트리의 모든 노드를 삭제하는 함수. 후위순회로 진행하면 된다. 다른 순회로 하면 왜 안되는지도 생각해보자.
>> 116-130 : 트리의 레벨 순회.
큐가 필요하다. 또한 TreeNode의 포인터를 담아야 하므로, 73 라인에서 보는 것 처럼 큐의 데이터 타입을 TreeNode* 로 변경하였다.
알고리즘은 다음과 같다.
1) 우선 루트를 큐에 담는다.
2) 큐가 비어 있지 않을때까지 루프를 돈다.
3) 큐에 있는 노드 하나를 꺼내 해당 데이터를 출력한다.
4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다.
>> 135-142 : 트리를 생성하는 과정이다.
### BST 는 아마 언젠가 업데이트를 할거 같아. 시간은 걸리겠지만, 하게되면 알려줄게. 여기까지 따라오느라 다들 수고 많았어!!
'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글
| 180301 튜터링 - 큐(Queue) (0) | 2018.03.01 |
|---|---|
| 180301 튜터링 - 스택의 응용 (수정:180514) (0) | 2018.03.01 |
| 180220 튜터링 - 스택 (0) | 2018.02.21 |
| 180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트 (0) | 2018.02.14 |
| 180206 튜터링 - 연결리스트 (0) | 2018.02.06 |
