문제 링크 https://www.acmicpc.net/problem/1389 문제 해설 Idea BFS 1부터 N까지의 번호에 대해 매번 BFS를 수행하면서 다른 모든 노드와의 거리를 파악 가장 작은 거리의 합을 가진 노드의 인덱스 번호를 출력 Time Complexity O(N^2+NM) = 510,000 Data Size N: 2 <= int <= 100 M: 1 <= int <= 5,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/5430 문제 해설 Idea Implementation, Deque 문제에서 주어진대로 매번 배열을 뒤집으면 O(N^2)의 시간 복잡도로 시간 초과가 발생 배열에 영향을 주지 않으면서 R 함수를 처리하기 위해 상태 변수를 정의하고, D 함수가 호출될 경우 배열의 상태에 따라 첫 번째 수를 버릴지 마지막 수를 버릴지 결정 마지막에 배열의 상태를 업데이트하고 정해진 형태로 결과를 출력 Time Complexity O(N) = 100,000 Data Size T: 1 <= int <= 100 p: 1 <= int <= 100,000 n: 1 <= int <= 100,000 arr: int(100) * n (like [x_1,…,x_n]) 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from collections import deque for _ in range(int(input())): p = input() n = int(input()) arr = deque(eval(input())) forward = True try: for cmd in p: if cmd == 'R': forward = not forward elif cmd == 'D': if forward: arr....
문제 링크 https://www.acmicpc.net/problem/1463 문제 해설 Idea Dynamic Programming N에 대해 조건을 만족하는 경우에서 3으로 나누기, 2로 나누기, 1을 빼는 연산을 반복 수행하고 각각의 연산횟수 별로 도출할 수 있는 값을 모두 저장 앞선 결과를 모두 활용해 다음 결과에 대한 모든 경우를 탐색하고 결과 집합에 1이 있을 시 탐색을 종료 1이 포함된 마지막 집합의 인덱스 번호를 최소 연산횟수로 출력 Data Size N: 1 <= int <= 10^6 해설 코드 1 2 3 4 5 6 7 8 9 10 11 N = int(input()) dp = [{N,}] while 1 not in dp[-1]: dp....
문제 링크 https://www.acmicpc.net/problem/1697 문제 해설 Idea BFS N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행 K에 대한 거리를 출력 N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단축을 위해 예외로 처리 Time Complexity O(N) = 100,000 Data Size N: 0 <= int <= 100,000 K: 0 <= int <= 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from collections import deque def bfs(start, target): MAX = 10**5 count = [0] * (MAX+1) queue = deque([start]) while queue: x = queue....
문제 링크 https://www.acmicpc.net/problem/20922 문제 해설 Idea Two Pointer 수열의 시작과 끝 지점에 대한 두 개의 포인터 지정 끝 지점에 대한 포인터를 확장하면서 탐색되는 원소의 수를 카운트 원소의 수가 K개와 같아지는 시점부터 시작 지점에 대한 포인터를 확장하여 범위 축소 최종적으로 두 포인터 간 거리의 최대치를 출력 Time Complexity O(N) = 200,000 Data Size N: 1 <= int <= 200,000 K: 1 <= int <= 100 a: int(100,000) * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 N, K = map(int, input()....