문제 링크 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
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 해설 Idea Dynamic Programming S[1] = {N} S[2] = {NN, N+N, N-N, N*N, N/N} S[3] = {NNN, S[2] (+,-,*,/) S[1][y], …} 2부터 8까지의 범위를 가진 i와 1부터 i-1까지의 범위를 가진 j에 대해, S[j]와 S[i-j]의 사칙연산 결과를 S[i]에 추가하고 해당 집합이 number를 포함하는지 검증 Time Complexity DP: O(1) Data Size N: 1 <= int <= 9 number: 1 <= int <= 32,000 answer: int <= 8 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from itertools import product def solution(N, number): S = [set() for _ in range(9)] if N == number: return 1 else: S[1]....
문제 링크 https://www.acmicpc.net/problem/21318 문제 해설 Idea Prefix Sum 실수한 곡에 대한 누적합을 구하고 인덱싱을 통해 특정 구간에 대한 누적합 출력 마지막 곡은 항상 성공하기 때문에 y에 대한 누적합과 y-1에 대한 누적합이 다르면 1 감소 Time Complexity Prefix Sum: O(N) = 100,000 Data Size N: 1 <= int <= 100,000 scores: int(10^9) * N Q: 1 <= int <= 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/16987 문제 해설 Idea Backtracking 0번째 계란부터 마지막 계란까지의 모든 경우의 수를 탐색 시간 단축을 위해 현재 계란이 깨진 경우 또는 나머지 모든 계란이 깨진 경우를 예외로 처리 한 번에 두 개 이상의 계란을 치는 경우를 방지하기 위해 계란을 친 후 원상복구 수행 Time Complexity Backtracking: O(N^N) = 16,777,216 Data Size N: 1 <= int <= 8 S, W: 1 <= int <= 300 해설 코드 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 N = int(input()) eggs = list() for _ in range(N): eggs....