문제집: 단기간 성장
1.백준 문제집: 단기간 성장
index 페이지입니다.
2.백준 #12865 평범한 배낭 (파이썬) : 0-1 배낭 문제
0-1 배낭 문제. 이 알고리즘도 다익스트라, 플로이드-워셜처럼 외우자!
3.백준 #1655 가운데를 말해요 (파이썬)
중위값을 최대 힙, 최소 힙 두개로 구하는 참신한 방법
4.백준 #3197 백조의 호수 (파이썬)
완전히 똑같은 맵에서 BFS를 여러번 해야 한다면... 이전에 했던 정보를 버리지 마라! 언뜻 짜면서 컴퓨터가 같은 짓을 여러번 할 것이라는 생각이 든다면, 반드시 시간 초과가 나는 알고리즘이다.
5.백준 #11401 이항 계수 3 (파이썬) : 페르마의 소정리
"1,000,000,007으로 나눈 나머지"의 의미를 드디어 알았다!
6.백준 #10830 행렬 제곱 (파이썬)
행렬 곱셈 알고리즘, 분할 정복을 이용한 행렬 제곱 알고리즘
7.백준 #2933 미네랄 (파이썬)
해설 거의 안 보고 풀었다. 엣지 케이스가 좀 있어서 푸는데 시간 꽤 걸렸지만 뿌듯하다.
8.피보나치 수를 구하는 여러가지 방법 (파이썬)
이 글은 Baekjoon, 피보나치 수를 구하는 여러가지 방법 게시글을 이해해보려 작성하였습니다. 원 게시글이 C/C++로 작성되어 있어서, 필자의 코딩테스트 주력 언어인 Python으로 바꾸어보았습니다.
9.백준 #11404 플로이드 (파이썬)
생각할 것도 없고, 그냥 플로이드-워셜 알고리즘을 쓰기만 하면 통과할 수 있다.
10.백준 #1956 운동 (파이썬)
플로이드-워셜에서 대각성분 값을 INF 그대로 두고 시작하면, 끝났을 때 담긴 값은 0이 아니라 사이클 값이 된다~
11.백준 #17404 RGB거리 2 (파이썬)
RGB거리 1과 dp 알고리즘은 똑같다.
12.백준 #2482 색상환 (파이썬)
경우의 수를 dp 배열의 값으로 만들 수도 있구나... 생각을 유연하게!
13.백준 #12886 돌 그룹 (파이썬)
돌 세 무더기라서 약간 헷갈릴 법 하다.
14.백준 #11779 최소비용 구하기 2 (파이썬)
아주 전형적인 다익스트라 문제다. 하지만 최단 비용만 출력하는 게 아니라 그때의 경로를 함께 출력해야 하므로 추가 변수가 필요하다.
15.백준 #1167 트리의 지름 (파이썬)
트리에서 아무 정점이나 잡고, dfs/bfs를 통해 가장 먼 비용을 갖는 정점을 찾아낸다면, 그 정점은 반드시 트리의 지름을 이루는 정점 중 하나가 된다.
16.백준 #2263 트리의 순회 (파이썬)
포스트오더와 인오더 출력값을 가지고 프리오더를 구할 수 있다니?!
17.백준 #1717 집합의 표현 (파이썬) : Union-Find(합집합 찾기)
Class 5 깨기 시작! Class 5 중에 가장 만만한 Union-Find를 배워보자. 정말 쉽다.
18.백준 #1197 최소 스패닝 트리 (파이썬) : 크루스칼 알고리즘
드디어 최소 스패닝 트리를 배웠다. 이번 글에서는 가장 대중적인 방식인 Kruskal Algorithm을 활용한다.
19.백준 #11657 타임머신 (파이썬)
전형적인 벨만-포드 알고리즘 문제