알고리즘 문제를 풀다 보면 "동작은 하지만 더 효율적으로 할 수 있지 않을까?" 라는 생각이 들 때가 있습니다. 오늘은 백준 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에서 간선 하나를 제거하면 정확히 두 개의 트리가 생성가장 비싼 간선을 제거해야 남은 비용이 최소해결..

😮 문제가 뭔가요?숫자 N이 주어지면 아래 세 가지 연산 중 하나를 선택해서 1을 만들어야 해요:3으로 나누어 떨어지면 ➡️ 3으로 나누기2로 나누어 떨어지면 ➡️ 2로 나누기1 빼기목표는 가장 적은 횟수로 1을 만드는 거예요!🔗 백준에서 직접 풀어보기😅 처음 생각나는 방법 (근데 이건 틀렸어요!)처음에는 이렇게 생각하기 쉬워요:"3으로 나누는 게 제일 빨리 작아지니까, 3으로 나눌 수 있을 때는 무조건 3으로 나누자!"N = int(input())count = 0while N != 1: if N % 3 == 0: N //= 3 elif N % 2 == 0: N //= 2 else: N -= 1 count += 1print(count..

머리말Baekjoon 13705번 문제(( Ax + B \sin(x) = C ))를 풀 때,처음에는 Python 내장 math.sin()을 사용했지만 '틀렸습니다'가 발생했다.왜 그럴까?이 글에서는math.sin()을 사용한 기존 코드Decimal + 직접 테일러 전개로 구현한 정답 코드를 비교하고,왜 Decimal + 테일러 전개가 필요한지 쉽게 설명한다.1. 기존 코드 (math.sin 사용)import sysimport mathinput = sys.stdin.readlinea, b, c = map(int, input().split())l = (c - b) / ar = (c + b) / afor _ in range(80): m = (l + r) / 2 V = a * m + b * math...