알고리즘 문제를 풀다 보면 "동작은 하지만 더 효율적으로 할 수 있지 않을까?" 라는 생각이 들 때가 있습니다. 오늘은 백준 11728번 '배열 합치기' 문제를 통해 단순한 접근법에서 최적화된 해결책으로 발전하는 과정을 살펴보겠습니다.문제 분석문제 설명백준 11728번: 배열 합치기시간 제한: 1.5초메모리 제한: 256MB정답 비율: 46.789%문제 내용: 이미 정렬되어 있는 두 배열 A와 B가 주어질 때, 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성해야 합니다.입력 조건첫째 줄: 배열 A의 크기 N, 배열 B의 크기 M (1 ≤ N, M ≤ 1,000,000)둘째 줄: 배열 A의 내용 (정렬된 상태)셋째 줄: 배열 B의 내용 (정렬된 상태)배열 원소: 절댓값이 10⁹보다 작거나 같은 정수..

문제 요약5×5 빙고판에 1~25까지의 수가 한 번씩 적혀 있습니다.사회자가 25개의 수를 한 번씩 부를 때,각 수가 불릴 때마다 빙고판에서 해당 수를 지웁니다.가로, 세로, 대각선 중 5개가 모두 지워진 줄이 3개 이상이 되는 순간철수는 "빙고!"를 외치게 됩니다.사회자가 몇 번째 수를 부른 후 빙고가 완성되는지 구하는 문제입니다.접근 방식빙고판과 사회자가 부르는 수의 순서를 2차원 리스트로 입력받습니다.각 숫자가 불릴 때마다, 빙고판에서 해당 숫자를 찾아 체크합니다.매번 가로, 세로, 두 대각선에 대해5개가 모두 체크된 줄(빙고 줄)의 개수를 셉니다.빙고 줄이 3개 이상이 되는 순간,그때까지 부른 수의 개수를 출력하고 종료합니다.실생활 비유로 설명하면,"빙고판에 체크 표시를 하면서가로, 세로, 대각선..

문제 요약9×9 크기의 스도쿠 보드가 주어집니다.각 행, 각 열, 그리고 3×3 박스마다 1~9가 중복 없이 한 번씩만 등장해야 합니다.아직 채워지지 않은 칸은 0으로 주어지며,모든 빈 칸을 조건에 맞게 채운 "가장 사전순으로 앞서는" 해답을 출력하는 문제입니다.접근 방식이 문제는 대표적인 "백트래킹" 유형입니다.먼저, 빈 칸(0)의 좌표를 모두 저장합니다.각 빈 칸에 대해 1~9 중 가능한 숫자를 하나씩 시도합니다.숫자를 넣었을 때 행, 열, 3×3 박스에 중복이 없으면 다음 칸으로 진행합니다.만약 모든 빈 칸을 채웠다면, 그 즉시 답을 출력하고 탐색을 종료합니다(사전순 보장).불가능하면 백트래킹(원상복구)하여 다른 숫자를 시도합니다.실생활 비유로 설명하면,"빈 칸마다 1~9 중 가능한 숫자를 하나씩 ..

문제 요약N개의 집이 일렬로 있고, 각 집을 빨강, 초록, 파랑 중 하나로 칠해야 합니다.각 집을 각 색으로 칠하는 비용이 주어질 때, 1번 집의 색은 2번, N번 집의 색과 달라야 하고 N번 집의 색은 N-1번, 1번 집의 색과 달라야 하며 나머지 집도 인접한 집과 색이 달라야 합니다.이 조건을 모두 만족하면서 모든 집을 칠하는 최소 비용을 구하는 문제입니다.접근 방식이 문제는 "원형" 형태의 인접 제약이 추가된 RGB거리 문제입니다.즉, 1번 집과 N번 집도 서로 색이 달라야 하므로,단순한 DP로는 해결이 어렵고,1번 집의 색을 고정한 뒤, 1번 집을 빨강/초록/파랑 각각으로 칠하는 경우를 모두 시도 그에 따라 N번 집이 같은 색이 되지 않도록 DP를 돌려 세 경우 중 최소값을 정답으로 선..

