DP 문제https://www.acmicpc.net/problem/17404문제 요약1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.💡 풀이 코드 (실패 - 마지막 행을 0번째 행으로 옮겨 겹치지 않게 하는 코드)'''51 10 1001 10 1001 10 1001 10 1001 10 100출략 : 32정답 :122'''# 마지막 행을 0번째 행으로 옮겨 겹치지 않도록 하자.import sys n = int(sys.stdin.readline())graph = [[0] * 3 for _ in range(n + 1)]dp = [[0] * 3 for _ ..

DP 문제https://www.acmicpc.net/problem/1149 💡 풀이 코드 (성공)import sys n = int(sys.stdin.readline())graph = [[0] * 3 for _ in range(n + 1)]dp = [[0] * 3 for _ in range(n + 1)]for i in range(1, n + 1): graph[i][0], graph[i][1], graph[i][2] = map(int, sys.stdin.readline().split()) if i == 1: dp[i][0],dp[i][1],dp[i][2] = graph[i][0],graph[i][1],graph[i][2]def sol(n, graph): for i in ..

MST / BFS + 이진탐색 문제https://www.acmicpc.net/problem/1939최소 신장 트리(MST)란?개념connected, weighted, undirected(양방향 가중 그래프)에서 정의되며, 신장 트리 중에서 가중치의 합이 최소가 되는 신장 트리이다.즉, 그래프에서 모든 정점을 포함하면서, 간선들의 가중치 합이 최소가 되는 트리를 의미한다. 최소 신장 트리 (가중치 합 : 8) 구현 방식MST를 구현하기 위해선 두개의 그리디 알고리즘을 사용할 수 있다. 1) Prim's Algorithm다엑스트라와 비슷한 방식이다.Dijkstra는 최단 경로를 찾는 알고리즘Prim은 최소 신장 트리를 찾는 알고리즘 (MST)자료구조 heap을 활용하여 최소 신장이 되도록 노드를 방문하는 식..

누적합, 수학 문제https://www.acmicpc.net/problem/10986접근 방식이 문제는 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수(부분구간의 개수)를 구하는 것이다.부분구간의 개수를 구해야 하므로 투포인터 알고리즘을 잠깐 떠올렸으나 주어진 데이터의 앞뒤 연관성이 없기 때문에 다른 방법을 고안해냈다. 투포인터 알고리즘을 쓸 수 없는 이유1) 투포인터 알고리즘의 일반적인 사용 사례투포인터 알고리즘은 주로 다음과 같은 조건을 만족하는 경우에 사용된다.정렬된 배열: 배열이 정렬된 상태에서 특정 합을 찾는 문제.특정 조건을 만족하는 구간: 예를 들어, 구간의 길이 또는 합이 특정 조건을 만족하는 경우.단일 스캔: 한 번의 배열 스캔으로 문제를 해결할 수 있는 경우.2) 투포인터 ..

이분 탐색 문제https://www.acmicpc.net/problem/2512💡 풀이 코드 (성공)import sys n = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))amounts = int(sys.stdin.readline())def binary_search(n, arr, amounts): start = 1 end = max(arr) answer = 0 while start

이분 탐색 문제https://www.acmicpc.net/problem/2110문제 이해1. 요점문제의 요점은 다음과 같다.각 공유기 사이의 거리 및 간격이 최대가 되게끔 공유기 C개를 배치하라.즉, 공유기 C개를 각각 최대한 멀리 떨어뜨려라.이때 공유기 사이의 거리 및 간격이 각각 달라도 된다. 최대가 되게 공유기를 배치 후 이 중에서 최소값을 출력한다.결론적으로는 공유기들이 각각 최대한 멀리 떨어져 있어야 한다. 2. 예시9 31 2 3 4 5 6 7 8 100정답 : 7 (1 8 100)9 410 20 30 40 48 60 70 80 81정답 : 20 (10 30 60 80)9 41 2 3 4 5 6 7 15 100정답 : 6 (1 7 15 100)10 41 2 3 4 5 6 7 8 9 10정답 :..