week2: 그래프 탐색

[Taehyeon-Kim]

• a 2178 미로탐색
• b 1012 유기농배추
• c 2468 안전영역
• d 2583 영역 구하기
• e 1992 쿼드트리
• f 2828 사과담기
• g 2910 빈도정렬
• h 4659 비밀번호 발음하기
• i 2870 수학숙제
• 10709 https://www.acmicpc.net/problem/10709
• 3474 https://www.acmicpc.net/problem/3474
• 2852 https://www.acmicpc.net/problem/2852
• 1436 https://www.acmicpc.net/problem/1436
• 9012 https://www.acmicpc.net/problem/9012
• 4949 https://www.acmicpc.net/problem/4949
• 14502 https://www.acmicpc.net/problem/14502 - 연구소
• 2636 https://www.acmicpc.net/problem/2636 - 치즈
• 1068 https://www.acmicpc.net/problem/1068 - 트리
• 1325 https://www.acmicpc.net/problem/1325
• 17298 https://www.acmicpc.net/problem/17298 - 오큰수

[Taehyeon-Kim]

sw

• 감시
  cctv끼리 통과할 수 없다라는 문장이 없었는데도 불구하고 내맘대로 해석해서 풀이 작성 -> 이 부분때문에 디버깅만 30분 이상 소요

[Taehyeon-Kim]

3474

팩토리얼 결과로 나온 수의 0의 개수를 구하라

1. 어떻게 0의 개수를 구하나?
2. 자릿수마다 0을 체크하기에는 10억 팩토리얼의 수가 너무 큼(완전탐색 불가)
3. 숫자를 적어봐라 ex. 5400
4. 5400의 구성은 어떠한가? 작은 조합으로 분해해보기
5. 54 * 10 * 10
6. 10의 개수가 2개네? -> 10의 개수가 결국 0의 개수 -> 10은 2와 5로 이루어져 있음
7. 2의 개수와 5의 개수를 체크하면 되겠네?
8. 예를 들어서 10! 이라면
9. 1 2 3 4 5 6 7 8 9 10 까지 2의 개수는 몇 개인가?
10. 2 : 5개 , 4 : 2개, 8 : 1개
11. 2의 제곱수를 파악하면 됨
12. 5로 이루어진 수가 더 작기 때문에 짝을 맞추려면 5가 몇개로 이루어져 있는지만 파악하면 됨

수에 대한 감각이 없으면 아이디어를 떠올리기 어려울 것 같다.

1. 문제를 많이 풀어보거나
2. 관찰을 여러 방면으로 해보거나 -> 항상 가장 작은 단위로 쪼개보고, 조합해보고 해보는 습관이 필요할 것 같다.

[Taehyeon-Kim]

2852 nba 농구

큐
타임 체크
https://muker.tistory.com/470

[Taehyeon-Kim]

17298 오큰수

플로우가 정리 안되는 느낌이었음
다시 한번더 풀어봐야할듯

• 무지성 - 2중 for문까지는 생각했는데 stack을 못 떠올림
• 한방향으로 한번만 탐색하는 것까지도 생각함

[Taehyeon-Kim]

1068 트리

• dfs가 떠올랐다.
• 딕셔너리와 카운트 배열을 만들어서 해결하려고 했는데 루트만 남겨졌을 때의 처리를 하지 못했다.
• 리프노드라는 것이 자식 노드가 없다는 의미인데, 직접 노드를 제거하는 것이 아니라 특정 노드에서의 탐색을 하지 않는다면 나머지 서브 트리의 노드들도 탐색을 진행하지 않기 때문에 재귀 수행 중에 커트를 해주면 원하는대로 동작을 하게 된다.