Problem Solving 썸네일형 리스트형 BOJ 14728 - 벼락치기 문제 링크https://www.acmicpc.net/problem/14728 문제 해결 1. 공부 시간이 한정되어있으므로, 모든 과목을 공부할 수 없다. 2. 현재 과목을 공부했을 때와 하지 않았을 때를 모두 고려해야하므로, DP를 사용해서 문제를 해결한다. 3. DP[i][j] = i번 째 과목에서 j만큼 시간이 남았을 때의 최대 점수. 주의할 점 || 생각해볼 점 1. 공부 시간을 넘어가게 되면 답이 될 수 없는 큰 값을 return해준다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 14720 - 우유 축제 문제 링크https://www.acmicpc.net/problem/14720 문제 해결 1. DP[i][j] = i번 째 우유 상점이고, 이전에 j 우유를 먹었을 때의 최대 우유 개수. 2. 딸기 -> 초코 -> 바나나 -> 딸기 -> 초코 .... 이런 특정한 규칙을 지켜야 하므로 이전에 먹은 우유의 정보를 저장하고 있어야한다. 주의할 점 || 생각해볼 점 1. 시작은 딸기 우유이므로, 딸기 우유가 없으면 0을 출력해야 한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 4811 - 알약 문제 링크https://www.acmicpc.net/problem/4811 문제 해결 1. DP[i][j] = 온전한 알약 i개와 반쪽짜리 알약 j개가 있을 때의 문장의 경우의 수 주의할 점 || 생각해볼 점 1. 처음엔 DP를 이용하지 않고 그냥 완전탐색을 해서 시간초과가 났다. 2. 완전한 알약이 없거나, 하나만 있으면서 반쪽짜리 알약이 없다면 경우의 수는 한 가지다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 SW Expert Academy 1795 - 인수의 생일 파티 문제 링크 - 문제 해결 1. 단방향 그래프를 입력받고, 1부터 N까지의 임의의 점에서 K까지의 최단거리와 K부터 임의의 점까지의 최단거리의 합 중에서 가장 큰 값을 구하는 문제. 2. 다익스트라 알고리즘으로 문제 해결. 주의할 점 || 생각해볼 점 1. 최대 간선의 수(N)가 10,000개, 최대 정점의 수(M)가 1,000개. 1부터 N까지의 임의의 수 전부에서 최단거리를 구하려면 시간복잡도 에 의해서 아슬아슬해진다. 그러므로 입력 받을 때, 정방향과 반대방향 인접리스트를 두 개 만들어서 K에서 다익스트라 알고리즘을 두 번 수행하면 된다. 참고 - 다익스트라 알고리즘 visual code : https://www.swexpertacademy.com/main/visualcode/main.do#/home.. 더보기 BOJ 9465 - 스티커 문제 링크https://www.acmicpc.net/problem/9465 문제 해결 1. 스티커를 규칙에 맞춰서 뗄 때, 떼어낸 스티커의 점수 합의 최대값을 구해야한다. 2. DP[i][j] = 스티커 (i, j)에서 최대값. 주의할 점 || 생각해볼 점 1. 1열과 2열에서 시작한 값이 다르므로 두 번 탐색한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2186 - 문자판 문제 링크https://www.acmicpc.net/problem/2186 문제 해결 1. 임의의 칸에서 시작해서 상하좌우로 1~K만큼씩 움직일 때마다 만나는 문자를 차례로 이었을 때, 주어진 문자열과 같은 경우의 수를 구하는 문제. 2. DP[i][j][k] = 문자판 좌표 (i, j)에 있는 문자와 주어진 문자열 S의 S[k]와 같을 때의 경우의 수. 주의할 점 || 생각해볼 점 1. DP 테이블을 만들 때, k의 범위가 최대 80까지임을 간과하면, 많은 수의 "틀렸습니다"를 획득할 수 있다. 2. BFS, DFS 모두 해를 구할 수 있다. 하지만 BFS로 문제를 해결할 시 메모리 초과에 걸리게 되어서 DFS+DP로 구현했다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1915 - 가장 큰 정사각형 문제 링크https://www.acmicpc.net/problem/1915 문제 해결 1. 직사각형 내에서 1로 된 가장 큰 정사각형의 넓이를 구하는 문제. 2. DP[i][j] = (i, j)에서 가장 큰 정사각형의 한 변의 길이. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2157 - 여행 문제 링크https://www.acmicpc.net/problem/2157 문제 해결 1. 항로를 통해서 이동할 때, 이용할 수 있는 가장 큰 기내식 점수의 합을 구하는 문제. 2. DP[i][j] = i번 째 도시에서 j번 이동했을 때의 가장 큰 기내식 점수의 합. 주의할 점 || 생각해볼 점 1. 항상 도시의 숫자가 증가하는 방향으로 이동한다. 2. 시작 점도 이동 횟수에 포함되어 있다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1126 - 같은 탑 문제 링크https://www.acmicpc.net/problem/1126 문제 해결 1. 주어진 블럭을 사용해서 두 탑을 만들 때, 높이가 같으면서 가장 높게되는 높이를 구하는 문제. 2. DP[i][j] = i번 째 블럭을 사용하여 (탑1의 높이 - 탑2의 높이) = j가 되는 가장 높은 높이. 주의할 점 || 생각해볼 점 1. 블럭의 높이의 차를 인덱스로 사용하는 문제이므로, 높이의 차가 음수가 되서는 안된다. 2. 두 탑이 서로 자리가 바뀔 수 있으므로 값은 두 배가 나온다. 그러므로 2로 나눈 것이 답이 된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1937 - 욕심쟁이 판다 문제 링크https://www.acmicpc.net/problem/1937 문제 해결 1. 상하좌우를 움직여서 현재보다 증가하는 방향으로 나아가는 가장 긴 거리를 구하는 문제. 2. DP[i][j] = (i, j)에서 출발했을 때, 도달할 수 있는 가장 긴 거리. 주의할 점 || 생각해볼 점 1. 주로 한 방향으로 증가하는 문제만이 DP라고 생각하기 쉽기 때문에, 상하좌우 움직이는 이 문제에 대해서 DP를 생각하기 쉽지가 않다. 2. 하지만 어느 점에서 출발하든, (i, j)를 지나게되면 (i, j)로 부터 도달할 수 있는 최장 거리는 같게된다. 3. 만약 그냥 DFS만을 사용하게되면 의 시간이 소요된다.(정점의 개수를 N*N이라하고 전체 다 이동한다 생각하면 N*N만큼 이동할 수 있으므로) 참고 - ※.. 더보기 이전 1 2 3 4 5 6 ··· 9 다음