DP, 누적합 문제https://www.acmicpc.net/problem/2560 접근 방식 문제를 단순화해서 생각해보자.우리가 구해야하는 값은 N일째 되는 날 살아있는 짚신벌레 수(를 1000으로 나눈 나머지)이다.그러면 dp에 무슨 값을 기록해야할까 ? -> for문을 N번 돌며 dp[i]에 i일에 살아있는 짚신벌레 수를 기록하자.참조해야 하는 배열 없이, 이전 dp 배열에 기록했던 짚신벌레 수를 활용하여 현재 dp 배열의 값(현재 i일째에 살아있는 짚신벌레 수)를 구할 수 있다.dp[i]는 i일째 되는 날에 살아있는 짚신벌레의 수💡 풀이코드 (성공)import sys a, b, d, N = map(int, sys.stdin.readline().split())def sol(a, b, d, N): ..

DP, 누적합 문제https://www.acmicpc.net/problem/2616 이 문제는 냅색 알고리즘의 변형으로도 볼 수 있을 것 같다.누적합을 저장해준 (1차원) 배열을 만들고, 해당 배열을 활용하여 소형 기관차 3대로 최대 운송할 수 있는 손님수를 구하는 문제이다. 초기 접근 방식객차의 수, 소형 기관차가 최대로 끌 수 있는 객차의 수, 소형 기관차의 갯수(3)에 대한 정보가 주어졌다.처음에 이 문제를 보고 DP로 풀어야겠다고 생각했다. 그러나 초기에는 r = 소형 기관차가 최대로 끌 수 있는 객차의 수, c = 객차의 수에 대한 DP 배열의 형태를 구상하였기에 문제가 생각보다 쉽게 풀리지 않았다.3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다. 여기서 "최대"라는 말에 포커스..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/21736 💡 풀이코드 (성공 - DFS 1)import sys sys.setrecursionlimit(10 ** 9) r, c = map(int, sys.stdin.readline().split())graph = []start = []visited = [[False] * c for _ in range(r)]dy = [0, -1, 0, 1]dx = [1, 0, -1, 0]cnt = 0for i in range(r): l = list(sys.stdin.readline().strip()) for j in range(c): if l[j] == "I": start.append((i,..

DP / Knapsack 문제https://www.acmicpc.net/problem/7579 냅색(Knapsack) 알고리즘간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.출처: 위키피디아 냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)해당 문제는 0-1 배낭문제의 경우다.  일반적인 배..

DP / Knapsack 문제https://www.acmicpc.net/problem/12865  냅색(Knapsack) 알고리즘 냅색 알고리즘은 대표적인 동적 계획법(DP) 문제 중 하나로, 주어진 가방에 담을 수 있는 무게 제한과 각 물건의 가치를 고려하여 최대한의 가치를 얻는 문제다. 이 알고리즘은 크게 두 가지 유형으로 나뉜다. 1. 분할 가능한 배낭 문제 (Fractional Knapsack): 물건을 부분적으로 쪼개어 담을 수 있는 경우에 해당한다.각 물건의 가치를 무게로 나눈 값(즉, 무게 대비 가격 비율)을 기준으로 물건을 정렬하여 높은 비율 순서대로 가방에 담는다.가방의 남은 용량보다 물건의 무게가 크다면, 물건을 잘라서 넣는다. 이렇게 하면 쉽게 최대 가치를 얻을 수 있다.2. 0-1 ..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/1967 트리의 지름 트리의 지름이란?어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말한다.즉, 트리의 지름이란 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다.위의 그래프에서 9 노드와 12 노드의 사이의 거리는 45이며, 이 경로가 트리의 지름이 된다. 트리의 지름을 구하는 순서1. DFS를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.2. DFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.  💡 풀이코드 (성공 - DFS)# DFS# visited 초기화 주의 im..