본문 바로가기

백준4

[백준] 11286번 - 절댓값 힙 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석📌 문제 개요절댓값 힙은 절댓값이 작은 순서대로 값을 정렬하는 힙(우선순위 큐)이다.만약 절댓값이 동일하다면 값이 작은 수가 우선순위를 갖는다.이 힙을 이용해 주어진 연산을 수행하는 프로그램을 작성해야 한다.🎯 요구사항정수 x를 힙에 추가 (x ≠ 0일 경우)절댓값이 가장 작은 값 출력 & 삭제 (x == 0일 경우)같은 절댓값을 가진 값이 여러 개일 경우, 값이 작은 수를 먼저 출력힙이 비어 있다면 0을 출력N의 최대 크기가 100,000이므로 O(log N) 이하의 연산 속도가 필요하다.2. 해결 방법🔹 핵심 개념우선순위 큐(Priority Queue) 를 활용하여 데이터를 정렬하고 관리할 수 있다.우선순위 큐에서 커스텀 정렬을 적용하여, 절댓값이 작은 순서 + 값이 작은.. 2025. 2. 27.
[백준] 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.

티스토리툴바