Week 1-2 : How to code Recursive function
<180329>
- 재귀함수 만들기
1) 함수를 잘 정의하고, 그 정의를 그대로 활용하기
2) 어떻게 쪼갤지 생각하기..
3) 언제까지??(재귀의 종료, 탈출조건)
4) 점화식을 알고 있다면 그대로 표현하기.
- 구현해보기.
1) 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을 리턴하면 될 것 같다.
2) evenSum(n) : 1부터 n까지의 수 중 짝수의 합 구하기.
1 2 3 4 5 6 | int evenSum(int n) { if(n < 1) return 0; if(n&1) n--; return n + evenSum(n-2); } | cs |
>> n이 짝수인 경우, 1부터 n까지의 수 중 짝수의 합은 1부터 n-2까지의 수중 짝수의 합에 현재 값을 더하면 된다.
>> n이 홀수일 수도 있으므로, 4번 라인에서 예외처리를 한번 더 한다.
>> 홀수의 경우 마지막 비트는 항상 1이다. 그러므로 홀수와 1을 비트연산을 하면 1이 나온다. 조건식에서 1은 참..!!
3) combi(n, r) : n개의 수 중 r개의 수를 뽑는 방법의 수.
1 2 3 4 5 | int combi(int n, int r) { if(r == 0 || n == r) return 1; return combi(n-1, r-1) + combi(n-1, r); } | cs |
>> 우리는 nCr = n-1Cr + n-1Cr-1 이라는 점화식을 알고있다....ㅎㅎ
>> 해당 점화식을 그대로 표현했을 뿐이다.
>> 즉, n개의 수 중 r개의 수를 뽑는 방법의 수는
임의의 수 하나를 무조건 뽑는 다고 생각했을 때인, n-1개의 수 중 r-1 개를 뽑는 방법에 수와
그 임의의 수 하나를 무조건 안뽑는다고 생각햇을 때인, n-1개의 수 중 r 개를 뽑는 방법에 수를 더하면 된다.
>> 그리고 우리는 nC0 == nCn == 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까지 거꾸로 출력하는 것과 같다.
6) arrSum(int arr[], int n) : 배열 arr에서 0번째 값에서 n번째 값까지의 합을 구하는 함수.
1 2 3 4 5 | int arrSum(int arr[], int n) { if(n == 0) return arr[0]; return a[n] + arrSum(arr, n-1); } | cs |
>> 배열 arr에서 0값 요소에서 n번째 값까지의 합은 배열 arr에서 0번째 값에서 n-1번째 값까지의 합에 n번째 값을 더하면 된다.
7) arrMax(int arr[], int n) : 배열 arr에서 0번째 값에서 n번째까지의 값 중 최대값을 구하는 함수
1 2 3 4 5 6 7 | int arrMax(int arr[], int n) { int k; if(n == 0) return arr[0]; k = arrMax(arr, n-1); return a[n] > k ? a[n] : k; } | cs |
>> 배열 arr에서 0번째 값에서 n-1번째까지의 값 중 최대값이 k라고 하자.
then, k와 a[n] 중에서의 최대값이 배열 arr에서 0번째 값에서 n번째까지의 값 중에서 최대값이 된다.
>> 시각적인 이미지 참고 블로그(전에 설명 들은 동생이 정리해놨다..ㅎㅎ) : http://mattlee.tistory.com/17?category=680710
- 숙제 : 배열의 값들 중 두번째 최대값 구하기.
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 3-2 : Linked List (0) | 2018.04.15 |
|---|---|
| Week 3-1 : Linked List (0) | 2018.04.11 |
| Week 2-2 : ArrayList (0) | 2018.04.05 |
| Week 2-1 : How to code Recursive function2 (0) | 2018.04.04 |
| Week 1-1 : C Lang review (0) | 2018.03.28 |
Week 02
< 180328 >
1) 두 변수의 값 변경
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 a = 5; int b = 7; int t = a; a = b; b = t; printf("%d %d\n", a, b); a = 5; b = 7; a = a+b; b = a-b; a = a-b; printf("%d %d\n", a, b); return 0; } | cs |
>> a 컵에는 콜라, b컵에는 쥬스가 담겨있는 상황에서, 두 잔의 내용물을 바꾸고 싶을 때, 새로운 잔(t)를 이용하면 된다..!!
>> 17-19 는 새로운 변수 없이 두 정수값을 바꾸는 테크닉..?? 학교 교재에 있는 내용이라고 함..
2) sizeof 연산자 활용하기
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 | #include <stdio.h> int main() { char ch = 'A'; int n = 5; double d = 3.14; printf("char: %dbyte\n", sizeof(char)); // 1 printf("int: %dbyte\n", sizeof(int)); // 4 printf("flot: %dbyte\n", sizeof(float)); // 4 printf("double: %dbyte\n", sizeof(double)); // 8 printf("long: %dbyte\n", sizeof(long)); // 8 printf("long long: %dbyte\n", sizeof(long long)); // 8 printf("1: %dbyte\n", sizeof(1)); // 4 printf("'A': %dbyte\n", sizeof('A')); // 4 printf("3.14: %dbyte\n", sizeof(3.14)); // 8 printf("1LL: %dbyte\n", sizeof(1LL)); // 8 printf("ch: %dbyte\n", sizeof(ch)); // 1 printf("n: %dbyte\n", sizeof(n)); // 4 printf("d: %dbyte\n", sizeof(d)); // 8 return 0; } | cs |
>> 17 번 라인이 좀 특이하다. 1바이트를 기대했는데 4바이트가 나온다.
>> 관련 내용은 여기를 참고..!! (http://hashcode.co.kr/questions/76/cc에서-sizeofa의-차이)
3) 문자가 데이터에 어떻게 저장되는지..??
1 | char ch = 'A'; | cs |
위 코드의 경우 ch 라는 변수는 메모리 1바이트(8비트)를 차지한다.
그리고 해당 8비트에서 최 상위 비트는 부호비트를 나타낸다. 0은 양수, 1은 음수..!!
'A' 의 정체는 아스키 코드값 10진수로 65에 해당한다.
65는 이진수로 01000001 이다
즉, 8비트 기준으로 01000001 의 형태로 저장이 된다.
상위 1비트는 부호비트 이므로 char 타입의 변수에는 -128 ~ 127 까지의 값을 저장할 수 있다.
즉 256 개의 데이터를 저장할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include <stdio.h> int main() { char a = 127; printf("%d\n", a); // 127 a = a+1; printf("%d\n", a); // -128 return 0; } | cs |
>> 7 번라인의 결과는 127이다. 하지만 10의 결과는 128이 아닌 -128이 출력이 된다.
>> 127 은 2진수로 표현하면 01111111 이다. 여기에 1을 더하면 10000000 이 된다.
>> 최상위 비트는 부호비트인데 부호비트가 0에서 1로 변경되었다. 즉 음수가 되었다.
>> 다음 내용을 설명하기 전에, -1 이란 값에 대해 알아보자.
>> -1은 8비트 기준 11111111 이며, 32비트 기준 11111111 11111111 11111111 11111111 과 같이 표현한 수 있다.
>> 즉 1로만 가득채워진다.
>> 증명 : 위 값에 1을 더하면 0이된다. 8비트 기준 100000000 이 되는데, 1는 비트 범위를 넘어가므로 버리게 되므로 00000000, 즉 0이 된다.
>> 그렇다면 11111111을 이용해서 10000000 을 만들어보자.
>> 11111111 에서 01111111 을 빼면 10000000 이 된다.
>> 즉 -1에서 127을 뺀 결과이며 위 결과는 정확하게 -128이 나오게 된다.
4) 최상위 비트를 부호비트로 사용하지 않고싶다면..?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <stdio.h> int main() { unsigned char a = 127; printf("%d\n", a); // 127 a = a+1; printf("%d\n", a); // 128 a = 255; printf("%d\n", a); // 255 a = a+1; printf("%d\n", a); // 0 return 0; } | cs |
>> 변수를 선언할 때, 자료형 앞에 unsigned 를 추가로 선언하면 된다.
>> 11111111 은 255라는 값이 되며, 여기서 1을 더하면 0이 된다.
5) '1' vs 1
그러다면 위의 결과는..?
'1' 은 1바이트이며, '1'은 아스키코드값 10진수로 49에 해당한다.
49는 이진수로 110001 이므로 00110001 의 형태로 저장이 된다.
1은 정수이므로 4바이트가 필요하다. 그리고 1은 이진수로 1이다
그렇기 때문에 00000000 00000000 00000000 00000001 의 형태로 저장이 된다.
<숙제>
- 2의 보수 검색해보기.
- 오버플로우 검색해보기
Week 1-1 : C Lang review
<180327>
- C Lang review
8-3) 문자열 복사하기.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <stdio.h> void myStrcpy(char *to, char *from) { while(*from) *(to++) = *(from++); *to = 0; } int main() { char a[]="HS_Turoring"; char b[100]; myStrcpy(b, a); puts(b); return 0; } | cs |
>> 조건식에서의 참, 거짓.
>> 널문자의 아스키 코드값 == 0
>> 널문자 따로 넣어주기 (7번 라인)
>> 포인터 연산의 원리 생각해보기.
>> 배열의 이름은 상수형태의 포인터.
>> 포인터(변수)는 말그대로 변수이므로, 주소값이 바뀔 수 있다.
8-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 28 | #include <stdio.h> int myStrlen(char *s) { int i=0; while(s[i]) i++; return i; } void reverse(char *to, char *from) { int idx=0; int len=myStrlen(from); for(int i=len-1; i>=0; i--) to[idx++] = from[i]; to[idx] = 0; } int main() { char a[]="HS_Turoring"; char b[100]; reverse(b, a); puts(b); return 0; } | cs |
>> 널문자 삽입 코드 필수.
>> 배열의 이름[문자열의 길이] 에는 널문자가 들어있다.
>> 문자열의 길이는 reverse() 에서 구한다음 진행하면 됨.
9) 순환함수.
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 mul(int n) { if(n == 1) return 1; return n * mul(n-1); } int mulEven(int n) { if(n < 1) return 1; if(n%2 == 1) n--; return n * mul(n-2); } int main() { int n; scanf("%d", &n); printf("%d\n", mul(n)); printf("%d\n", mulEven(n)); return 0; } | cs |
>> 함수를 잘 정의하고, 그 정의를 그대로 활용하기.
>> 어떻게 쪼개서 생각할 수 있을까? 고민해보기.
>> 생각한 것을 그대로 코드로 옮기기. 함수의 기능을 그대로 활용해서..!!
>> 탈출조건 고민해보기.
2-4) is직각삼각형?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> int isTri(int max, int a, int b) { return max*max == a*a + b*b; } int main() { int a, b, c; int tri; scanf("%d%d%d", &a, &b, &c); if(a > b && a > c) tri = isTri(a, b, c); else if(b > a && b > c) tri = isTri(b, a, c); else tri = isTri(c, a, b); tri ? puts("직각") : puts("ㄴㄴ"); return 0; } | cs |
>> 큰값만 알면 되므로..
>> 함수를 사용해야 하는 이유 생각해보기..!!
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 3-2 : Linked List (0) | 2018.04.15 |
|---|---|
| Week 3-1 : Linked List (0) | 2018.04.11 |
| Week 2-2 : ArrayList (0) | 2018.04.05 |
| Week 2-1 : How to code Recursive function2 (0) | 2018.04.04 |
| Week 1-2 : How to code Recursive function (0) | 2018.03.30 |
Week 5 - BFS
<180324>
Week5 - BFS
[6593] 상범빌딩 (http://boj.kr/6593)
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; struct P { int L, R, C; }; int L, R, C; int dl[]={1, -1, 0, 0, 0, 0}; int dr[]={0, 0, 1, -1, 0, 0}; int dc[]={0, 0, 0, 0, 1, -1}; bool safe(int l, int r, int c) { return (0 <= l && l < 30) && (0 <= r && r < 30) && (0 <= c && c < 30); } int main() { while(1) { scanf("%d%d%d", &L, &R, &C); if(!L && !R && !C) break; P s, e; char g[31][31][31]; for(int l=0; l<L; l++) { for(int r=0; r<R; r++) scanf("%s", g[l][r]); for(int r=0; r<R; r++) { for(int c=0; c<C; c++) { if(g[l][r][c] == 'S') s = (P){l, r, c}; if(g[l][r][c] == 'E') { g[l][r][c] = '.'; e = (P){l, r, c}; } } } } queue<P> q; q.push(s); int visited[31][31][31]={0}; visited[s.L][s.R][s.C] = 1; while(!q.empty()) { int curL = q.front().L; int curR = q.front().R; int curC = q.front().C; q.pop(); if(curL == e.L && curR == e.R && curC == e.C) break; for(int k=0; k<6; k++) { int nL = curL+dl[k]; int nR = curR+dr[k]; int nC = curC+dc[k]; if(safe(nL, nR, nC) && g[nL][nR][nC]=='.' && !visited[nL][nR][nC]) { visited[nL][nR][nC] = visited[curL][curR][curC]+1; q.push((P){nL, nR, nC}); } } } int ans = visited[e.L][e.R][e.C]; if(!ans) puts("Trapped!"); else printf("Escaped in %d minute(s).\n", ans-1); } } | cs |
>> 3차원을 확장되었을 뿐, 이전 문제들과 동일하다.
>> 36번줄에 대해 처리를 안하면 답이 안나온다...
[5014] 스타트링크 (http://boj.kr/5014)
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; int F, S, G, U, D; int visited[1000001]; int main() { scanf("%d%d%d%d%d", &F, &S, &G, &U, &D); queue<int> q; q.push(S); visited[S] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); if(cur == G) break; int next = cur+U; if(next < 1000001 && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } next = cur-D; if(0 <= next && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } } if(!visited[G]) puts("use the stairs"); else printf("%d\n", visited[G]-1); } | cs |
[]
'Tutoring > PS' 카테고리의 다른 글
| Week 7 - DFS+BFS (0) | 2018.04.07 |
|---|---|
| Week 6 - BFS (숨박꼭질) (0) | 2018.03.30 |
| Week 4 - BFS (0) | 2018.03.11 |
| Week3 - DFS (0) | 2018.03.07 |
| Week 2 - DFS (0) | 2018.02.21 |
Week 01
< 180321 >
- C 언어는 main() 에서부터 시작한다..!!
- 첫 프로그래밍
1 2 3 4 5 6 7 | #include <stdio.h> int main() { printf("Hello World"); return 0; } | cs |
>> 1 : 헤더파일 선언, #include <stdio.h> 에서 stdio는 standard input output 의 약자.
- 주석처리
1 2 3 4 5 6 7 | //#include <stdio.h> int main() { printf("Hello World"); return 0; } | cs |
>> 1 : // 는 한줄을 주석처리 한다. 주석처리 하면 해당 라인을 무시한다.
>> 위의 경우 1번 라인을 무시하게 되면 printf() 를 사용할 수 없게 된다.
- 서식문자 : %d, %c, %lf
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { printf("int : %d\n", 20); printf("char : %c\n", 'A'); printf("double : %lf\n", 3.141592); return 0; } | cs |
>> 20 은 상수형 정수
>> 'A' 는 상수형 문자
>> 3.141592 는 상수형 실수
>> printf() 에서 정수를 출력하고 싶을 땐 서식문자 %d를, 문자는 %c, 실수는 %lf 를 사용한다.
>> 위의 경우 세종류의 데이터가 있다. 정수형, 문자형, 실수형
- 변수를 선언하고, 값을 대입하고 출력하기.
1) 정수
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { int num; num = 3; printf("num = %d\n", num); return 0; } | cs |
>> 5 : 정수형 변수 선언. 정수형 데이터를 담는 변수를 선언하기 위해서는 int 라는 자료형을 선언하고 한칸 띄고 변수 이름을 쓴다. (변수이름은 마음데로, 하지만 작명규칙이 존재, 찾아볼것.)
>> 6 : 정수값을 num 이란 변수에 대입. 여기서 = 는 대입연산자 이다.
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> int main() { int num; num = 3; printf("num = %d\n", num); // num = 3 num = 7; printf("num = %d\n", num); // num = 7 return 0; } | cs |
>> 9 : num 이란 변수에 7을 대입. 10 라인에서 num = 7 이란 결과가 출력
>> 변수 vs 상수 : 변수는 변하는 값. 어떤 값을 대입하냐에 따라 값이 바뀔 수 있다. 하지만 상수는 그 값 자체로만 사용이 가능. 그래서 상수.
2) 문자
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { char ch; ch = 'A'; printf("ch = %c\n", ch); // ch = A return 0; } | cs |
>> 5 : 문자를 담는 변수를 선언하기 위해서는 자료형 char 을 사용
3) 실수
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { double dnum; dnum = 3.14; printf("dnum = %lf\n", dnum); // dnum = 3.140000 return 0; } | cs |
>> 5 : 실수를 담는 변수를 선언하기 위해서는 자료형 double 를 선언한다.
>> 7 : 실행결과는 dnum = 3.140000 , 기본적으로 소수점 6자리까지 출력한다.
- 문자의 정체
1 2 3 4 5 6 7 8 | #include <stdio.h> int main() { char ch = 'b'-'a'; printf("ch = %d\n", ch); // ch = 1 return 0; } | cs |
>> 5 : 변수 ch를 선언과 동시에 'b'-'a' 값으로 초기화
>> 여기서 'b'-'a' 라는 연산이 가능하다...!!
1) 문자의 정체는 정수. 실제로 어떤 문자는 어떤 정수의 값으로 매핑(매칭)되어 있다. (아스키 코드표 참조)
2) 아스키 코드값의 특징
>> 문자인 숫자는 '0', '1', '2', ... '9' 의 순서로 되어 있다. 얼마에 매핑되어 있는지는 외울 필요 없음.
>> 알파벳 대문자는 'A', 'B', 'C', ... , 'Z' 순으로 되어있다.
>> 알파벳 소문자는 'a', 'b', 'c', ... , 'z' 순으로 되어 있따.
>> 알파벳 대문자가 소문자보다 앞선다. (작은 값을 갖는다.)
>> 'a' 와 'A'의 차이, 'b' 와 'B'등 소문자와 대문자 사이의 아스키코드 값 차이는 일정하다.
>> 널문자의 아스키 코드값은 0 (알아두면 좋음.)
- 소문자를 대문자로, 대문자를 소문자로 변경해서 출력하기.
1 2 3 4 5 6 7 8 9 10 11 | #include <stdio.h> int main() { char ch1 = 'a'; char ch2 = 'A'; char diff = 'a'-'A'; printf("a => %c\n", ch1-diff); // a => A printf("A => %c\n", ch2+diff); // A => a return 0; } | cs |
>> 소문자와 대문자의 차이가 일정하기 때문에, 그 일정한 값을 대문자에서 더해주면 소문자가 되고, 소문자에서 빼주면 대문자가 된다...!!
- 문자 '9' 를 정수 9로 표현하기.
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { char num = '9'; printf("num = %c\n", num); printf("num = %d\n", num-'0'); return 0; } | cs |
>> 6, 7번라인 모두 9를 출력한다. 6의 결과는 문자형태의 9, 7의 결과는 정수형태의 9.
>> '1' 과 '0' 의 차이는 1 이다.
>> '2' 와 '1'의 차이도 1 이다.
>> '2' 와'0'의 차이는 2이다. >> '9' 와 '0'의 차이는 9 가 된다..!!
- 기타
1) 검색은 구글에서.
2) 소스코드를 실행했을 때 뜨는 창의 이름은 콘솔창.
3) VS2017 에서 빌드하고 컴파일 할때 단축시 사용하기..!!
4) C 언어의 소스코드 확장자는 .c
5) 과제는 기왕이면 해와서 튜터링 시간에 맞춰보기.
- 숙제
1) 1 vs '1' 의 차이 알아보기.
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 |
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 |
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 |
180301 튜터링 - 큐(Queue)
< 180301 >
- 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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <stdio.h> #include <stdlib.h> #define MAX 100 typedef struct queue { int 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); } void enqueue(Queue * q, int data) { q->data[(q->rear)++] = data; } int peek(Queue * q) { if (isEmpty(q)) { printf("(peek)큐가 비어있습니다. : "); return -11111; } return q->data[q->front]; } void dequeue(Queue * q) { if (!isEmpty(q)) { (q->front)++; } } int main() { Queue q; init(&q); enqueue(&q, 1); enqueue(&q, 9); enqueue(&q, 9); enqueue(&q, 8); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); } | 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 | #include <stdio.h> #include <stdlib.h> #define MAX 100 typedef struct queue { int 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, int data) { if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n"); else { q->rear = (q->rear + 1) % MAX; q->data[q->rear] = data; } } int peek(Queue * q) { if (isEmpty(q)) { printf("(peek)큐가 비어있습니다. : "); return -11111; } return q->data[(q->front+1) % MAX]; } void dequeue(Queue * q) { if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n"); else { q->front = (q->front + 1) % MAX; } } int main() { Queue q; init(&q); enqueue(&q, 1); enqueue(&q, 9); enqueue(&q, 9); enqueue(&q, 8); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); dequeue(&q); printf("%d\n", peek(&q)); } | cs |
>> 사용한 공간의 낭비를 막을 수 있다.
>> 빈 상태와 포화상태를 구분하기 위해 한 칸을 비워둔다.
>> 21-23 : 포화상태에 대한 코드이다. 모듈러 연산을 통해 마지막 인덱스 다음 인덱스를 0으로 만들 수 있다.
### 연결리스트를 이용한 큐를 만들어보자.
>> head 포인터를 front 로, tail 포인터를 rear 로 두고 만들면 된다.
### 덱
>> 앞으로도 넣고 뒤로더 넣을 수 있으며, 앞에서도 꺼내고 뒤에서도 꺼낼 수 있다.
'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글
| 180301 튜터링 - 트리(Tree) (0) | 2018.03.02 |
|---|---|
| 180301 튜터링 - 스택의 응용 (수정:180514) (0) | 2018.03.01 |
| 180220 튜터링 - 스택 (0) | 2018.02.21 |
| 180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트 (0) | 2018.02.14 |
| 180206 튜터링 - 연결리스트 (0) | 2018.02.06 |
180301 튜터링 - 스택의 응용 (수정:180514)
< 숙제 Review >
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 | #include <stdio.h> #define MAX 100 typedef struct stack { char s[MAX]; int top; } Stack; void init(Stack *s); int isEmpty(Stack *s); int isFull(Stack *s); void push(Stack *s, char data); char peek(Stack *s); void pop(Stack *s); int isRightBraket(char *bk) { int idx; Stack s; init(&s); for(idx=0; bk[idx]; idx++) { char ch = bk[idx]; if(ch == '{' || ch == '(' || ch == '[') push(&s, ch); else { char tmp; if(isEmpty(&s)) return 0; tmp = peek(&s); pop(&s); if((tmp == '{' && ch != '}') || (tmp == '[' && ch != ']') || (tmp == '(' && ch != ')')) return 0; } } return isEmpty(&s); } int main() { char str[]="[(){}[(){}]]"; isRightBraket(str) ? puts("True") : puts("False"); return 0; } | cs |
>> 28-29 : 여는 괄호에 대한 짝이 안맞으면 0을 리턴.
>> 30 : 검사가 끝나면 스택은 비워있어야 하므로..!!
>> 26번 라인잉 추가되었다. 이 코드가 없으면 닫는 괄호로 먼저 시작하는 코드들에 대해 에러가 발생한다. (수정:180514)
2. 중위식을 후위식으로 만드는 함수 (http://boj.kr/1918)
- 연산자 우선순위
>> *, / : 제일 크다.
>> +, - : 두번째
>> ( : 제일 작다.
- 규칙
>> 피연산자를 만나면 그대로 출력
>> 연산자를 만나면 스택에 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 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 | #include <stdio.h> #define MAX 100 typedef struct stack { char s[MAX]; int top; } Stack; void init(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAX-1; } void push(Stack *s, char data) { s->s[++(s->top)] = data; } char peek(Stack *s) { return s->s[s->top]; } void pop(Stack *s) { (s->top)--; } int getPriority(char op) { switch(op) { case '*': case '/': return 10; case '+': case '-': return 1; } return 0; } void infixToPostfix(char *t) { Stack s; init(&s); for(int i=0; t[i]; i++) { char ch = t[i]; if('A' <= ch && ch <= 'Z') printf("%c", ch); else { if(ch == '(') push(&s, ch); else if(ch == ')') { char op = peek(&s); while(op != '(') { printf("%c", op); pop(&s); op = peek(&s); } pop(&s); } else { int curP = getPriority(ch); while(curP <= getPriority(peek(&s))) { printf("%c", peek(&s)); pop(&s); } push(&s, ch); } } } while(!isEmpty(&s)) { printf("%c", peek(&s)); pop(&s); } } int main() { char s[100]; scanf("%s", s); infixToPostfix(s); puts(""); return 0; } | cs |
>> 이전 튜터링(스택) 때 서술한 알고리즘을 그대로 구현한 코드다
>> A+(B*C)*D*E+F —> ABC*D*E*+F+ 이렇게 결과가 나온다.
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 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 | #include <stdio.h> #include <stdlib.h> #define MAX 100 typedef struct stack { char s[MAX]; int top; } Stack; void init(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAX-1; } void push(Stack *s, char data) { s->s[++(s->top)] = data; } char peek(Stack *s) { return s->s[s->top]; } void pop(Stack *s) { (s->top)--; } int getPriority(char op) { switch(op) { case '*': case '/': return 10; case '+': case '-': return 1; } return 0; } char* infixToPostfix(char *t) { char *res = (char*)malloc(sizeof(char)*100); int idx=0; Stack s; init(&s); for(int i=0; t[i]; i++) { char ch = t[i]; if('0' <= ch && ch <= '9') { res[idx++]=ch; printf("%c", ch); } else { if(ch == '(') push(&s, ch); else if(ch == ')') { char op = peek(&s); while(op != '(') { printf("%c", op); res[idx++]=op; pop(&s); op = peek(&s); } pop(&s); } else { int curP = getPriority(ch); while(curP <= getPriority(peek(&s))) { printf("%c", peek(&s)); res[idx++] = peek(&s); pop(&s); } push(&s, ch); } } } while(!isEmpty(&s)) { printf("%c", peek(&s)); res[idx++] = peek(&s); pop(&s); } res[idx] = 0; return res; } 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 = peek(&s); pop(&s); int op1 = peek(&s); 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() { char s[100], *t; scanf("%s", s); printf("%s = ", s); t=infixToPostfix(s); printf(" = %d\n", exp(t)); free(t); return 0; } | cs |
>> input : 8/2-3+3*2
>> infixToPostfix() 에서 출력을 할 때마다 해당 문자를 배열에 저장하고,
이전에 구현해놓은 exp() 를 그대로 사용하면 된다..
여기서 후위식을 저장할 배열을 왜 동적할당을 했는지 생각해보자..!! (지역변수 관련)
4. 미로탐색
...
'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글
| 180301 튜터링 - 트리(Tree) (0) | 2018.03.02 |
|---|---|
| 180301 튜터링 - 큐(Queue) (0) | 2018.03.01 |
| 180220 튜터링 - 스택 (0) | 2018.02.21 |
| 180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트 (0) | 2018.02.14 |
| 180206 튜터링 - 연결리스트 (0) | 2018.02.06 |
