문제 링크 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()....
문제 링크 https://www.acmicpc.net/problem/22859 문제 해설 Idea Implementation, String , , 태그 등을 구분 의 attribute인 title을 우선 출력하고 안에 있는 를 한 줄씩 출력 안에 있는 태그와 시작과 끝에 있는 공백을 지우고 2개 이상의 공백을 하나로 변경 제목은 무조건 존재하고 태그 사이에는 공백이 없으며 태그는 올바른 쌍으로만 주어짐을 보장 정규 표현식을 활용해 조건에 맞는 문장을 파싱하고 불필요한 문자를 제거해 출력 Data Size source: str(1,000,000) 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import re source = input() main = re....
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238 문제 해설 Idea Binary Search answer에 대한 이진탐색 수행 (1 <= answer <= max(times)*n) 매 탐색마다 answer 시간 동안 심사관들이 심사할 수 있는 사람의 수를 계산 심사한 사람의 수가 n명 이상일 경우 최대 범위를 조정하고 재탐색 심사한 사람의 수가 n명 미만일 경우 최소 범위를 조정하고 재탐색 n명 이상의 사람을 심사할 수 있는 가장 작은 answer를 반환 Time Complexity Binary Search: O(M Log N^N) = 6,000,000 Data Size n: 1 <= int <= 1,000,000,000 times: int(1,000,000,000) * 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solution(n, times): answer = 0 start, end = 1, max(times)*n while start <= end: mid = (start+end)//2 passed = 0 for time in times: passed += mid // time if passed >= n: break if passed >= n: answer = mid end = mid-1 elif passed < n: start = mid+1 return answer