https://www.acmicpc.net/problem/1912난이도 : S2Tag : DP풀이 일자 : 2025-05-02문제 탐색하기n개의 정수로 이루어진 수열이 주어진다.이 중 연속된 몇 개의 수를 선택해서 만들 수 있는 합 중 가장 큰 값을 구하라.단, 수는 하나 이상 반드시 선택해야 한다.조건1 ≤ n ≤ 100,000 (입력 수열의 길이)각 수는 -1,000 ≤ 정수 ≤ 1,000가능한 시간복잡도n이 최대 100,000이기 때문에,모든 구간을 다 탐색하는 이중 for문 (O(n²)) 방식은 시간 초과가 발생합니다.따라서 한 번의 순회로 정답을 찾는 O(n) 알고리즘이 필요하며,이 문제는 이전 상태값을 이용해 현재 값을 갱신하는 DP(동적 계획법) 으로 해결할 수 있습니다.알고리즘 선택DP ..

https://www.acmicpc.net/problem/3085난이도 : S2Tag : Simulation(구현)풀이 일자 : 2025-04-27문제 탐색하기보드의 크기: N × N (3 ≤ N ≤ 50)사탕 색상: C(빨강), P(파랑), Z(초록), Y(노랑)인접한 두 칸을 교환했을 때, 행이나 열에서 같은 색으로 이어진 가장 긴 부분의 길이를 구해야 한다.상근이가 먹을 수 있는 사탕의 최대 개수를 출력포인트인접한 두 칸만 교환 가능하다.교환 후 다시 원래 자리로 돌려놓을 수 있다.입력으로 주어지는 보드는 반드시 색이 다른 인접 칸이 존재한다가능한 시간복잡도최대 N = 50이므로, 전체 칸 수는 2500개.각 칸마다 인접한 칸과 교환을 시도하고, 그때마다 전체 보드를 스캔해서 최대 연속 길이를 구..

https://www.acmicpc.net/problem/13901난이도 : S1Tag : Simulation(구현)풀이 일자 : 2025-04-26문제 탐색하기방의 크기: R*C (3 장애물의 개수: k (0 로봇의 시작 위치: sr (0로봇의 이동방향: 1 = 위쪽, 2 = 아래쪽, 3 = 왼쪽, 4 = 오른쪽로봇이 움직이는 규칙로봇은 사용자가 지정한 방향을 일직선으로 움직인다.이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.로봇이 움직일 수 없을 경우 동작을 멈춘다.가능한 시간복잡도최대 방의 크기가 1,000*1,000 약 백만이므로 모든 위치를 순회해도 충분히 1초..

https://www.acmicpc.net/problem/2823난이도 : S3Tag : 그래프, 구현풀이 일자 : 2025-04-24문제 탐색하기R, C: 마을의 크기 (3 ≤ R, C ≤ 10). : 길, X : 빌딩상하좌우로 이동 가능유턴을 하지 않고 모든 길을 다닐 수 있어야 한다막다른 길이 하나라도 있으면 1 출력, 아니면 0 출력여기서 유턴이 필요하다는 것은 어떤 길(.)에서 갈 수 있는 방향이 하나밖에 없다는 뜻입니다.즉, 막다른 길(출구가 하나뿐인 길)이 있으면 반드시 유턴이 발생합니다.핵심은 모든 길(.)의 인접 길 개수(차수)가 2개 이상인지 확인하는게 목표입니다.가능한 시간복잡도전체 칸 수는 최대 100칸 (10x10)모든 칸을 한 번씩 순회하면서 인접 길의 개수를 확인하기시간복잡도..

https://www.acmicpc.net/problem/2659난이도 : S3Tag : Simulation(구현)풀이 일자 : 2025-04-24문제 탐색하기시계수: 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수위 그림 카드에서 3227, 2273, 2732, 7322로 읽을 수 있으므로 시계수는 2273카드는 1~9까지 4자리가 주어진다. (중복 허용)해당 숫자의 시계수를 구하고, 이 시계수가 전체 시계수 중에서 몇 번째로 작은지 구하는 것이 목표가능한 시간복잡도시계수는 1111부터 9999까지 존재할 수 있으므로,확인해야 하는 숫자의 개수는 최대 9,999 - 1,111 + 1 = 8,889개입니다. 각 숫자마다 시계 방향으로 4번 회전해보고, 그 중 가장 작..

https://www.acmicpc.net/problem/2012난이도 : S3Tag : Greedy풀이 일자 : 2025-04-23문제 탐색하기N: 총 학생 수 (1 불만도: |예상 등수 - 실제 등수|즉, 모든 학생의 불만도 합이 최소가 되도록 실제 등수를 매기면 됩니다.가능한 시간복잡도최대 50만 명이 입력으로 들어오기 때문에,입력 처리: O(N)정렬: O(N log N) 정도까지는 충분히 풀 수 있습니다.단순 for문 이중 루프 같은 O(N^2) 방식은 시간 초과 나기 때문에 불가능합니다.알고리즘 선택그리디 + 정렬 조합으로 풀겠습니다.학생들이 적은 예상 등수는 실제 등수와 최대한 비슷할수록 불만도가 작아집니다.따라서 예상 등수를 오름차순 정렬한 뒤,앞에서부터 실제 등수 1, 2, 3... 순서..

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만, 도로..