본문 바로가기

코딩테스트 준비/백준633

[백준] 30987번 - 하루 피부과 [Java] https://www.acmicpc.net/problem/30987 1.  아이디어 2차 함수의 정적분을 구현하는 문제로 정적분에서 상수가 소거되므로 상수항을 제외한 부정적분에 적분 구간을 입력하면 값이 나오도록 calculate 메서드를 활용했다.2. 문제풀이 2차 함수와 1차 함수의 차는 계수 차로 계산하면 되고 이후 적분값을 메서드로 구하는 방법으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(.. 2025. 3. 10.
[백준] 2170번 - 선 긋기 [Java] https://www.acmicpc.net/problem/2170 1.  아이디어 그리디 알고리즘과 스위핑 알고리즘으로 해결할 수 있었다.2. 문제풀이 일반적인 그리디 알고리즘이랑 스위핑 두 가지 방식으로 접근했다.그리디 알고리즘은 선의 x 좌표를 기준으로 오름차순 정렬한 우선순위 큐(items)와 y 좌표를 기준으로 내림차순 정렬한 우선순위 큐(pq) 두 개를 사용했다. items에서 원소(item)를 하나씩 꺼내서 pq의 원소(cur)와 비교하며 item과 cur이 겹치는 부분이 있으면 두 선을 합친 선을 pq에 다시 삽입하고 겹치는 부분이 없으면 각각 삽입하는 방식으로 구현했다. 이후 pq의 모든 선을 꺼내서 길이를 합하면 된다.스위핑은 x 좌표를 기준으로 오름차순, x 좌표가 같으면 y 좌표를 기.. 2025. 3. 7.
[백준] 11000번 - 강의실 배정 [Java] https://www.acmicpc.net/problem/11000 1.  아이디어 그리디 알고리즘으로 해결할 수 있었다.시작 시간에 대한 오름차순 정렬 우선순위 큐와 종료 시간에 대한 오름차순 우선순위 큐 두 개를 활용해서 해결할 수 있다.2. 문제풀이 시작 시간에 대한 오름차순 우선순위 큐를 items, 종료 시간에 대한 오름차순 우선순위 큐를 pq로 선언했다.pq에 items의 첫번째 원소를 삽입한채로 시작하며 pq의 peek의 종료 시간보다 items의 peek의 시작 시간이 늦으면 pq의 해당 강의 뒤에 items의 강의를 붙이는 개념으로 생각할 수 있어서 pq의 해당 원소를 제거했다.pq에서 제거했으면 뒤에 붙이는 거니 pq에 삽입해야하고 pq에서 제거하지 않았어도 새로운 강의실이 필요한 것이.. 2025. 3. 6.
[백준] 2457번 - 공주님의 정원 [Java] https://www.acmicpc.net/problem/2457 1.  아이디어 그리디 알고리즘으로 해결할 수 있었다.시작일에 대한 오름차순 정렬 우선순위 큐와 종료일에 대한 내림차순 우선순위 큐 두 개를 활용해서 3월 1일부터 피어있는 꽃 중 가장 지는 날이 늦을 꽃을 선택하고 현재 날짜를 갱신 후 다시 현재 날짜에 피어 있는 꽃 중 가장 지는 날이 늦은 꽃을 선택하는 과정을 반복했다.2. 문제풀이 최초 모든 꽃은 시작일에 대한 오름차순 우선순위 큐에 담았다.이후 현재 날짜를 3월 1일로 세팅해서 3월 1일에 피어져 있는 꽃들을 임시 우선순위 큐에 담고 이 중 가장 지는 날이 늦은 꽃 하나만 선택했다. 이후 현재 날짜를 다시 갱신하고 현재 날짜 기준 피어져 있는 꽃들을 다시 임시 우선순위 큐에 담는 .. 2025. 3. 5.
[백준] 7570번 - 줄 세우기 [Java] https://www.acmicpc.net/problem/7570 1.  아이디어 가장 긴 연속하며 증가하는 번호로 이루어진 부분 수열을 구하고 수열에 해당하지 않는 번호를 적절하게 앞 뒤로 이동시키는 그리디 알고리즘과 다이나믹 프로그래밍으로 해결할 수 있다.2. 문제풀이 dp 배열을 먼저 선언했고 dp 배열은 인덱스에 해당하는 숫자로 끝나는 가장 긴 연속하며 증가하는 부분 수열의 길이를 저장한다.점화식은 dp[idx] = dp[idx-1] + 1 로 연속해야하므로 해당 숫자보다 1 작은 숫자로 끝나는 가장 긴 연속하며 증가하는 부분 수열의 길이 + 1을 해주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public stati.. 2025. 3. 4.
[백준] 1744번 - 수 묶기 [Java] https://www.acmicpc.net/problem/1744 1.  아이디어 그리디 알고리즘으로 해결할 수 있다.1 보다 큰 정수는 값이 큰 정수부터 2개씩 묶을수록 최대가 되고, 1은 그냥 더할 때 최대가 된다.0 이하인 정수는 절댓값이 큰 정수부터 2개씩 묶을수록 최대가 된다.2. 문제풀이 1 보다 큰 정수를 담은 우선순위 큐와 0 이하인 정수를 담은 우선순위 큐 두 개를 활용했다.1은 따로 담지 않고 바로 더해줬다.1 보다 큰 정수를 담은 우선순위 큐는 절댓값이 큰 수부터 묶어야하므로 우선순위 큐의 길이가 홀수면 앞의 수 하나는 빼서 그냥 더하고 나머지는 묶는 식으로 구현했고,0 이하인 정수를 담은 우선순위 큐도 절댓값이 큰 수부터 묶어야하므로 하나밖에 안남아서 묶을 수 없으면 그냥 더하는 조.. 2025. 3. 4.
[백준] 32951번 - AI 선도대학 [Java] https://www.acmicpc.net/problem/32951 1.  아이디어 주어진 연도에서 2024년을 빼면 몇 년이 지났는지 간단하게 알 수 있다.2. 문제풀이 아이디어 그대로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); System.out.println(N - 2024); }}4. 후기 2025. 3. 3.
[백준] 25370번 - 카드 숫자 곱의 경우의 수 [Java] https://www.acmicpc.net/problem/25370 1.  아이디어 중복 순열을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 1부터 9까지의 카드를 중복해서 선택할 수 있고 7장을 선택했을 때 곱의 경우의 수를 구하는 문제로 선택을 중복 순열로 찾아나가며 값을 파라미터로 들고 다녔다. 이후 7장의 선택이 끝나면 Set에 넣는 과정을 반복했고 경우의 수는 Set의 크기를 구하면 된다.3. 코드 package day_01.BOJ_25370;import java.io.*;import java.util.*;public class Main { private static final Set set = new HashSet(); private static int N; public s.. 2025. 3. 3.
[백준] 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.

티스토리툴바