Algorithm

문제 링크 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)...

문제 링크 https://www.acmicpc.net/problem/18352 문제 해설 Idea BFS 시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록 거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력 거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축 Time Complexity BFS: O(N+M) = 1,300,000 Data Size N: 2 <= int <= 300,000 M: 1 <= int <= 1,000,000 K: 1 <= int <= 300,000 X: 1 <= int <= N A, B: 1 <= int <= N 해설 코드 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/1495 문제 해설 Idea Dynamic Programming P[i] = max(P[i-1]+V[i-1],P[i-1]-V[i-1]), 0 <= P[i] <= M 모든 P[i-1]가 P[i+1]에 영향을 줄 수 있기 때문에 범위 내 모든 값을 집합에 저장 마지막 곡에 대한 P가 존재할 경우 최댓값을 출력하고, 없을 경우 -1을 출력 Time Complexity DP: O(NM) = 50,000 Data Size N: 1 <= int <= 50 M: 1 <= int <= 1,000 S: 0 <= int <= M V: int * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 N, S, M = map(int, input()....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17686 문제 해설 Idea 정규표현식을 활용해 HEAD, NUMBER, TAIL을 분리 전체 파일명을 완전탐색하면서 리스트에 분리된 파일명을 저장 HEAD와 NUMBER를 기준으로 파일명을 정렬하고 정렬된 원본 파일명을 반환 Time Complexity Brute-Force + Sort: O(NM+NlogN)) = 110000 Data Size files: str(100) * 1000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 import re def solution(files): answer = [] for file in files: head, number, tail = re....