Dev_Diary

https://www.acmicpc.net/problem/2749해당 문제는 '피사노 주기' 라는 개념을 알고 있다면 쉽게 풀 수 있습니다. Pisano period - WikipediaFrom Wikipedia, the free encyclopedia Period of the Fibonacci sequence modulo an integer Plot of the first 10,000 Pisano periods. In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken moen.wikipedia.org피사노 주기는 피보나치 수열의 주기에 관한..

https://www.acmicpc.net/problem/1707그래프 탐색 문제입니다.노드를 탐색하며 색을 칠해주는데, 연결된 노드가 현재 노드와 같은 색이면 이분 그래프가 아니라고 출력해주면 됩니다.다만 주의할 점은 노드가 모두 연결되어있지 않을 수 있다는 점 입니다.또 출력시 모든 문자가 대문자라는 점을 주의해야 합니다.import sysfrom collections import dequeinput = sys.stdin.readline def solution(V, E, edges): # 그래프 graph = [[] for _ in range(V+1)] for u, v in edges: graph[u].append(v) graph[v].append(u..

https://www.acmicpc.net/problem/16563소수 문제입니다.단순히 하나하나 구하기에는 시간초과가 발생하므로 다른 방법을 찾아야 합니다. 소인수분해 문제는 어떤 수 K 를 소수 P 로 나누는 것을 반복합니다. 예를 들어210 = 2 x (105)       = 2 x 3 x (35)       = 2 x 3 x 5 x 7으로 순차적으로 구할 수 있습니다. 이는 큰 과정을 작은 과정으로 나누어 구할 수 있다는 말이고 DP 를 사용할 수 있는 조건임을 말합니다. 우선 나누어줄 인자인 소수를 구해줍니다.범위는 주어진 수들 중 가장 큰 수의 제곱근 이하면 됩니다.해당 범위의 소수들로 나누어 떨어지지 않는다면 그 수는 소수이기 때문에 따로 처리해주면 됩니다. 구해진 소수를 순회하며 인수분해 ..

https://www.acmicpc.net/problem/1094비트마스킹 문제입니다.막대를 둘로 쪼개어 합친다는 발상 자체가 어떤 수를 이진법으로 나타내면 어떤 모습인가? 를 물어보는 것과 같습니다.즉 이진법으로 나타낸 수 에서 1 이 자른 막대 조각과 같다고 볼 수 있습니다.import sysinput = sys.stdin.readlinedef solution(X): print(bin(X)[2:].count('1'))# 입력X = int(input().strip())solution(X)

https://www.acmicpc.net/problem/18352다익스트라 문제입니다.다익스트라로 시작점에서 최단거리를 찾아주면 풀 수 있습니다.주의할 점이 있다면 시작 노드의 최단거리를 0 으로 시작하지 않으면 2 의 최단거리를 갖는 노드를 검색할 때 시작 노드도 포함될 수 있습니다.import sysimport heapq as hqinput = sys.stdin.readlinedef solution(N, M, K, X, edges): # 그래프 graph = [[] for _ in range(N+1)] for A, B in edges: graph[A].append(B) # 최단거리 목록 min_dists = [float('inf') for _ in range(..

https://www.acmicpc.net/problem/21924최소 스패닝 트리 문제입니다.최소 스패닝 트리의 특성상 노드 개수가 N-1 이 아니면 모든 노드가 연결되지 않았다는 것만 알면 간단하게 풀 수 있습니다.import sysinput = sys.stdin.readline# Union-Finddef Union(root_list, node_1, node_2): # 각 노드의 루트 root_node_1 = Find(root_list, node_1) root_node_2 = Find(root_list, node_2) # 두 노드의 루트가 같으면 if root_node_1 == root_node_2: # 병합하지 않고 루트 리스트 리턴 return ..

https://www.acmicpc.net/problem/1939Union-Find 알고리즘을 사용하면 보다 간편하게 풀 수 있는 문제입니다. 최소 스패닝 트리(MST) 문제를 풀 때 사용하는 크루스칼 알고리즘과 어떻게 보면 비슷한 문제입니다.일반적으로 크루스칼 알고리즘을 풀 때 엣지를 코스트 기준으로 오름차순 정렬해 순차적으로 병합해가며 연결여부를 탐색합니다. 하지만 해당 문제에서는 모든 노드의 연결이 아닌 연결되었으면 하는 노드가 정해져 있고 최대로 옮길 수 있는 코스트를 찾는 문제이기 때문에 조금 결이 다르다고 볼 수 있습니다. 엣지를 코스트 기준으로 내림차순 정렬하면 코스트가 큰 노드먼저 연결하게 됩니다. 그렇게 순차적으로 병합하다보면 어느 순간 연결되었으면 하는 두 노드가 같은 그룹에 속하는 때..

https://www.acmicpc.net/problem/2565최대 증가 부분 수열 (LIS) 문제입니다.연결된 전선의 목적 인덱스가 점차 증가하는 방향이어야 전선끼리 교차하지 않기 때문에 시작 인덱스를 기준으로 정렬한 뒤 목적 인덱스로 LIS 를 풀어주면 됩니다.import sysinput = sys.stdin.readlinedef solution(N, lines): # 라인 정리 lines = [l[1] for l in sorted(lines, key=lambda x:x[0])] # 증가하는 최대 부분 수열 길이 max_inc = [1 for _ in range(N)] # 순회 for l in range(1, N): # 자신보다 이전 전선이고 자신보다 작..

https://www.acmicpc.net/problem/17142어떻게 시작 바이러스 위치를 샘플링 할까 고민하시겠지만 모든 경우를 진행해보면 됩니다. 최대 바이러스 10 개중 M 개를 뽑는 경우의 수 중 최대는 M == 5 인 경우일텐데 252 가지 밖에 안되기 때문에 모두 진행한다고 해도 최악의 경우 252*50*50 = 630,000 번의 계산이 일어납니다. 때문에 모든 경우를 계산해도 아주 넉넉하게 통과할 수 있습니다. M 개의 바이러스를 뽑았다면 모든 M 개의 점에서 동시에 BFS 를 진행하며 최솟값을 갱신해주면 됩니다.import sysfrom collections import dequefrom itertools import combinationsinput = sys.stdin.readlin..

https://www.acmicpc.net/problem/11054LIS 알고리즘을 두 번 사용해 풀 수 있는 문제입니다.가장 긴 증가하는 부분 수열 이라는 이름의 알고리즘인데, 이는 DP 로 쉽게 구현할 수 있습니다. 이 알고리즘을 양 끝에서 구현해 만날 때 가장 크게 이어지는 부분을 찾아주면 풀 수 있습니다.import sysinput = sys.stdin.readlinedef solution(N, nums): # DP / 0 행은 증가 / 1 행은 감소 부분수열 memo = [[0 for _ in range(N)] for _ in range(2)] # 첫 번째 수는 무조건 바이토닉 수열 memo[0][0] = 1 memo[1][-1] = 1 # 순회 for i ..