BOJ 2515 - 전시장 01. 🔎 문제 탐색N: 그림의 개수 $(1 \leq N \leq 300,000)$S: 판매가능해지는 보이는 부분의 세로 길이 H, C: (그림의 높이, 그림의 가격) $(1 \leq S \leq H \leq 300,000)$, $(1 \leq C \leq 1,000)$01-1. 가능한 시간 복잡도그림의 개수가 최대 300,000개로 시간 복잡도 $O(N log N)$ 이하로 구현되어야 함01-2. 알고리즘 선택높이가 오름차순으로 정렬된 그림 리스트에서 i번째 그림까지 최대 가격을 저장하고, 각 그림에 대해 이후에 등장할 그림의 높이가 S 만큼 차이가 날 경우, 이전에 저장된 최대 가격을 이용하여 누적 계산할 수 있으므로, DP를 이용각 i번째 그림에 대해 S만큼 차이..

01. 🔎 문제 탐색N: 드래곤 커브 개수 $(1 \leq N \leq 20)$x, y: 드래곤 커브 시작 점 $(0 \leq x,y \leq 100)$d: 드래곤 커브 시작 방향g: 드래곤 커브 세대드래곤 커브는 위 그림처럼, 이전 세대의 끝 점을 기준으로, 시계방향으로 90도 회전하여 끝 점에 이어져 늘어나는 것을 알 수 있음 OUTPUTN개의 드래곤 커브의 정보가 주어졌을 때, 1x1 정사각형의 4개 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력01-1. 가능한 시간 복잡도0세대에는 점 2개, 1세대에는 점 4개로 K세대에 점 $2^{K+1}$개를 가짐드래곤 커브 최대 개수 20개 * 최대 길이 $2^{10+1}$ = 약 40,960 번 연산$N*2^{K+1}$로 시간 복잡도 $O(2^{K..

01. 🔎 문제 탐색T: 테스트케이스 개수 $(T \leq 100)$h, w: 높이와 너비 $(2 \leq h,w \leq 100)$각 칸의 상태 { '.': 빈 공간, '*': 벽, '$': 문서, (대문자): 문, (소문자): 열쇠}문(대문자)은 그 알파벳이 나타내는 열쇠(소문자)로 열 수 있음열쇠는 여러 번 사용 가능 상근이는 빌딩 밖에서 시작해, 가장자리의 벽이 아닌 부분 어디로든 빌딩으로 들나들 수 있음만약, 문이 있을 경우 그 문의 열쇠가 필요OUTPUT상근이가 훔칠 수 있는 문서의 최대 개수를 출력01-1. 가능한 시간 복잡도빌딩에 들어갈 수 있는 가장자리 탐색 최대 4*100 - 4 = 약 396회, 시간 복잡도 $O(2h + 2w - 4)$빌딩에 들어간..

01. 🔎 문제 탐색N: 활동 영역 (NxN의 영역, N 영역의 칸 상태 (0: 빈 칸, 1: 벽)M: 목표 승객 수 ($M 초기연료 택시는 항상 최단경로로 이동현재 위치에서 가장 거리가 짧은 승객 우선 (거리가 같을 경우 아래의 우선 순위를 따름)행 번호가 가장 작은 승객 우선열 번호가 가장 작은 승객 우선위치가 같은 경우, 거리는 0연료는 1칸당 1씩 소모목적지에 도착 시, 승객을 태우고 소모한 연료의 2개가 충전 (초기 연료를 초과하여 충전도 가능)이동도중, 연료가 바닥나면 이동 실패 -> 하루 업무 종료만약, 목적지 도착과 동시에 연료 바닥 시에 이동 성공 판정OUTPUT모든 승객을 성공적으로 데려다주고 남은 연료의 양을 출력만약, 실패 시 -1을 출력01-1. 가능한 시간 복잡도시간 제..

01. 🔎 문제 탐색D: 준영이가 산책할 시간 (D분)한 건물에서 인접한 다른 건물로 이동하는 시간 1분캠퍼스의 지도가 위와 같을 때, 정보과학관에서 시작하여 D분이 될 때 정보과학관으로 도착 가능한 경로의 수를 출력01-1. 가능한 시간 복잡도D의 최대가 1e9로 시간 복잡도 $O(log D)$이하로 구현01-2. 알고리즘 선택분할 정복을 이용한 전이 행렬의 거듭제곱으로 구현02. 📝 코드 설계하기각 노드(건물)에 번호를 붙여, 갈 수 있는 인접한 건물을 나타내면 아래와 같다.정보과학관 (1)24 전산관 (2)134 신양관 (3)2456미래관 (4)1236진리관 (5)367 한경직기념관 (6)3458학생회관 (7)58 형남공학관 (8)67 처음 출발은 정보과학관이다. 0분(D=0) 일때, 각 ..

01. 🔎 문제 탐색n: 피보나치 수의 순서n=0, 피보나치 수 = 0n=1, 피보나치 수 = 1n의 최대는 1e18로 long long 사용피보나치 수를 1e9+7로 모듈러 연산하여 출력01-1. 가능한 시간 복잡도각 피보나치 수에 대해 선형탐색 시, O(N)의 시간 복잡도를 가지더라도 TLE 발생따라서, 시간 복잡도 O(log N) 이하로 구현01-2. 알고리즘 선택전이행렬을 이용한, 분할 정복으로 구현02. 📝 코드 설계하기피보나치 수열의 점화식을 나타내면 아래와 같음점화식을 행렬로 변환하면 아래와 같이 변환할 수 있음 V(n)과 A를 왼쪽과 같이 정의하면,위의 행렬 식을 아래와 같이 변환할 수 있음 V(n) = A^1 * V(n-1) = A^(n-1) * V(1) 위의 식을 풀어쓰면, 따..

01. 🔎 문제 탐색NxM 크기 공간치즈의 2변 이상이 외부 공기와 접촉하면, 그 치즈는 1시간 후 녹게 됨(단, 치즈 내부 공간은 접촉하지 않은 것으로 판단)맨 가장자리에는 치즈가 놓이지 않음INPUTN, M 입력NxM 크기만큼 상태 입력 (0: 공기, 1: 치즈)OUTPUT치즈가 모두 녹아 없어지게 되는 시간 출력01-1. 가능한 시간 복잡도N, M 외부 공기와 맞닿은 공간 탐색 O(NM)치즈에 대해 탐색 O(NM)치즈 탐색 1시간 당, 외부 공기 탐색 1회 진행하게 되므로, O(2NM)으로 볼 수 있다. 2e4로 1초내 충분히 수행가능01-2. 알고리즘 선택BFS를 이용하여 외부 공기와 치즈에 대해 탐색을 요구하는 시뮬레이션 문제 02. 📝 코드 설계하기N, M 그리고 NxM 크기 공간에 대한 ..

01. 🔎 문제 탐색D: n을 2배로 하여 10000으로 모듈러 연산한 값을 레지스터에 저장S: n-1을 레지스터에 저장. 단, n이 0일 경우 9999를 레지스터에 저장L: 각 자리수를 왼쪽으로 회전 (d1d2d3d4 -> d2d3d4d1)R: 각 지리수를 오른쪽으로 회전 (d1d2d3d4 -> d4d1d2d3)INPUTT: 테스트케이스 개수A: 시작 숫자, B: 목표 숫자OUTPUTA를 B로 바꾸기 위한 최소한의 명령을 출력01-1. 가능한 시간 복잡도최대 10000번의 연산, 시간 복잡도 O(N)으로 구현01-2. 알고리즘 선택시작 상태 A에서 D, S, L, R 4개의 명령으로 B를 만드는 것으로 BFS를 통해 최단 명령어를 구할 수 있음02. 📝 코드 설계하기A, B를 입력각 위치에 도달한 ..