본문 바로가기

백준

 (54)
[백준] 평행사변형 (1064번) 문제 해결 흐름1. 입력3개의 점의 좌표 A(x1​,y1​), B(x2​,y2​), C(x3​,y3​)를 입력받습니다.2. 일직선 확인주어진 3개의 점이 일직선상에 위치하는지 확인해야 합니다.조건: 점 A, B, C가 일직선상에 존재하면 평행사변형은 물론 사각형을 만들 수 없으므로 프로그램을 종료합니다.기울기 공식 : 기울기(AB) = (y2 - y1) / (x2 - y1)프로그래밍으로 나눗셈을 계산할 때는 부동소수점으로 인하여 계산이 정확하지 않습니다. 나눗셈을 사용하는 대신 곱셈 방식으로 변경하여 계산합니다.나눗셈을 곱셈으로 변경: (x2−x1)⋅(y3−y1)=(x3−x1)⋅(y2−y1)3. 거리 계산점과 점 사이의 거리를 계산하기 위해 유클리드 거리 공식을 사용합니다​유클리드 거리(Euclidean..
[백준] 요세푸스 문제(1158번): 커스텀 원형 연결 리스트로 해결하기 코드 힌트문제 흐름n명의 사람들이 원형으로 앉아 있습니다.매 k번째 사람을 제거하는 작업을 반복해 최종 순서를 출력합니다.기본적으로 요세푸스 문제는 큐를 활용한 풀이가 일반적이지만, 이 코드는 원형 연결 리스트를 직접 구현해 해결합니다.핵심 아이디어원형 연결 리스트 구현: 각 노드가 자기 자신을 포함한 원형 구조를 형성합니다. 마지막 노드는 처음 노드를 참조하며 리스트의 끝이 없습니다.현재 노드 추적: pointNode를 활용해 현재 노드를 추적하며, 매 k번째 노드를 제거합니다.출력 최적화: StringBuilder를 사용해 제거된 노드의 순서를 효율적으로 출력합니다.알고리즘 흐름리스트 초기화CircularLinkedList 클래스에서 노드를 추가해 원형 연결 리스트를 구성합니다.첫 번째 노드는 sta..
[백준] 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))입니다.완전탐색을 이용해 각 조합을 모두 탐색하면서 최소 능력치 차이를 찾습니다. 핵심 아이디어완전 탐색(백트래킹)을 사용해 모든 팀 조합을 탐색합니다.사람들을 두 팀으로 나누고, 각각의 팀 능력..

티스토리툴바