Week 05
< 180418 >
1) if ~else if~ 를 활용한 학점 계산.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> int main() { int n; scanf("%d", &n); if(90 <= n) printf("A\n"); else if(80 <= n) printf("B\n"); else if(70 <= n) printf("C\n"); else printf("D\n"); return 0; } | cs |
>> 9 라인의 경우 else if(80 <= n && n < 90) 으로 써도 되지만, 위와 같이 써도 된다.
2) 위 문제를 switch case 문으로.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <stdio.h> int main() { int n; scanf("%d", &n); switch(n/10) { case 10: printf("A\n"); break; case 9: printf("A\n"); break; case 8: printf("B\n"); break; case 7: printf("C\n"); break; default: printf("D\n"); break; } return 0; } | cs |
3) switch case 문의 실행흐름
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <stdio.h> int main() { int n; scanf("%d", &n); switch(n/10) { case 10: printf("A\n"); case 9: printf("A\n"); break; case 8: printf("B\n"); break; case 7: printf("C\n"); break; default: printf("D\n"); break; } return 0; } | cs |
>> 10 라인에서 break; 를 삭제하였다. 그다음 100을 입력받아 n에 저장하면 AA 가 출력된다..!!
>> 90 을 입력하면 A가 출력된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <stdio.h> int main() { int n; scanf("%d", &n); switch(n/10) { case 10: printf("A\n"); case 9: printf("A\n"); case 8: printf("B\n"); break; case 7: printf("C\n"); break; default: printf("D\n"); break; } return 0; } | cs |
>> 11 라인에 break; 도 삭제해보자. 그다음 100을 입력하면 AAB 가 출력된다.
>> 즉, 해당하는 case 번호를 만나면, 해당라인에서 break; 를 만날때까지 실행이 된다.
(90 을 입력하면 AB 가, 80을 입력하면 B가 출력된다.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <stdio.h> int main() { int n; scanf("%d", &n); switch(n/10) { case 10: case 9: printf("A\n"); break; case 8: printf("B\n"); break; case 7: printf("C\n"); break; default: printf("D\n"); break; } return 0; } | cs |
>> 2) 문제의 경우 위와같이 작성하면 된다.
4) 대문자 A 인지 소문자 a 인지, switch case 문으로
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <stdio.h> int main() { char ch; scanf("%c", &ch); switch(ch) { case 'A': printf("대문자 A\n"); break; case 'a': printf("소문자 a\n"); break; } return 0; } | cs |
>> case 다음에는 정수가 와야한다. 하지만 문자도 올 수 있다. 문자의 정체는 정수이기 때문이다..!!
5) 입력한 문자가, 대문자인지, 소문자인지, 숫자인지, 특수문자인지
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> int main() { char ch; scanf("%c", &ch); if('A' <= ch && ch <= 'Z') printf("대문자\n"); else if('a' <= ch && ch <= 'z') printf("소문자\n"); else if('0' <= ch && ch <= '9') printf("숫자\n"); else printf("특수문자\n"); return 0; } | cs |
>> && 연산자의 활용, 아스키 코드값의 특징 확인.
6) 임의의 숫자를 입력받아 실수형 숫자이면 소수 이하 숫자만 출력하고, 정수형 숫자면 짝수, 홀수를 구분하여 출력하는 프로그램 (7.7)
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> int main() { double d; scanf("%lf", &d); if(d - (int)d > 0) printf("%lf\n", d-(int)d); else (int)d%2 == 1 ? printf("odd\n") : printf("even\n"); return 0; } | cs |
7) printf() 에서의 증감연산자
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> int main() { int a = 4, b = 7; printf("%d\n", a + a++); // 8 printf("%d\n", ++a + a); // 12 printf("%d\n", (++a) + (++a)); // 15 , VS >> 16 printf("%d\n", b + b--); // 14 printf("%d\n", b + --b); // 11 , VS >> 10 return 0; } | cs |
>> 9라인의 결과가 Mac 에서 진행한 것과, Visual Studio 에서 진행한 것이 다르다....
Week 4-1 : Linked List
< 180417 >
1) 연결리스트에서 특정 값을 찾는 함수.
1 2 3 4 5 6 7 8 9 10 | ListNode* search(ListNode *head, int x) { ListNode *p = head; while(p) { if(p->data == x) return p; p = p->link; } return p; // p == NULL } | cs |
>> main() 에서의 head 포인터가 가리키는 대상이 변경될 가능성이 없기 때문에..!! 싱글포인터 자체로 매개변수로 전달 받는다.
>> 찾는 값이 없으면 NULL 을 리턴한다.
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 | void changeMax(ListNode **phead) { ListNode *prev=NULL, *cur=*phead; ListNode *pMax=NULL, *cMax=*phead; if(*phead == NULL) return ; while(cur->link != NULL) { if(cMax->data < cur->data) { cMax = cur; pMax = prev; } prev = cur; cur = cur->link; } // Compare cMax with last Node if(cMax->data < cur->data) { cMax = cur; pMax = prev; } // swap node pMax == NULL ? (cur->link = (*phead)->link) : (cur->link = pMax->link); pMax == NULL ? (*phead = cur) : (pMax->link = cur); prev->link = cMax; cMax->link = NULL; } | cs |
>> 8 : cur->link != NULL 이라고 조건의 설정해야 cur 포인터가 마지막 노드를 가리키게 된다.
>> 23-26 : 노드를 스왑하는 과정이다. 그림을 그려가며 순서를 잘 파악한 다음 코드로 옮겨버릇하자.
>> 매개변수로는 더블포인터를 주었다. main() 에서의 head 포인터가 가리키는 노드가 변경될 수 있기 때문이다.
(head 포이터가 가리키는 첫번째 노드가 최대값인 경우)
3) 두 개의 연결리스트 이어 붙이기.
- 교재의 있는 코드는 아래와 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | ListNode* concat(ListNode *head1, ListNode *head2) { ListNode *p; if(head1 == NULL) return head2; if(head2 == NULL) return head1; p = head1; while(p->link != NULL) p = p->link; p->link = head2; return head1; } | cs |
>> 이전까진 별 생각이 없었는데, 다시보니 head1 == NULL 인경우, 이 함수가 종료가 되어도 head1 은 NULL 상태 그대로다.
>> 하지만, head1 != NULL 인 경우, 마지막 노드에 head2 가 가리키는 노드를 이어 붙인다음 head1 의 주소를 리턴한다.
즉, 위의 경우 head1 의 변경이 없는데, 아래의 경우 head1 의 변경이 생긴다. 일관성이 없다.. 맘에 안든다;;
- 그래서 바꾸어 보았다. 무조건 head1 의 뒤에 이어붙여지는 결과가 될 수 있도록..!!
1 2 3 4 5 6 7 8 9 10 11 12 | void concat(ListNode **head1, ListNode *head2) { ListNode *p; if(head1 == NULL) { *head1 = head2; return ; } if(head2 == NULL) return ; p = *head1; while(p->link != NULL) p = p->link; p->link = head2; } | cs |
>> 8-9 : 루프를 빠져나가면 p는 마지막 노드를 가리키는 상태가 된다.
>> 예시는 아래와 같다.
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 5-1 : Circular Doubly Linked List / Stack ADT (0) | 2018.05.08 |
|---|---|
| Week 4-2 : Circular Linked List (0) | 2018.04.20 |
| 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 3-2 : Linked List
< 180412 >
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 | #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *link; } ListNode; ListNode* create_node(int data, ListNode* link) { ListNode *newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = data; newNode->link = link; return newNode; } void addNode(ListNode** phead, ListNode* newNode) { if(*phead == NULL) *phead = newNode; else { newNode->link = *phead; *phead = newNode; } } int main() { ListNode *head = NULL; addNode(&head, create_node(10, NULL)); addNode(&head, create_node(20, NULL)); return 0; } | cs |
>> 19 : 메인함수에서의 head 가 NULL 인경우 바로 뉴노드를 연결하면 된다.
>> 20-23 : head 가 어떤 노드를 가지고 있다면, 새로운 노드가 그 노드를 가리키고, head 가 뉴노드를 가리키도록 한다.
>> 이런식으로 진행이 된다.
2) 노드 추가하기 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 | #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *link; } ListNode; ListNode* create_node(int data, ListNode* link) { ListNode *newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = data; newNode->link = link; return newNode; } void addNode2(ListNode **phead, ListNode *p, ListNode *newNode) { if(*phead == NULL) *phead = newNode; else if(p == NULL) { newNode->link = *phead; *phead = newNode; } else { newNode->link = p->link; p->link = newNode; } } void display(ListNode *phead) { while(phead) { printf("%d ", phead->data); phead = phead->link; } } int main() { ListNode *head = NULL; ListNode *node; addNode2(&head, NULL, create_node(10, NULL)); node = create_node(20, NULL); addNode2(&head, NULL, node); addNode2(&head, NULL, create_node(30, NULL)); display(head); puts(""); addNode2(&head, node, create_node(40, NULL)); display(head); return 0; } | cs |
>> addNode2() 를 보자.
>> 첫번째 매개변수는 메인함수의 head 의 주소를, p 에는 새로 삽입할 노드의 이전 노드를, 마지막은 새로 삽입할 노드를 가리킨다.
>> 19 : 헤드가 비어있는 경우,
>> 20 : p == NULL 이란 것은 맨 왼쪽에 노드를 삽입하는 경우
>> 그 외의 경우는 p 노드의 다음자리에 새로운 노드를 삽입하는 경우 이다.
>> 실행결과
30 20 10
30 20 40 10
>> 그림으로 보면 아래와 같다.
- 45 라인까지의 실행결과.
- 48 라인에서 addNode2() 가 호출된 직후의 상황
>> phead 는 *phead 라고 생각하는게 나을것 같다.
- addNode2() 가 호출된 다음, 함수가 종료되기 직전의 상황.
>> phead 는 *phead 라고 생각하는게 나을것 같다.
3) display() 함수 (30-36 라인)
>> display() 함수를 보쟈. 함수의 내용은 어렵지 않을 것이다. 하지만 addNode() 와 비교해보면, 이중포인터로 받지 않는다는 것이 차이점이다.
>> 이것은 main() 의 head 가 가리키는 노드가 변경될 가능성이 있을 경우에는 이중포인터로 받아야 하지만,
display() 는 그럴필요가 없기 때문에 이중포인터로 받을 필요가 없다..!!
4) 노드의 삭제
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 4-2 : Circular Linked List (0) | 2018.04.20 |
|---|---|
| Week 4-1 : Linked List (0) | 2018.04.18 |
| 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 04
< 180411 >
Week 04
1) 1의 보수, 2의 보수.
- 10은 2진수로 00001010 (8비트 기준)
- 1의 보수를 취하면 11110101 이 된다. (0은 1로, 1은 0으로)
- 2의 보수는 1의 보수의 결과에 1을 더하면 된다. 11110110
>> 2의 보수의 결과는 -10이 된다.
>> 검증 : -1은 11111111 이다. 여기에서 9인 00001001 을 빼면 11110110 이 된다.
2) 삼항연산자( ? 연산자)
- 삼항 연산자의 폼은 (조건식) ? 식1 : 식2; 이다.
- 조건식의 결과는 참 혹은 거짓이다.
- 조건식의 결과가 참이면 식1이, 거짓이면 식2가 수행된다.
3-1) 두 수를 입력받아, 두수의 차이의 절대값을 출력하는 프로그래밍
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { int a, b; scanf("%d%d", &a, &b); printf("%d\n", a > b ? a-b : b-a); return 0; } | cs |
3-2) 세 수를 입력받아, 가장 큰값과 가장 작은 값을 출력하는 프로그래밍
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> int main() { int a, b, c; int max, min; scanf("%d%d%d", &a, &b, &c); max = a > b ?(a > c ? a : c) : (b > c ? b : c); min = a < b ?(a < c ? a : c) : (b < c ? b : c); printf("%d %d\n", max, min); return 0; } | cs |
>> 중첩된 삼항연산자 이해해보기..!!
4) 조건식에서의 참과 거짓.
- 거짓은 0으로 표현된다.
- 참은 0이 아닌 모든값, 즉 0이 아닌 모든 정수값이 된다.
1 2 3 4 5 6 7 8 9 10 11 | #include <stdio.h> int main() { 0 ? printf("A") : printf("B"); 1 ? printf("A") : printf("B"); 13 ? printf("A") : printf("B"); -2 ? printf("A") : printf("B"); return 0; } | cs |
>> 실행결과 : BAAA
5) && 연산자
- (조건식) && (조건식) 의 형태를 이룬다.
- 두 조건식이 참이면 참이 된다.
1 2 3 4 5 6 7 8 9 10 | #include <stdio.h> int main() { 1 && 1 ? printf("A") : printf("B"); 1 && 0 ? printf("A") : printf("B"); 0 && 1 ? printf("A") : printf("B"); 0 && 0 ? printf("A") : printf("B"); return 0; } | cs |
>> 실행결과 : ABBB
6) 문자 하나를 입력받아, 해당 문자가 알파벳 대문자인지 판단하는 프로그래밍.
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { char ch; scanf("%c", &ch); 'A' <= ch && ch <= 'Z' ? printf("TRUE") : printf("FALSE"); return 0; } | cs |
>> 아스키코드값의 특징, && 의 특징, 삼항연산자를 쓸 줄 알면 풀 수 있는 문제이다.
7) || 연산자.
- (조건식) || (조건식) 의 형태를 가지며, 두 조건식 중 하나의 조건식만 참이면 참이 된다.
1 2 3 4 5 6 7 8 9 10 11 | #include <stdio.h> int main() { 1 || 1 ? printf("A") : printf("B"); 1 || 0 ? printf("A") : printf("B"); 0 || 1 ? printf("A") : printf("B"); 0 || 0 ? printf("A") : printf("B"); return 0; } | cs |
>> 실행결과 : AAAB
8) 대입연산자
1 2 3 4 5 6 7 8 9 | #include <stdio.h> int main() { int a, b; a = b = 0; printf("%d %d\n", a, b); return 0; } | cs |
>> 6 번 라인을 보자. b = 0; 이라는 식은 b 에 0을 대입하고, 그 식 자체의 결과는 또한 0이 된다.
>> 그렇기 때문에 a = b = 0; 은 a = (b = 0); 에서 a = (0); 으로 이어지며,
>> 결과적으로 a 와 b 두 변수 모두에 0이 대입된다.
9) || 연산의 단축연산
- 아래의 프로그래밍의 실행결과를 에측해보자.
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> int main() { int a, b; a = b = 0; (a = 5) || (b = 3) ? printf("A") : printf("B"); printf(" %d %d\n", a, b); return 0; } | cs |
10) ! 연산자 (NOT 연산자)
- 참을 거짓으로, 거짓을 참으로 만드는 연산자 이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <stdio.h> int main() { int a=0; int b=3; !a ? printf("A") : printf("B"); !b ? printf("A") : printf("B"); !0 ? printf("A") : printf("B"); !1 ? printf("A") : printf("B"); return 0; } | cs |
>> 실행결과는 ABAB
11) Shift 연산자 >>, <<
- << 는 비트단위로 왼쪽으로 한칸씩 밀어낸다.
- >> 는 비트단위로 오른쪽으로 한칸씩 밀어낸다.
- 10을 2진수로 표현하면 00001010 이다.
- a = 10; a = a >> 1; 이 수행되면, 00000101 이 된다. 즉 a 에는 5가 저장지며, 결과적으로 2로 나눈 몫이 된다.
- a = 10; a = a << 1; 이 수행되면, 00010100 이 된다. 즉 a 에는 20이 저장되며, 결과적으로 2가 곱해진 결과가 된다.
- a = 10; a = a >> 2; 가 수행되면 a 는 2가 된다.
- a = 10; a = a << 2; 가 수행되면 a 는 40이 된다.
12) 기타.
- 콤마연산자
- 연산자 우선순위
- 단항, 2항, 3항, 대입, 콤마 연산자.
- 컴퓨터는 뺄셈, 곱셈, 나눗셈을 보수를 이용해서 덧셈으로 처리한다는 내용. >> 10 - 3 => 10 + (-3)
- 나눗셈의 경우에 피제수와 보수를 더하여 100이 될 때까지 더해진 횟수가 몫이 된다는 내용
>> Self...^^
Week 3-1 : Linked List
< 180410 >
1) 수시고사 review
- 특정 알파벳 갯수를 구하는 함수 만들기
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 findCh(char *s, char ch) { int cnt=0; while(*s) { if(*s == ch) cnt++; s++; } return cnt; } int main() { char str[]="Data Structure"; int cnt; cnt = findCh(str, 'u'); printf("%d\n", cnt); return 0; } | cs |
2) 노드 디자인하기 (with 자기참조 구조체) AND 헤드 포인터 선언 및 초기화
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include <stdio.h> typedef struct node { int data; struct node *link; } ListNode; int main() { ListNode *head = NULL; return 0; } | cs |
>> 3-6 : 노드 디자인하기
>> 10 : 노드를 연결하는 시작끈의 역할..정도?
>> NULL 로 초기화 해야한다.
>> main() 에서 10라인이 수행되고 나서의 상황.
3) create_node(10, NULL) 함수 만들기.
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> #include <stdlib.h> typedef struct node { int data; struct node *link; } ListNode; ListNode* create_node(int date, ListNode *link) { ListNode *newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = data; newNode->link = link; return newNode; } int main() { ListNode *head = NULL; ListNode *newNode = create_node(10, NULL); return 0; } | cs |
>> 그냥 노드를 만들어서 그 노드를 리턴하는 함수..!!
>> 매개변수로는 data 에 저장할 값과 새로운 노드에 연결할 노드의 주소를 전달한다.
>> create_node() 가 호출되어 종료되기 직전의 상황이며, 빨간선으로 된 화살표는 함수가 리턴한 결과이다.
>> data 와 link 의 매개변수에 대한 그림은 생략...(사실 그렸어야 하는데, 빼먹음. 피피티 작업 다시 하기 귀찮......)
>> create_node() 함수의 호출이 끝난 다음 main() 의 상황이다.
4) 지역변수와 동적할당
1 2 3 4 5 6 7 | ListNode* create_node(int date, ListNode *link) { ListNode newNode; newNode.data = data; newNode.link = link; return &newNode; } | cs |
>> 이런식으로 하면 newNode 의 주소가 넘어가지만,
newNode 는 지역변수이므로 함수가 끝나는 시점(중괄호가 끝나는 시점)에서 더이상 유효하지 않게 된다.
그렇기 때문에, 해당 메모리는 언제 다른 변수에게 할당될 지 모르는 일.
>> 하지만 동적할당을 하면 해당 변수의 라이프 타임은 프로그래머가 free() 로 직접 해제하기 전까지 유효하게 된다.
>> 그렇기 때문에 3) 에서 처럼 작성하는 것이 옳다. (함수가 끝나도 해당 데이터는 유효하므로..!!)
5) 헤드 포인터에 첫 노드 연결하기.
>> 이런 모양의 결과가 나오도록 add_node() 를 구현해보려고 한다.
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> #include <stdlib.h> typedef struct node { int data; struct node *link; } ListNode; ListNode* create_node(int date, ListNode *link) { ListNode newNode; newNode.data = data; newNode.link = link; return &newNode; } void add_node(ListNode **head, ListNode *listNode) { *head = listNode; } int main() { ListNode *head = NULL; ListNode *newNode = create_node(10, NULL); add_node(&head, newNode); return 0; } | cs |
>> 17-20, 26 : 매개변수를 전달하는 데 있어 타입에 꼭 신경을 쓰자, 포인터 변수의 주소를 넘기므로 더블포인터로 값(주소)을 받을 수 있다.
>> 단순히 하나를 연결하기 위한 함수이다. 확장할 예정이니 태클은 ㄴㄴ.
>> add_node() 함수가 호출된 직후의 상황. add_node() 의 head 와 link 는 매개변수이지만, 해당함수의 지역변수라고 보면 된다.
>> 19 번 라인이 수행된 결과이다.
- 시간내서 http://ychooni.tistory.com/34?category=277002 여기에 있는 내용들도 확인해보자..!!
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 4-1 : Linked List (0) | 2018.04.18 |
|---|---|
| Week 3-2 : Linked List (0) | 2018.04.15 |
| 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 7 - DFS+BFS
<>
Week 7 : DFS+BFS
[2146] 다리 만들기 (http://boj.kr/2146)
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 | #include <cstdio> #include <queue> #include <cstring> using namespace std; struct P { int r, c; }; int n; int g[101][101]; int checked[101][101]; int dr[]={1, 0, -1, 0}; int dc[]={0, 1, 0, -1}; int min(int a, int b) { return a < b ? a : b; } bool safe(int r, int c) { return (0 <= r && r < n) && (0 <= c && c < n); } void dfs(queue<P> &q, int r, int c, int cnt) { g[r][c] = cnt; for(int k=0; k<4; k++) { int nr = r+dr[k]; int nc = c+dc[k]; if(safe(nr, nc)) { if(g[nr][nc] == 1) { dfs(q, nr, nc, cnt); } else {// g[nr][nc] == 0 if(!checked[nr][nc]) { q.push((P){nr, nc}); checked[nr][nc] = 1; } } } } } int bfs(queue<P> &q, int cnt) { 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(safe(nr, nc) && g[nr][nc] != cnt && !checked[nr][nc]) { checked[nr][nc] = checked[curR][curC]+1; q.push((P){nr, nc}); if(g[nr][nc] != 0) { return checked[curR][curC]; } } } } return 1e9; } int main() { scanf("%d", &n); for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d", &g[i][j]); int cnt = 1; int ans = 1e9; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(g[i][j] == 1) { cnt++; queue<P> q; dfs(q, i, j, cnt); int tmp = bfs(q, cnt); ans = min(ans, tmp); memset(checked, 0, sizeof(checked)); } } } printf("%d\n", ans); } | cs |
>> 일단 하나의 섬을 하나의 컴퍼넌트로 체크를 하고, 섬 주위의 바다(0) 을 큐에 담는다.
>> 큐에 담긴 바다를 시작으로 거리를 잰다. 이때 현재섬이 아닌 섬을 만난 경우, 현재섬으로부터의 최소거리가 되므로 그 거리를 리턴한다.
>> 현재섬에는 cnt 값이 들어있다.
[]
[2573] 빙산 : http://boj.kr/2573
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 <cstdio> #include <queue> using namespace std; struct P { int r, c; }; struct M { int r, c, cnt; }; int r, c; int g[301][301]; int dr[] = {1, 0, -1, 0}; int dc[] = {0, 1, 0, -1}; int visited[301][301]; queue<P> q; void dfs(int i, int j, int &ans) { visited[i][j] = ans; for(int k=0; k<4; k++) { int ni = i+dr[k]; int nj = j+dc[k]; if(g[ni][nj] && visited[ni][nj]!=ans) dfs(ni, nj, ans); } } int solve(int sum) { int ans=0; while(sum) { ans++; queue<M> mq; while(!q.empty()) { int curR = q.front().r; int curC = q.front().c; q.pop(); int cnt = 0; for(int k=0; k<4; k++) { int nr = curR + dr[k]; int nc = curC + dc[k]; if(!g[nr][nc]) cnt++; } mq.push((M){curR, curC, cnt}); } while(!mq.empty()) { int curR = mq.front().r; int curC = mq.front().c; int cnt = mq.front().cnt; mq.pop(); if(g[curR][curC] > cnt) { q.push((P){curR, curC}); g[curR][curC] -= cnt; sum -= cnt; } else { sum -= g[curR][curC]; g[curR][curC] = 0; } } int cnt=0; for(int i=0; i<r; i++) { for(int j=0; j<c; j++) { if(g[i][j] && visited[i][j]!=ans) { cnt++; dfs(i, j, ans); if(cnt == 2) return ans; } } } } return 0; } int main() { scanf("%d%d", &r, &c); int sum = 0; for(int i=0; i<r; i++) { for(int j=0; j<c; j++) { scanf("%d", &g[i][j]); if(g[i][j]) q.push((P){i, j}); sum += g[i][j]; } } printf("%d\n", solve(sum)); } | cs |
>> 1년전엔 그렇게나 틀렸는데, 이번엔 바로 풀었다. (한번 틀렸는데, 문제 이해를 잘못해서...)
>> 빙산을 일단 q에 담고, 주변에 바다가 얼마나 둘러싸여있는지 mq 에 담은 다음, 녹인다. 그리고 섬이 분리가 되었는지 확인한다.
[4179] 불! : http://boj.kr/4179
'Tutoring > PS' 카테고리의 다른 글
| Week 1 - DP1 (0) | 2018.06.26 |
|---|---|
| Week 6 - BFS (숨박꼭질) (0) | 2018.03.30 |
| Week 5 - BFS (0) | 2018.03.24 |
| Week 4 - BFS (0) | 2018.03.11 |
| Week3 - DFS (0) | 2018.03.07 |
Week 2-2 : ArrayList
< 숙제 Review >
- common(n) : 양의 정수 n에 대해여 3자리 마다 콤마를 찍어 출력하는 함수.
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> void comma(int n) { if(n/1000 == 0) { printf("%d", n); return ; } comma(n/1000); printf(",%03d", n%1000); } int main() { int n; scanf("%d", &n); if(n < 0) { printf("-"); n = -n; } comma(n); return 0; } | cs |
- n-3 자리에 대해 콤마를 찍고 출력한 다음, 콤마를 찍고 나머지 세자리를 출력하면 된다.
- %03d : 3자리 확보, 빈자리는 0으로..!!
- 음수에 대한 예외처리는 19번 라인처럼 하면 될 것 같다.
< Tutoring >
- ArrayList
1) 구조체를 이용한 ArrayList 모델링하기.
1 2 3 4 5 6 | #define MAX 100 typedef struct { int list[MAX]; int len; } ArrayList; | cs |
>> 멤버 len 은 배열에 들어있는 데이터의 갯수..!!
2) init() 를 통한 초기화
1 2 3 4 | void init(ArrayList *plist) { plist->len = 0; } | cs |
>> C++ 에서 객체 생성시 생성자의 역할을 한다고 보면 된다.
>> 처음에 무엇을 초기화 해야할지 고민해보자..!
3) isEmpty(), isFull() 함수.
1 2 3 4 5 6 7 8 9 | int isEmpty(ArrayList *plist) { return plist->len == 0; } int isFull(ArrayList *plist) { return plist->len == MAX; } | cs |
>> 배열 요소의 갯수가 0개면 비어있는 상태.
>> len 의 갯수가 MAX 개면 가득 찬 상태..!!
4) 특정 위치에 데이터 삽입
1 2 3 4 5 6 7 8 9 10 | void add(ArrayList *plist, int pos, int data) { if(isFull(plist)) return ; if(!(0 <= pos && pos <= plist->len)) return ; for(int i=plist->len-1; i>=pos; i--) plist->list[i+1] = plist->list[i]; plist->list[pos] = data; plist->len++; } | cs |
>> 3 : 데이터가 가득차있으면 삽입 불가능.
>> 4 : 컨트롤 할 수 있는 인덱스의 범위를 벗어나면 삽입 불가능.
>> 6, 7 : 데이터를 중간에 삽입하는 경우, 삽입할 위치의 데이터부터 마지막 데이터까지 한칸씩 뒤로 밀어야 한다.
>> 데이터를 뒤로 한칸씩 옮길때는 마지막 데이터부터 옮겨야 한다. (값의 복사)
>> 8 : 원하는 위치에 데이터를 저장하는 코드.
>> 9 : 데이터를 삽입햇으므로 갯수 증가시키기.
5) 특정 위치의 데이터 삭제.
1 2 3 4 5 6 7 8 9 10 11 12 | int del(ArrayList *plist, int pos) { int ret; if(isEmpty(plist)) return -9999; if(!(0 <= pos && pos < plist->len)) return -9999; ret = plist->list[pos]; for(int i=pos; i<plist->len-1; i++) plist->list[i] = plist->list[i+1]; plist->len--; return ret; } | cs |
>> 5 : pos <= plist->len 이 아니다. 등호(=)가 빠져야 한다..!!
>> 8, 9 : 값을 왼쪽으로 한칸씩 옮긴다. 마지막 위치의 데이터는 신경안써도 된다.
>> plist->len 을 통해 유효한 데이터의 위치를 계산할 수 있다..!!
'Tutoring > 18-1 DS' 카테고리의 다른 글
| Week 3-2 : Linked List (0) | 2018.04.15 |
|---|---|
| Week 3-1 : Linked List (0) | 2018.04.11 |
| 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 1-1 : C Lang review (0) | 2018.03.28 |
Week 03
< 180404 >
1) 과제풀이.
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> int main() { int t, s; int bits, bytes; scanf("%d%d", &t, &s); bits = 2 * t * s * 4000; bytes = bits/8; return 0; } | cs |
>> 7 : scant() 에서 %d 는 10진수 정수를 입력받기 위한 서식문자.
>> 7 : &변수명 인 경우, &는 변수의 주소를 반환해주는 연산자..!!
2) %d 와 %c ..
- 숫자를 입력하고, 엔터를 친 다음, 문자를 입력하고 엔터를 쳤을때, 어떤 결과를 원한다.
- 아래 코드의 문제점은..??
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <stdio.h> int main() { int n; char ch; scanf("%d", &n); scanf("%c", &ch); printf("%d %c\n", n, ch); printf("End\n"); return 0; } | cs |
>> 숫자를 입력하고 엔터를 치면, 해당 숫자는 n에 저장되는데,
다음에 문자를 치기전에 쳤던 엔터도 문자로 인식이 되어 %c 에 저장이 된다.
- 해결책 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int main() { int n; char ch; scanf("%d", &n); getchar(); scanf("%c", &ch); printf("%d %c\n", n, ch); printf("End\n"); return 0; } | cs |
>> 스캔에프 사이에 getchar() 을 추가한다. 이유가 궁금하면 검색을...
getchar() 을 검색하기전에 '입력버퍼' 라는 것에 대해 검색을 먼저 해보자.
- 해결책2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <stdio.h> int main() { int n; char ch; scanf("%d", &n); scanf(" %c", &ch); printf("%d %c\n", n, ch); printf("End\n"); return 0; } | cs |
>> 9 : "%c" 를 " %c" 라 바꿧다. 즉 빈칸이 엔터키를 포함시켜, 정상적으로 문자를 입력받을 수 있게된다.
>> 이 원리가 궁금하면 스캔에프 사용법에 대해 검색을 해보자..
>> 해결책 2를 권함..^^
3) 입력 프롬프트에서 1을 입력했다. 프로그램은 이 1이란 것을 숫자 1인지, 문자 '1' 인지 어떻게 구분을 하여 저장을 할까??
1 2 3 | scanf("%d", &n); scanf("%c", &ch); | cs |
>> 서식문자를 무엇으로 지정했는지에 따라 구분이 가능하다.
4) 10진수 정수를 입력받아, 8진수, 16진수로 출력하기. 문자를 입력받아 그 문자의 아스키코드값 출력하기
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 n; char ch; scanf("%d", &n); printf("10진수: %d\n", n); printf("8진수: %o\n", n); printf("16진수: %x\n", n); printf("\n"); scanf(" %c", &ch); printf("%c의 ASCII 코드값: %d\n", ch, ch); return 0; } | cs |
>> 실행결과
1 2 3 4 5 6 7 | 10 10진수: 10 8진수: 12 16진수: a A A의 ASCII 코드값: 65 | cs |
5) 10진수 vs 8진수 vs 10진수
10진수 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
8진수 : 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 ...
16진수 : 1 2 3 4 5 6 7 8 9 10 A B C D E F G 10 ...
6) 4자리 정수(1000 ~ 9999) 까지의 정수를 입력받았을 때, 이를 거꾸로 출력해보기.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> int main() { int n, res; scanf("%d", &n); res = n%10; n /= 10; res = res*10 + n%10; n /= 10; res = res*10 + n%10; n /= 10; res = res*10 + n%10; printf("%d\n", res); return 0; } | cs |
>> 1234 를 입력하면, 4321 이 출력된다.
>> 8 : res 에는 4가 저장된다.
>> 9 : n 에는 123 이 들어있다.
>> 11 : res 에는 43 이 저장된다.
>> 12 : n 에는 12 가 저장된다.
>> 14 : res 에는 432 가 저장된다.
>> 15 : n 에는 1 이 저장된다.
>> 17 : res 에는 4321 이 저장된다.
7) 증감 연산자. a++ vs ++a
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include <stdio.h> int main() { int a, b, c; a = 5; b = a++; c = ++a + b++; printf("%d %d %d\n", a, b, c); return 0; } | cs |
>> 실행결과 : 7 6 12
>> 8라인이 끝나기 전에는 a에는 5가, b에도 5가 저장되어 있다.
>> 8라인이 끝나고 나서야 a에 값이 6으로 증가한다.
>> 9번 라인이 끝나기 전에는 a는 1이 증가한 7이, b에는 5가, c에는 그 둘의 합인 12가 저장된다.
>> 9번 라인이 끝나고 나서야 b의 값은 1이 증가하여 6이된다.
>> 그렇기 때문에 10라인에서 최종적으로 7 6 12 라는 결과가 출력된다.
8) scanf() 에서의 서식문자 %lf vs %f
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> int main() { float 키1, 키2, 키3, 키4; char 혈1, 혈2, 혈3, 혈4; printf("학생1의 키와 혈액형:"); scanf("%f %c", &키1,&혈1); printf("학생2의 키와 혈액형:"); scanf("%f %c", &키2, &혈2); printf("학생3의 키와 혈액형:"); scanf("%f %c", &키3, &혈3); printf("학생4의 키와 혈액형:"); scanf("%f %c", &키4, &혈4); printf("평균 키:%.1lf\n", (키1 + 키2 + 키3 + 키4) / 4); 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 | #include <stdio.h> int main() { double 키1, 키2, 키3, 키4; char 혈1, 혈2, 혈3, 혈4; printf("학생1의 키와 혈액형:"); scanf("%f %c", &키1,&혈1); printf("학생2의 키와 혈액형:"); scanf("%f %c", &키2, &혈2); printf("학생3의 키와 혈액형:"); scanf("%f %c", &키3, &혈3); printf("학생4의 키와 혈액형:"); scanf("%f %c", &키4, &혈4); printf("평균 키:%.1lf\n", (키1 + 키2 + 키3 + 키4) / 4); 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 | #include <stdio.h> int main() { double 키1, 키2, 키3, 키4; char 혈1, 혈2, 혈3, 혈4; printf("학생1의 키와 혈액형:"); scanf("%lf %c", &키1,&혈1); printf("학생2의 키와 혈액형:"); scanf("%lf %c", &키2, &혈2); printf("학생3의 키와 혈액형:"); scanf("%lf %c", &키3, &혈3); printf("학생4의 키와 혈액형:"); scanf("%lf %c", &키4, &혈4); printf("평균 키:%.1lf\n", (키1 + 키2 + 키3 + 키4) / 4); return 0; } | cs |
>> 원하는 결과가 출력될 것이다.
>> 결론 : scarf() 에서의 서식문자 %lf 는 double 형 변수에 , %f 는 float 형 변수에 맞는 서식문자이다.
9) 기타
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> int main() { int a=20, b=10; a = a+b; a += b; a = a-b; a -= b; a = a*b; a *= b; a = a/b; a /= b; return 0; } | cs |
>> 7, 8과 10, 11과 13, 14와 16, 17은 같은 연산이다.
- printf() 함수를 통해 %를 출력하고 싶으면 %% 를 써야한다.
1 2 3 4 5 6 7 | #include <stdio.h> int main() { printf("%d%%\n", 10); return 0; } | cs |
>> 실행결과 : 10%
Week 2-1 : How to code Recursive function2
<180403>
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 | #include <stdio.h> int max; int f2(int arr[], int n) { int k; if(n == 1) { max = arr[n] > arr[n-1] ? arr[n] : arr[n-1]; return arr[n] > arr[n-1] ? arr[n-1] : arr[n]; } k = f2(arr, n-1); if(arr[n] < k) return k; if(arr[n] > max) { int t=max; max=arr[n]; return t; } return arr[n]; } int main() { int arr[] = {50, 10, 2, 30, 11, 33}; printf("%d\n", f2(arr, 5)); return 0; } | cs |
>> n 은 마지막 인덱스
>> 12 : k 에는 n-1번째 요소들까지에서의 두번째 최대값이 저장된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <stdio.h> #include <string.h> int isP(char str[], int s, int e) { if(s >= e) return 1; return str[s]==str[e] ? isP(str, s+1, e-1) : 0; } int main() { char str[100]; scanf("%s", str); isP(str, 0, strlen(str)-1) ? puts("True") : puts("False"); return 0; } | cs |
>> 첫번째 인덱스와 마지막 인덱스의 문자가 같을때, 그 안의 문자열이 팰린드롬이면 팰린드롬이다.
>> noon, eye, 다시합창합시다 와 같은 문자열은 모두 팰린드롬이다.
3) 하노이 타워 이동 순서.
- Hanoi(n, from, by, to) : n개의 쟁반을 from 에서 by를 거쳐 to로 옮기는 과정을 출력하는 함수.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <stdio.h> void Hanoi(int n, char from, char by, char to) { if(n == 1) { printf("%d번 쟁반을 %c에서 %c로 이동.\n", n, from, to); return ; } Hanoi(n-1, from, to, by); printf("%d번 쟁반을 %c에서 %c로 이동.\n", n, from, to); Hanoi(n-1, by, from, to); } int main() { Hanoi(3, 'A', 'B', 'C'); return 0; } | cs |
>> A 에 있는 n 개의 쟁반을 C에 옮기려고 함.
>> A 에 있는 n개의 쟁반들 중, n-1개의 쟁반을 B에 옮기고,
>> A 에 있는 n번째 쟁반을 C로 옮긴다.
>> 그런다음 B 에 옮겨놨던 n-1개의 쟁반을 C로 옮기면 된다.
>> A 에 있는 쟁반들 중, n-1개의 쟁반을 B에 옮기는 과정을 출력하고,
>> A 에 있는 n번째 쟁반을 C로 옮긴다.
>> 그런다음 B 에 옮겨놨던 n-1개의 쟁반을 C로 옮기는 과정을 출력한다.
>> 실행결과
1 2 3 4 5 6 7 | 1번 쟁반을 A에서 C로 이동. 2번 쟁반을 A에서 B로 이동. 1번 쟁반을 C에서 B로 이동. 3번 쟁반을 A에서 C로 이동. 1번 쟁반을 B에서 A로 이동. 2번 쟁반을 B에서 C로 이동. 1번 쟁반을 A에서 C로 이동. | cs |
4) 별찍는 순서.
4-1)
1 2 3 4 5 6 7 | void f(int n) { if(n == 0) return ; f(n-1); printf("*"); f(n-1); } | cs |
4-2)
1 2 3 4 5 6 7 | void f(int n) { if(n == 0) return ; f(n-1); f(n-1); printf("*"); } | cs |
4-3)
1 2 3 4 5 6 7 | void f(int n) { if(n == 0) return ; printf("*"); f(n-1); f(n-1); } | 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 1-2 : How to code Recursive function (0) | 2018.03.30 |
| Week 1-1 : C Lang review (0) | 2018.03.28 |
Week 6 - BFS (숨박꼭질)
<180331>
Week 6 - BFS
[12851] 숨박꼭질2 (http://boj.kr/12851)
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 | c#include <cstdio> #include <queue> using namespace std; const int MAX = 100001; int main() { int n, k; scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[MAX]={0}; int ok=0, ans=-1, cnt=0; while(!q.empty()) { int sz = q.size(); ans++; for(int i=0; i<sz; i++) { int cur = q.front(); q.pop(); visited[cur] = 1; if(cur == k) { ok = 1; cnt++; continue; } int next = cur+1; if(next < MAX && !visited[next]) { q.push(next); } next = cur-1; if(0 <= next && !visited[next]) { q.push(next); } next = cur*2; if(next < MAX && !visited[next]) { q.push(next); } } if(ok) break; } printf("%d\n%d\n", ans, cnt); } | cs |
>> 방문체크를 꺼내면서 해야한다.
>> ans 는 트리에서 레벨수회를 할 때 그 레벨을 세는 역할을 한다고 생각하면 될 것 같다.
[13529] 숨박꼭질3 (http://boj.kr/13549)
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 <cstdio> #include <queue> using namespace std; const int MAX = 100001; int main() { int n, k; scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[MAX]={0}; visited[n] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); int next = cur+1; if(next < MAX && (!visited[next] || visited[next]>visited[cur]+1)) { q.push(next); visited[next] = visited[cur]+1; } next = cur-1; if(0 <= next && (!visited[next] || visited[next]>visited[cur]+1)) { q.push(next); visited[next] = visited[cur]+1; } next = cur*2; if(next < MAX && (!visited[next] || visited[next]>visited[cur])) { q.push(next); visited[next] = visited[cur]; } } printf("%d\n", visited[k]-1); } | cs |
>> 정답이 언제든 갱신될 수 있다고 생각했다. 그래서 다 돌리고 난 뒤에 저장되어 있는 값이 정답이라고 생각한 것을 코드로 옮겼다.
>> 다음에 방문할 위치가 현재위치보다 적은 시간에 방문할 수 있다면 다시 방문해야한다.
[13913] 숨박꼭질4 (http://boj.kr/13913)
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 <queue> using namespace std; const int MAX = 100001; int n, k, from[MAX]; void trace(int cur) { if(cur == n) { printf("%d", cur); return ; } trace(from[cur]); printf(" %d", cur); } int main() { scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[MAX]={0}; visited[n] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); int next = cur+1; if(next < MAX && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; from[next] = cur; if(cur == k) break; } next = cur-1; if(0 <= next && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; from[next] = cur; if(cur == k) break; } next = cur*2; if(next < MAX && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; from[next] = cur; if(cur == k) break; } } printf("%d\n", visited[k]-1); trace(k); } | cs |
>> from 배열에 주목하자.
>> from[next] = cur; 은 next 의 이전 위치는 cur 이란 뜻이다.
'Tutoring > PS' 카테고리의 다른 글
| Week 1 - DP1 (0) | 2018.06.26 |
|---|---|
| Week 7 - DFS+BFS (0) | 2018.04.07 |
| Week 5 - BFS (0) | 2018.03.24 |
| Week 4 - BFS (0) | 2018.03.11 |
| Week3 - DFS (0) | 2018.03.07 |