문제 요약DDR(Dance Dance Revolution) 게임에서,중앙(0)과 네 방향(1: 위, 2: 왼쪽, 3: 아래, 4: 오른쪽) 발판이 있습니다.처음엔 두 발 모두 중앙(0)에 있고, 주어진 스텝 순서대로 한 발씩 움직여야 합니다. 같은 위치에 두 발이 동시에 있을 수는 없습니다(시작 제외).한 발이 이미 해당 위치에 있다면, 그 발로 반복해서 눌러야 합니다.발을 움직일 때 드는 힘은 다음과 같습니다:중앙(0) → 다른 위치: 2같은 위치 반복: 1인접한 위치로 이동: 3반대편(예: 위↔아래, 왼↔오른) 이동: 4모든 스텝을 밟는 데 필요한 최소 힘을 구하는 문제입니다.접근 방식이 문제는 "상태"를 잘 정의해서 DP(동적 프로그래밍)로 해결해야 합니다.각 스텝마다, 왼발과 오른발이 각각 어디..

문제 요약두 개의 정수 배열 A, B가 주어집니다.각 배열에서 연속된 부분 구간(부 배열)을 하나씩 골라,A의 부 배열의 합 + B의 부 배열의 합 = T가 되는 쌍의 개수를 구하는 문제입니다.예를 들어,A = [1, 3, 1, 2], B = [1, 3, 2], T = 5라면A의 부 배열과 B의 부 배열을 각각 골라 합이 5가 되는 경우의 수를 모두 세야 합니다.접근 방식처음에는 모든 부 배열 쌍을 직접 만들어 합을 비교하는 완전탐색을 떠올릴 수 있습니다.하지만 배열의 길이가 최대 1,000이므로,O(N² × M²) 방식은 시간 초과가 발생합니다.여기서 "부 배열의 합"이라는 조건에 주목하면,각 배열의 모든 부 배열 합을 미리 구해놓고,A의 부 배열 합 + B의 부 배열 합 = T즉, A의 부 배열 합이..

문제 요약여러 명의 플레이어가 각각 1~1,000,000 사이의 서로 다른 수가 적힌 카드를 한 장씩 받습니다.각 플레이어는 본인을 제외한 모든 플레이어와 한 번씩 결투를 하며, 내 카드의 수로 상대의 수를 나누어 떨어지면 승리(+1점), 반대로 상대가 내 수를 나누어 떨어뜨리면 패배(-1점), 둘 다 아니면 무승부(점수 변화 없음)이렇게 모든 결투가 끝난 뒤, 각 플레이어의 최종 점수를 구하는 문제입니다.접근 방식처음에는 모든 플레이어 쌍을 비교하는 완전탐색을 떠올릴 수 있습니다.하지만 플레이어 수 N이 최대 100,000명, 카드 숫자 범위도 1,000,000까지라서O(N²) 방식은 시간 초과가 발생합니다.여기서 "나누어 떨어진다"는 조건에 주목하면,각 카드의 배수(2배, 3배, ...)가 다른..

들어가며백준 1647번 '도시 분할 계획' 문제는 최소 신장 트리(MST)의 성질을 활용한 흥미로운 문제입니다. 핵심 아이디어는 전체 그래프에서 MST를 만든 후, 가장 비싼 간선 하나를 제거하면 두 개의 연결된 마을로 나눌 수 있다는 점입니다.문제 분석📋 문제 요약시간 제한: 2초 | 메모리 제한: 256MB | 정답률: 49.164%N개의 집과 M개의 길이 있는 마을을 두 개의 마을로 분할각 마을 내에서는 모든 집이 연결되어야 함남은 길의 유지비 합을 최소화🎯 핵심 통찰마을을 두 개로 나누기 = MST에서 간선 하나 제거하기왜 이 방법이 최적일까요?MST는 N-1개의 간선으로 모든 정점을 연결MST에서 간선 하나를 제거하면 정확히 두 개의 트리가 생성가장 비싼 간선을 제거해야 남은 비용이 최소해결..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/92343문제2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/340199문제민수는 다양한 지폐를 수집하는 취미를 가지고 있습니다. 지폐마다 크기가 달라 지갑에 넣으려면 여러 번 접어서 넣어야 합니다. 예를 들어 지갑의 크기가 30 * 15이고 지폐의 크기가 26 * 17이라면 한번 반으로 접어 13 * 17크기로 만든 뒤 90도 돌려서 지갑에 넣을 수 있습니다. 지폐를 접을 때는 다음과 같은 규칙을 지킵니다.지폐를 접을 때는 항상 길이가 긴 쪽을 반으로 접습니다.접기 전 길이가 홀수였다면 접은 후 소수점 이하는 버립니다.접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있다면 그만 접습니다.지갑의 가로, 세로 크기를 담은 정수 리스트 wallet과..