백준 (52) 썸네일형 리스트형 [백준] 1, 2, 3 더하기 문제 흐름문제 목표숫자 n이 주어졌을 때, 숫자 1, 2, 3을 사용해 그 합이 n이 되는 모든 경우의 수를 계산합니다.입력 및 출력 설명여러 테스트 케이스에 대해 각각의 숫자 n을 입력받고, 각 경우에 대해 결과를 출력합니다. 핵심 아이디어동적 프로그래밍(DP)현재 숫자 i를 만들기 위해 마지막에 추가하는 숫자가 1, 2, 또는 3일 때의 경우를 합산합니다.점화식: arr[i] = arr[i-1] + arr[i-2] + arr[i-3]여기서 arr[i]는 숫자 i를 만드는 경우의 수를 나타냅니다.이 문제는 미리 계산된 DP 배열에서 결과를 빠르게 조회하는 방식으로 해결할 수 있습니다. 알고리즘 흐름DP 배열 초기화arr[0]=1로 초기화합니다.배열을 통해 1부터 10까지의 결과를 미리 계산합니다.DP .. [백준] 연속합 (1912번) 문제 흐름문제 목표주어진 배열에서 연속된 부분 수열의 최대 합을 구하는 문제입니다.이 문제는 동적 프로그래밍을 이용하여 해결할 수 있습니다.입력 설명첫 줄에 정수 N (배열의 크기)를 입력받습니다.다음 줄에 N개의 정수 (각 원소의 값)를 입력받습니다.출력 설명연속된 부분 수열의 최대 합을 출력합니다. 핵심 아이디어동적 프로그래밍(DP):현재 원소까지의 최대 합을 계산하면서 최댓값을 갱신합니다.배열의 각 원소를 순회하면서, 이전 원소와 현재 원소를 합치는 것이 더 큰 경우에 업데이트합니다.위 알고리즘을 카데인 알고리즘이라고 합니다.점화식:dp[i]는 dp[i-1] + arr[i] (현재 원소를 포함한 최대 합)과 arr[i] (현재 원소만) 중 큰 값을 선택합니다. 알고리즘 흐름입력 처리배열의 크기 N과.. [백준] 토마토 (7576번) 문제 흐름문제 목표상자에 있는 토마토들이 모두 익는 데 걸리는 최소 일수를 구합니다.토마토는 익은 상태에서 인접한 상하좌우의 토마토들을 하루마다 익게 만듭니다.모든 토마토가 익을 수 없는 경우 -1을 출력합니다.입력 설명첫 줄에 MMM (상자의 세로 크기)와 NNN (가로 크기) 입력.그다음 각 칸의 상태(익은 토마토: 1, 익지 않은 토마토: 0, 빈 칸: -1)로 상자를 초기화합니다.출력 설명모든 토마토가 익는 데 걸린 최소 일수를 출력.익지 못하는 토마토가 있다면 -1을 출력합니다. 핵심 아이디어BFS(너비 우선 탐색) 사용: 여러 위치에서 동시에 확산되는 문제이므로 BFS가 적합합니다.큐(Queue)를 활용하여 여러 익은 토마토를 동시에 처리하며, 매일 새로운 익은 토마토를 큐에 추가합니다.익지 .. [백준] 부분합 (1806번) 문제 흐름문제 목표주어진 정수 배열에서 연속된 부분 수열의 합이 주어진 수 S 이상이 되도록 하는 가장 짧은 부분 수열의 길이를 찾는 것입니다.입력 설명첫 번째 줄에 두 개의 정수 N (배열의 크기)과 SSS (목표 합) 이 주어집니다.두 번째 줄에는 N개의 정수가 배열의 요소로 주어집니다.출력 설명조건을 만족하는 가장 짧은 부분 수열의 길이를 출력하며, 그런 부분 수열이 없는 경우에는 0을 출력합니다. 핵심 아이디어슬라이딩 윈도우 기법을 사용하여 두 포인터(시작점과 끝점)를 이동시킵니다.현재 부분 수열의 합이 목표 합 S 이상이 될 때까지 끝점을 이동시키고, 목표를 만족하면 시작점을 이동하여 가능한 한 부분 수열의 길이를 최소화합니다. 알고리즘 흐름입력값 읽기: 배열의 크기 N과 목표 합 S를 입력받고.. [백준] 단지번호붙이기 (2667번) 문제 흐름문제 목표N x N 크기의 이진 행렬이 주어졌을 때, 1로 이루어진 연결된 집합(단지)을 찾아야 합니다.각 집합의 크기를 계산하여 총 단지 수와 단지별 집의 개수를 출력합니다.연결은 상하좌우 인접한 1들을 통해 이루어지며, 대각선 연결은 포함되지 않습니다.입력 설명첫 줄에 지도 크기 N이 주어집니다.이후 N개의 줄에 0과 1로 이루어진 행렬이 주어집니다. 1은 집이 있는 곳, 0은 빈 공간을 의미합니다.제약 조건최대 크기가 25x25인 행렬입니다.깊이 우선 탐색(DFS)을 사용해 모든 단지를 탐색하고 각 단지의 크기를 구합니다. 핵심 아이디어DFS(깊이 우선 탐색)를 사용해 한 번 방문한 집(1)은 다시 방문하지 않도록 방문 체크를 합니다.단지 내의 집을 모두 탐색할 때마다 단지 크기를 계산하고.. [백준] 스타트와 링크 (14889번) 문제 흐름문제 목표T명이 주어졌을 때, 두 팀으로 나누고 팀 능력치 차이의 최소값을 구하는 문제입니다.각 팀의 능력치는 해당 팀의 두 사람 사이 능력치 합으로 계산합니다.두 팀의 능력치 차이가 최소가 되도록 팀을 나누는 것이 핵심입니다.입력 설명첫 줄에 사람 수 T가 주어집니다 (항상 짝수).이후 T x T 크기의 능력치 행렬이 주어지며, 행렬의 (i, j)는 i번과 j번 사람이 같은 팀일 때 기여하는 능력치를 의미합니다.제약 조건사람 수가 최대 20명이므로 가능한 팀 조합의 경우의 수는 조합(C(T, T/2))입니다.완전탐색을 이용해 각 조합을 모두 탐색하면서 최소 능력치 차이를 찾습니다. 핵심 아이디어완전 탐색(백트래킹)을 사용해 모든 팀 조합을 탐색합니다.사람들을 두 팀으로 나누고, 각각의 팀 능력.. [백준] RGB거리 (1149번) 문제 흐름문제 목표:각 집을 세 가지 색(빨강, 초록, 파랑) 중 하나로 칠합니다.단, 인접한 두 집은 같은 색으로 칠할 수 없습니다.모든 집을 칠할 때의 최소 비용을 구해야 합니다.입력 설명:첫 줄에 집의 개수 n이 주어집니다.이후 n개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠할 때 드는 비용이 주어집니다.제약 조건:DP(동적 계획법)을 사용해 인접 집의 색이 겹치지 않도록 최소 비용을 누적합니다. 핵심 아이디어DP(동적 계획법)으로 최소 비용을 누적 계산합니다.각 집을 특정 색으로 칠할 때 최소 비용은 이전 집에서 자신과 다른 색을 선택한 최소 비용과 현재 색의 비용을 더한 값입니다.마지막 집까지 누적된 비용 중 최소값을 결과로 출력합니다. 알고리즘 흐름입력받기:n개의 집과 각 색의 비용을 2차원.. [백준] 하노이 탑 이동 순서 (11729번) 문제 흐름목표: 주어진 n개의 원판을 첫 번째 기둥(스택)에서 세 번째 기둥으로 옮기는 것이 목표입니다. 단, 한 번에 한 개의 원판만 옮길 수 있으며, 큰 원판이 작은 원판 위에 놓일 수 없습니다.출력:최소 이동 횟수를 출력합니다.각 이동 경로를 (from, to) 형식으로 출력합니다. 핵심 아이디어재귀적 접근:원판이 1개일 때는 바로 목표 기둥으로 옮기면 됩니다.원판이 여러 개일 경우, 재귀적으로:상위 원판 n-1개를 보조 기둥으로 이동합니다.가장 큰 원판을 목표 기둥으로 이동합니다.보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동합니다.스택 사용: 각 기둥은 스택으로 구현되어, 원판 이동 시 올바른 순서를 유지합니다. 알고리즘 흐름초기화 (initHanoi):세 개의 기둥(스택)을 초기화합니다.. 이전 1 2 3 4 ··· 7 다음