본문 바로가기

코딩테스트/백준12

[백준] 9465번 - 스티커 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석🏆 문제 개요2 × n 크기의 스티커 배열에서 점수를 최대로 얻도록 스티커를 선택해야 한다.단, 선택한 스티커와 변을 공유하는 스티커는 사용할 수 없다.최대 점수를 출력하는 프로그램을 작성해야 한다.🎯 요구사항각 테스트 케이스에 대해 최대 점수를 출력해야 한다.두 행(2 × n)으로 구성된 스티커 배열에서 인접하지 않은 스티커들을 선택해야 한다.1 ≤ n ≤ 100,000이므로, 효율적인 알고리즘이 필요하다. (시간 복잡도 O(n) 이하)2. 해결 방법🔹 핵심 개념이 문제는 다이나믹 프로그래밍(DP)을 활용하면 효과적으로 해결할 수 있다.점화식을 세우는 것이 핵심이며, 각 위치에서 얻을 수 있는 최대 점수를 누적해 나가는 방식이다.🔑 해결 절차입력값 처리 및 DP 테이블 초.. 2025. 2. 27.
[백준] 7562번 - 나이트의 이동 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석🏰 문제 개요체스판 위에서 나이트(knight)가 주어진 위치에서 목표 위치까지 이동하는 최소 횟수를 구하는 문제이다.나이트는 다음과 같은 8가지 방향으로 이동할 수 있다.(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1), (2, 1), (1, 2)🎯 요구사항나이트가 l x l 크기의 체스판에서 이동해야 한다.출발 위치 (sr, sc)에서 도착 위치 (er, ec)까지 가는 최소 이동 횟수를 구해야 한다.여러 개의 테스트 케이스가 주어지므로, 각각의 결과를 출력해야 한다.2. 해결 방법🔹 핵심 개념이 문제는 그래프 탐색(BFS)를 이용하면 최적의 해결책을 찾을 수 있다.BFS는 최단 경로를 찾을 때 가장 적합한 알고리즘이다.🔑.. 2025. 2. 27.
[백준] 1992번 - 쿼드트리 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석쿼드트리는 흑백 영상 압축 방식 중 하나로, 2차원 배열을 네 개의 구역으로 나누어 표현하는 방법.주어진 영상이 모두 같은 값(0 또는 1)으로 이루어져 있다면 해당 숫자로 압축되지만, 0과 1이 섞여 있다면 네 개의 부분으로 나눈 뒤 각 부분을 다시 압축하는 방식.이 문제는 재귀적인 방식으로 2차원 배열을 압축하여 출력하는 것이 핵심.입력 조건첫 번째 줄: 영상의 크기 N (1 ≤ N ≤ 64), 항상 2의 제곱수로 주어짐두 번째 줄부터: N개의 길이가 N인 문자열 (0 또는 1)출력 조건압축된 쿼드트리 결과를 출력예를 들어, 아래와 같은 입력이 주어진다면:81111000011110000000011110000111111110000111100000000111100001111출력은 .. 2025. 2. 27.
[백준] 17471번 - 게리맨더링 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석🏙️ 문제 개요백준시의 시장이 공정한 선거를 위해 도시를 두 개의 선거구로 나누려고 한다. 각 선거구는 최소 한 개의 구역을 포함해야 하며, 모두 연결된 형태여야 한다.이때, 두 선거구의 인구 차이를 최소화하는 방법을 찾는 것이 목표다.🎯 요구사항두 개의 선거구로 구분해야 한다.각 선거구 내 구역들이 연결되어 있어야 한다.두 선거구의 인구 차이의 최솟값을 구해야 한다.선거구를 나누는 것이 불가능한 경우 -1을 출력해야 한다.2. 해결 방법🔹 핵심 개념이 문제는 브루트포스(모든 경우 탐색) + 그래프 탐색(BFS) 방식으로 해결할 수 있다.구역을 두 선거구로 나누는 모든 경우의 수를 생성N개의 구역을 두 개의 그룹으로 나누는 모든 조합을 찾는다.선거구의 크기는 최소 1개 이상이.. 2025. 2. 27.
[백준] 14889번 - 스타트와 링크 문제 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석문제 개요총 N명의 사람이 있으며, N은 짝수이다.사람들을 두 팀으로 나누어야 한다. (N/2명씩)능력치 행렬 S[i][j]가 주어지며, i번과 j번 사람이 같은 팀일 때 팀의 능력치에 추가된다.두 팀의 능력치 차이를 최소화하는 팀 구성을 찾아야 한다.제약 조건4 ≤ N ≤ 20이므로 완전 탐색(브루트포스)이 가능하지만, 효율적인 탐색 방법이 필요함.S[i][i] = 0이고, S[i][j] ≠ S[j][i]일 수 있다.팀 구성 조합을 만들고, 각 팀의 능력치를 계산한 후, 차이가 최소인 경우를 찾는다.2. 해결 방법1) 조합을 이용한 팀 구성N명을 두 개의 그룹(N/2명씩)으로 나누어야 하므로 조합을 활용한다.백트래킹을 이용하여 첫 번째 팀을 구성하고, 남은 인원은 자동으로 두 번.. 2025. 2. 21.
[백준] 1991번 - 트리 순회 풀이 및 코드 분석 (Java) 문제 링크성능 요약메모리: 273920 KB, 시간: 296 ms이번 문제는 이진 트리의 전위, 중위, 후위 순회를 구현하는 문제입니다.트리는 배열을 활용한 완전 이진 트리 방식으로 저장하고,이를 바탕으로 재귀를 이용한 트리 순회를 구현합니다.1. 문제 분석트리를 순회하는 방식은 다음과 같습니다.순회 방식순서전위 순회(루트) → (왼쪽 자식) → (오른쪽 자식)중위 순회(왼쪽 자식) → (루트) → (오른쪽 자식)후위 순회(왼쪽 자식) → (오른쪽 자식) → (루트) 입력으로 루트(A)부터 시작하는 트리 구조가 주어지며, 이를 기반으로 세 가지 순회 결과를 출력해야 합니다.예제 입력7A B CB D .C E FE . .F . GD . .G . .예제 출력ABDCEFGDBAECFGDBEGFCA2. 해결 방.. 2025. 2. 20.

티스토리툴바