난이도 : 실버5 ~ 골드1 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 3시간 1. 11725번 트리의 부모 찾기 (난이도 : 실버2, 유형 : 그래프 탐색, 정답 : O) 2. 22860번 폴더 정리 (난이도 : 골드3, 유형 : 구현, 정답 : O) 3. 15661번 링크와 스타트 (난이도 : 실버1, 유형 : 완전 탐색, 정답 : O) 4. 14391번 종이 조각 (난이도 : 골드3, 유형 : 완전 탐색, 정답 : X) 트리의 부모 찾기 그래프 탐색 문제, A 노드에서 B 노드로 탐색할경우 B 노드의 부모는 A 노드가 된다. import java.util.*; import java.lang.*; import java.io.*; public class Ma..
난이도 : 실버3 ~ 골드3 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 3시간 1. 2285번 우체국 (난이도 : 골드4, 유형 : 그리디, 정답 : △) 2. 21608번 상어초등학교 (난이도 : 골드5, 유형 : 구현, 정답 : O) 3. 9465번 스티커 (난이도 : 실버1, 유형 : DP, 정답 : △) 4. 11725번 트리의 부모 찾기 (정답 : X) 우체국 좌우 인원의 차가 0에 가까운 마을에 우체국을 지으면 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우게 된다. import java.util.*; import java.lang.*; import java.io.*; public class Main { public static voi..
난이도 : 실버3 ~ 골드3 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 3시간 1. 백준 16932번 모양만들기 (난이도 : 골드3, 유형 : 그래프 탐색, 정답 : O) 2. 백준 2800번 괄호제거 (난이도 : 골드5, 유형 : 브루트포스·스택, 정답 : △) 3. 백준 2285번 우체국 (정답 : X) 4. 백준 11725번 트리의 부모 찾기 (정답 : X) 모양만들기 N X M 크기의 배열에서 0인 칸 하나를 1로 만들어서 제일 많이 연결된 1의 수를 구하는 문제이다. 무식한 방법으로 모든 0인 칸을 각각 1로 만들어 그래프 탐색하는 방법이 있지만 그랬다간 시간 초과날게 뻔했다. 한번의 그래프 탐색으로 이 문제를 해결할 순 없을까? 부분 그래프를 그룹으..
난이도 : 실버3 ~ 골드3 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 : 3시간 1. 백준 1106번 호텔 (난이도 : 골드 5, 유형 : DP, 정답 : O) 2. 백준 14620번 꽃길 (난이도 : 실버 2, 유형 : 완전탐색, 정답 : △) 3. 백준 22944번 죽음의 비 (정답 : X) 4. 백준 22868번 산책 (정답 : X) 호텔 문제를 보고 최적 부분 구조를 파악할 수 있었다. X명을 구하는데 드는 최소 비용은 1명과 X-1명을 구하는데 드는 최소 비용, 2명과 X-2명을 구하는데 드는 최소 비용, ··· 중의 최소값이다. 따라서 DP를 적용했고 구현의 편의성을 위해 Bottom-up 방식으로 1명, 2명, ···, X명을 구하는데 드는 최소..
난이도 : 실버 3 ~ 골드 3 유형 : 브루트포스, DP, 그리디, 구현, BFS/DFS 시간 : 2시간 30분 1. 백준 14719번 빗물 (난이도 : 골드 5, 유형 : 구현, 정답 : O) 2. 백준 8980번 택배 (난이도 : 골드 2, 유형 : 그리디, 정답 : O) 3. 백준 14500번 테트로미노 (난이도 : 골드 5, 유형 : 브루트포스, 정답 : △) 4. 백준 22868번 산책 (정답 : X) 빗물 문제를 보고 구현 문제임을 바로 파악할 수 있었다. 어떤 칸이 빗물에 고일려면 아래의 조건을 만족해야 한다. 아래 칸이 막혀야함 (아래칸이 블록이거나 빗물에 고여있거나 맨밑이어야함) 왼쪽과 오른쪽이 막혀야함 (해당 칸을 기준으로 왼쪽과 오른쪽이 블록이어야함) 아래 칸이 막혔는지는 바로 알 ..
난이도 : 실버 3 ~ 골드 3 유형 : 브루트포스, DP, 그리디, 구현, BFS/DFS 시간 : 2시간 1. 백준 15486번 퇴사 2 (난이도 : 골드3, 유형 : DP, 정답 : △) 2. 백준 17276번 배열 돌리기 (난이도 : 실버2, 유형 : 구현, 정답 : △) 3. 백준 14500번 테트로미노 (정답 : X) 4. 백준 22868번 산책 (정답 : X) 퇴사 2 Top-down 방식으로 풀었다가 시간 초과가 발생했다. 나중에 찾아보니 Bottom-up 방식으로 풀어야되는 문제였다. 문제를 보고 최적 부분 구조가 보였고 DP 문제임을 알 수 있었다. import java.io.*; import java.util.*; public class Main { public static void m..
난이도 : 실버 3 ~ 골드 3 유형 : DP, 브루트포스, 그리디, 구현, BFS/DFS 시간 : 3시간 1. 백준 16508번 전공책 (난이도 : 실버3, 유형 : 브루트포스, 정답 : ○) 2. 백준 21314번 민겸수 (난이도 : 실버2, 유형 : 그리디, 정답 : △) 3. 백준 15486번 퇴사 2 (정답 : X) 4. 백준 14500번 테트로미노 (정답 : X) 전공책 각 전공책을 선택할 것인지에 따라 최대 2의 16승 만큼의 경우의 수가 발생하므로 완전 탐색을 적용할 수 있었다. 각 경우를 탐색해 원하는 단어를 만들 수 있는 경우의 수에서 발생하는 비용 중 최소 비용을 출력한다. import java.lang.*; import java.util.*; import java.io.*; publ..
