문제 링크 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://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....
문제 링크 https://www.acmicpc.net/problem/16918 문제 해설 Idea Simulation (or BFS) 초기에 빈 칸(.)을 0, 폭탄이 있는 칸(O)을 1로 설정 처음에 폭탄이 있는 칸의 상태를 우선 1 증가시키고, 이후 모든 칸의 상태를 1씩 증가시키는 과정 반복 매번 각 칸의 상태를 점검하면서 3을 초과할 경우 해당 위치 및 이웃 위치를 폭발 대상에 추가 폭발 대상이 존재할 경우 격자의 범위를 벗어나지 않는 범위 내에서 상태를 0으로 변환 위 과정을 N초 동안 반복하고, 0은 빈칸으로, 나머지는 O로 표시하여 출력 Time Complexity Simulation: O(N^3) = 8,000,000 Data Size R, C, N: 1 <= int <= 200 해설 코드 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 import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/2302 문제 해설 Idea Dynamic Programming 자리를 옮길 수 있는 연속되는 좌석의 수는 피보나치 수열을 따름 (S[i] = F[i+1]) VIP 좌석 번호를 기준으로 연속되는 좌석의 수를 리스트로 저장 모든 연속되는 좌석 수에 대한 피보나치 수를 곱하고 출력 Sequence S2 (1,2) -> (1,2), (2,1) = 2(F3) S3 (1,2,3) -> (1,2,3), (2,1,3), (1,3,2) = 3(F4) S4 (1,2,3,4) -> (1,2,3,4), (2,1,3,4), (1,2,4,3), (1,3,2,4), (2,1,4,3) = 5(F5) S5 (1,2,3,4,5) -> (1,2,3,4,5), (1,2,4,3,5), (1,2,3,5,4), (2,1,3,4,5), (2,1,4,3,5), (2,1,3,5,4), (1,3,2,4,5), (1,3,2,5,4) = 8(F6)...