본문 바로가기

전체 글667

[백준] 1106번 - 호텔 [Java] https://www.acmicpc.net/problem/1106 1.  아이디어 무한 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.고객을 무게, 돈을 가치로 생각하면 되며 C명 이상을 담았을 때 최솟값을 구해야 하는 점에 주의해야한다.2. 문제풀이 1차원 dp, 2차원 dp 두 가지 방식으로 풀어봤고 최솟값을 저장하는 배낭 문제여서 최댓값으로 초기화한 후 최솟값을 저장하도록 했다.C명 이상인 최솟값을 구해야하는 조건에서 정확히 C명일 때를 구하는게 아님에 주의해야하고 돈을 정수배만큼 투자할 수 있다는 점에서 무한 배낭 문제임에 주의해야한다.이를 위해 dp의 크기를 C보다 크게 설정해야하는데 한번 배낭에 담을 때 고객이 최대 100명이므로 100만큼 더 크게 설정했고 중복으로 담을 수 있어서 현재.. 2025. 3. 3.
[백준] 16493번 - 최대 페이지 수 [Java] https://www.acmicpc.net/problem/16493 1.  아이디어 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.챕터의 종류가 최대 20가지여서 부분집합을 활용해서도 해결할 수 있었다.2. 문제풀이 부분집합은 재귀를 통한 완전탐색으로 진행하되 N일이 넘어가는 집합은 더 탐색하지 않도록 백트래킹을 했다.다이나믹 프로그래밍은 날짜를 인덱스 값을 페이지 수로 하는 일반적인 0-1 배낭으로 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main_PowerSet { private static class Item { int day; int page; public Item(i.. 2025. 2. 27.
[백준] 7579번 - 앱 [Java] https://www.acmicpc.net/problem/7579 1.  아이디어 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.앱을 비활성화하는 비용을 무게, 앱을 비활성화해서 확보할 수 있는 메모리를 가치로 생각하면 된다.2. 문제풀이 1차원 dp, 2차원 dp 두 가지 방식으로 모두 풀어봤고 dp 테이블에는 확보할 수 있는 메모리를, 인덱스에는 비활성화하는데 필요한 비용을 두면 된다. 비활성화하는데 필요한 비용이 0일 수 있어서 인덱스 0부터 모두 사용하고 이후 정답을 찾을 때도 0번 인덱스부터 탐색을 해야한다. 정답은 최소 비용으로 M 이상의 메모리를 확보해야하는데 인덱스 자체가 이미 정렬이 된 개념이어서 앞에서부터 순회하면 된다.3. 코드 import java.io.*;import .. 2025. 2. 27.
[백준] 2294번 - 동전 2 [Java] https://www.acmicpc.net/problem/2294 1.  아이디어 무한 배낭 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 각 가치를 만드는데 필요한 동전의 최소 개수를 저장하는 문제로 역시 주어지는 동전의 종류가 늘어난다고 생각하는 배낭 스타일로 풀 수 있다. dp 테이블의 초기화가 중요한데 0원을 만드는데는 동전이 필요없으니 0개이고 나머지 금액을 만드는데는 동전이 무한히 많이 필요하다고 초기화를 해줘서 이후 갱신과정에서 최소 개수로 갱신이 되도록 해줘야 한다.3. 코드 import java.io.*;import java.util.*;public class Main_1D { private static final int MAX = 10001; public.. 2025. 2. 27.
[백준] 2293번 - 동전 1 [Java] https://www.acmicpc.net/problem/2293 1.  아이디어 무한 배낭 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 각 동전에 번호를 매긴 후 1번 동전만 주어졌을 때 사용해서 만들 수 있는 경우의 수, 1번, 2번 동전만 주어졌을 때 사용해서 만들 수 있는 경우의 수 이렇게 동전의 종류를 확장하며 풀어가면 된다. 다음 동전 종류가 주어졌을 때 기존의 조합으로도 각 경우를 만들 수 있으므로 해당 경우는 그대로 두고 새로운 동전으로 만들 수 있는 경우는 새로운 동전의 가치를 뺀 금액을 만들 수 있는 경우의 수로 찾으면 된다. 이때 같은 동전을 여러 개 사용할 수 있어서 새로운 동전이 주어진 상황에서의 금액과 비교해야한다.3. 코드 import java.io.*;.. 2025. 2. 27.
[백준] 2629번 - 양팔저울 [Java] https://www.acmicpc.net/problem/2629 1.  아이디어 TopDown, BottomUp 다이나믹 프로그래밍을 활용해서 해결했다.2. 문제풀이 TopDown 방식은 부분집합을 구하는 재귀 메서드와 메모이제이션을 활용했는데 부분집합은 해당 추를 사용하지 않거나 왼쪽 팔에 추를 올리거나 오른쪽 팔에 추를 올리는 3가지 경우가 있다.추의 개수가 최대 30개이므로 모든 경우의 수는 3^30가지가 되고 이건 시간초과가 발생하게 된다. 이를 해결하기 위해 boolean 타입 2차원 배열을 활용해 해당 추까지 주어졌을 때 구할 수 있는 무게를 방문 체크하고 방문된 경우를 만나면 바로 종료하도록 했다.파라미터로는 추의 번호와 구할 수 있는 무게를 들고 다녔고 구할 수 있는 무게는 왼쪽 팔 - .. 2025. 2. 26.
[백준] 9084번 - 동전 [Java] https://www.acmicpc.net/problem/9084 1.  아이디어 Coins 문제와 동일한 문제다.([코딩테스트 준비/백준] - [백준] 3067번 - Coins [Java])2. 문제풀이 동일하게 다이나믹 프로그래밍을 활용한 무한 배낭으로 해결했다.3. 코드 import java.io.*;import java.util.*;public class Main_1D { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedW.. 2025. 2. 26.
[백준] 3067번 - Coins [Java] https://www.acmicpc.net/problem/3067 1.  아이디어 무한 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.직관적인 2차원 dp 테이블을 활용한 방식과 좀 더 발전한 1차원 dp 배열을 활용한 방식으로 해결했다.2. 문제풀이 2차원 dp 테이블은 행을 동전의 번호, 열을 방법의 수로 하면 되고 1차원 dp 배열은 방법의 수를 인덱스로 하면 된다.방법의 수는 현재 동전을 사용해서 만들 수 있는 경우의 수와 현재 동전을 사용하지 않고 만들 수 있는 경우의 수의 합으로 구할 수 있다.2차원 dp 테이블의 경우 0원을 만들 수 있는 경우는 1가지이므로 모든 행의 0번 인덱스는 1로 초기화했다.방법의 수를 구하기 위해 dp 테이블의 각 칸은 현재 동전을 사용하지 않고 만들 수 있는.. 2025. 2. 26.
[백준] 12865번 - 평범한 배낭 [Java] https://www.acmicpc.net/problem/12865 1.  아이디어 대표적인 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.직관적인 2차원 dp 테이블을 활용한 방식과 좀 더 발전한 1차원 dp 배열을 활용한 방식으로 해결했다.2. 문제풀이 2차원 dp 테이블은 행을 물건의 번호, 열을 무게로 하면 되고 1차원 dp 배열은 무게를 인덱스로 하면 된다.2차원 dp 테이블은 행 번호가 늘어날수록 고려하는 물건의 종류가 늘어난다고 생각하면 되고 현재 번호의 물건을 담았을 때와 안 담았을 때 중 최댓값을 찾으면 된다.1차원 dp 배열은 2차원 dp 테이블이 이전 행의 정보로 현재 행을 구성하는 점에 착안해 갱신해주면 되고 이때 인덱스를 뒤에서부터 갱신해줘서 같은 물건이 중복으로 담기.. 2025. 2. 26.
[백준] 23290번 - 마법사 상어와 복제 [Java] https://www.acmicpc.net/problem/23290 1.  아이디어 마법 연습의 각 작업을 메서드로 분리하고 조립해서 로직을 구현하는 방식으로 접근했다.2. 문제풀이 물고기는 위치와 방향을 담은 객체로 관리하며 Queue로 다뤘다.각 위치의 물고기 수를 저장하기 위한 카운팅 맵과 각 위치에서 냄새의 남은 시간을 저장하기 위한 카운팅 맵을 활용했다.작업 1은 작업 5에서 복제를 하기 위해 현재 물고기 정보를 따로 보관해야한다.작업 2는 물고기의 이동으로 델타배열을 통해 회전을 구현하고 상어 위치와 냄새 위치를 기록해서 구현하면 된다.작업 3은 상어의 이동으로 DFS 알고리즘을 통한 완전 탐색으로 진행했고 방문 체크 및 방문 해제로 물고기를 중복으로 제외하지 않게 주의하면서 탐색했고 가장 많.. 2025. 2. 24.
[백준] 21611번 - 마법사 상어와 블리자드 [Java] https://www.acmicpc.net/problem/21611 1.  아이디어 달팽이 배열을 활용한 다양한 연산을 하는 문제로 구슬을 파괴 후 재배치 -> 구슬의 폭발과 재배치 반복 -> 구슬의 변화 순서가 반복된다.각 단계를 수행하는 메서드를 작성해서 조합하는 방식으로 해결했고 달팽이 배열의 이동을 처리하기 위해 Queue와 Deque, 델타 배열을 활용했다.2. 문제풀이 달팽이 배열의 회전 방향에 맞춰 반시계 방향으로 델타 배열을 만들었고 입력의 d를 이 델타 배열에 맞추기 위한 배열도 선언했다. 이후 각 마법에 대해 destroy 메서드를 호출했는데 해당 메서드에서 마법의 한 사이클을 전부 수행했다. 먼저 구슬을 파괴한 후 재배치를 해야하는데 이때 달팽이 배열의 순회로 구슬을 Queue에 담고.. 2025. 2. 23.
[백준] 20058번 - 마법사 상어와 파이어스톰 [Java] https://www.acmicpc.net/problem/20058 1.  아이디어 2차원 배열의 회전, 얼음의 양 줄이기, 가장 큰 얼음 덩어리의 크기를 각각 구현해서 합치면 되는 문제로 2차원 배열의 회전읜 격자의 크기와 동일한 크기의 배열과 인덱스의 활용으로, 얼음 양 줄이기는 Queue를 활용해서, 가장 큰 얼음 덩어리의 크기는 BFS, DFS 알고리즘으로 구할 수 있다.2. 문제풀이 얼음판의 크기는 2^N으로 주어지는데 편의를 위해 N을 2^N으로 바꿔서 이용했다. 이를 위해 비트 연산자를 활용했다. 격자의 크기 역시 비트 연산으로 L을 2^L로 바뀌줬고 이후 회전 메서드에서 이용했다. 회전은 두 2차원 배열의 크기가 다른 점만 주의해서 구현하면 된다. 얼음의 양 줄이기는 사방탐색으로 줄여야 하.. 2025. 2. 23.

티스토리툴바