https://www.acmicpc.net/problem/1916난이도 : G5Tag : Graph풀이 일자 : 2025-04-21문제 탐색하기N개의 도시가 있고, 한 도시에서 다른 도시로 가는 M개의 버스 정보가 주어진다.우리는 A도시에서 B도시까지 이동하는 최소 비용을 구해야 한다.예를 들어 1번 도시에서 5번 도시까지 가는 경우,1 → 4 (비용 1), 4 → 5 (비용 3) 을 선택하면 총 비용은 4가 된다.이처럼 다양한 경로 중 가장 저렴한 비용을 찾아 출력하는 문제입니다.조건도시 개수 N (1 ≤ N ≤ 1,000)버스 개수 M (1 ≤ M ≤ 100,000)M개의 줄에 걸쳐 (출발 도시, 도착 도시, 비용) 정보마지막 줄에 출발 도시 A와 도착 도시 BA → B로 이동할 때의 최소 비용 출..

https://www.acmicpc.net/problem/18352난이도 : S2Tag : Graph풀이 일자 : 2025-04-20문제 탐색하기N개의 도시(1 ~ N)M개의 단방향 도로모든 도로의 거리는 1출발 도시 X에서 최단 거리가 정확히 K인 도시들을 오름차순 출력예를 들어 N = 4, K = 2, X = 1일 때,1 → 2 → 4 로 도달 가능하므로 결과는 4 하나만 출력됩니다.조건입력도시 개수 N (2 ≤ N ≤ 300,000)도로 개수 M (1 ≤ M ≤ 1,000,000)거리 정보 K (1 ≤ K ≤ 300,000)출발 도시 X (1 ≤ X ≤ N)M개의 도로 정보 (A → B 단방향)출력최단 거리가 K인 도시 번호 오름차순 출력없으면 -1 출력가능한 시간복잡도최대 도시 수 30만, 도로..

https://www.acmicpc.net/problem/1713난이도 : S1Tag : Simulation(구현)풀이 일자 : 2025-04-17문제 탐색하기N: 사진틀의 개수 (1 ≤ N ≤ 20)총 추천 횟수는 최대 1000회학생 번호는 1부터 100까지의 자연수조건 추천이 시작되기 전, 사진틀은 모두 비어 있다.추천받은 학생은 반드시 사진틀에 게시되어야 한다.사진틀이 가득 찼을 경우:추천 수가 가장 적은 학생의 사진을 삭제동점일 경우, 더 오래된 학생 사진을 삭제이미 게시된 학생이 추천을 받을 경우, 추천 수만 증가한다.삭제된 학생의 추천 수는 초기화된다.가능한 시간복잡도추천 횟수: 최대 1000회사진틀 개수: 최대 20개삭제 대상은 매번 리스트를 순회하여 O(N)으로 찾을 수 있습니다.Coll..

https://www.acmicpc.net/problem/5212난이도 : S2Tag : Simulation(구현)풀이 일자 : 2025-04-16문제 탐색하기R: 지도의 세로 길이 (행), 1 ≤ R ≤ 10C: 지도의 가로 길이 (열), 1 ≤ C ≤ 10지구 온난화로 인해 50년 후 섬의 일부가 바다에 잠기게 됩니다.인접한 4칸 중 바다가 3칸 이상이면 해당 땅은 물에 잠깁니다.여기서 인접한 4칸은 상, 하, 좌, 우를 의미.또한, 지도의 범위를 벗어난 칸은 바다로 간주합니다.50년 후의 지도를 출력하되, 모든 섬을 포함하는 가장 작은 직사각형 범위만 출력해야 합니다.문제 조건에 따라 50년 후에도 최소한 하나 이상의 섬은 남습니다.가능한 시간복잡도최대 지도 크기는 10 × 10 = 100칸각 칸..

https://www.acmicpc.net/problem/10157난이도 : S3Tag : Simulation(구현)풀이 일자 : 2025-04-15문제 탐색하기C: 공연장의 가로길이R: 공연장의 세로 길이K: 관객의 대기 순서공연장은 (1,1)부터 (C, R)까지의 좌석으로 구성되며, 관객들은 대기번호 순서대로 좌석에 배정됩니다.배정 방식은 (1,1)부터 시작해 시계방향으로 나선형으로 회전하며 안쪽으로 들어갑니다. 즉, 이 문제의 핵심은 나선형 회전을 구현하면서,K번째 관객이 배정받는 좌표 (y, x)를 구하는 것입니다.가능한 시간복잡도대기번호 K는 최대 1억까지 주어질 수 있지만,공연장의 최대 크기는 1000 × 1000 = 1,000,000이므로,실제로 좌석이 배정되는 최대 수는 100만 개입니다..

https://www.acmicpc.net/problem/13164난이도 : G5Tag : 그리디풀이 일자 : 2025-04-14문제 탐색하기N명의 원생을 키 순서대로 줄 세운다.이들을 인접하게 K개의 조로 나누고각 조의 티셔츠 제작 비용은 가장 큰 키 - 가장 작은 키로 계산된다.모든 조의 비용 합을 최소화하는 것이 목표다.예를 들어1 3 5 6 10에서 K=3이면,[1,3], [5,6], [10] → 총 비용: (3-1) + (6-5) + (0) = 3이 나오게 됩니다.가능한 시간복잡도N은 최대 300,000이므로 O(N log N) 또는 O(N) 수준의 알고리즘이 필요합니다.정렬 + 슬라이싱 또는 우선순위 처리를 통해 해결 가능합니다.알고리즘 선택그리디를 선택하겠습니다.왜 그리디가 가능할까?원생은..

https://www.acmicpc.net/problem/18230난이도 :  S1Tag : 그리디풀이 일자 : 2025-04-13문제 탐색하기2×N 크기의 화장실 바닥이 있다.사용 가능한 타일은 다음 두 가지이다:2×1 크기 타일 A개2×2 크기 타일 B개각 타일에는 예쁨의 정도가 주어지며, 회전 가능하다.바닥 전체를 타일링했을 때 예쁨의 총합이 최대가 되도록 배치해야 한다.가능한 시간복잡도N, A, B는 최대 2000이므로전체 타일 수는 최대 4000정렬 후 부분 선택만 하면 되므로→ O(N log N) 정도의 알고리즘이면 충분합니다.알고리즘 선택그리디 알고리즘을 선택하겠습니다.이유는 다음과 같습니다:각 타일은 회전이 가능하므로, 2×1은 1칸, 2×2는 2칸을 채운다고 보면 됩니다.한정된 공간(N칸..

https://www.acmicpc.net/problem/14247난이도 :  S2Tag : 그리디풀이 일자 : 2025-04-12문제 탐색하기n: 총 나무의 개수Hi: i번째 나무의 첫날 길이Ai: i번째 나무가 하루에 자라는 길이목표는 n일 동안 하루에 하나씩 나무를 잘라 최대한 많은 나무 길이를 얻는 것입니다.이때, 잘린 나무는 다시 0부터 자라기 때문에 같은 나무를 여러 번 자를 수 있다는 조건이 있습니다.가능한 시간복잡도입력: O(N)정렬: O(NlogN)순차 계산: O(N)→ N ≤ 100,000 이므로 30만 이내로 충분히 통과 가능합니다.알고리즘 선택그리디를 선택하겠습니다.문제를 처음 보면,“매일 자란 나무 중 가장 긴 걸 자르면 되지 않을까?” 라고 생각할 수 있습니다.하지만 아래 반례를..