그리디 알고리즘30 [백준] 1946번 - 신입 사원 [Java] https://www.acmicpc.net/problem/1946 1. 아이디어 두 성적 모두 다른 지원자 보다 떨어지는 자는 선발하지 않으므로 한 성적을 기준으로 정렬한 후 순회하며 정렬 기준이 아닌 다른 성적에 대해 이전 모든 지원자 보다 떨어지면 선발하지 않으면 된다.2. 문제풀이 성적은 1부터 N 중 중복되지 않는 수 이므로 1차원 배열을 활용해 한 성적을 인덱스, 한 성적은 값으로 하면 인덱스로 한 성적을 기준으로 정렬이 된 것으로 볼 수 있다. 배열을 순회하며 값의 최솟값을 갱신하며 저장하고 이 값을 현재 배열의 값과 비교하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(S.. 2025. 3. 18. [백준] 11501번 - 주식 [Java] https://www.acmicpc.net/problem/11501 1. 아이디어 최대 이익을 내려면 현재 날짜보다 이후 날짜 중 더 비싼 날이 있을 때 이중 가장 비싼 날 팔아야한다. 이를 위해 뒤에서부터 순회하며 해당 날짜의 가격이 현재까지 찾은 최대 가격보다 싸면 사서 팔고 비싸면 최대 가격을 갱신하는 과정을 반복했다.2. 문제풀이 아이디어 그대로 구현했다.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. 13. [백준] 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. [백준] 2810번 - 컵홀더 [Java] https://www.acmicpc.net/problem/2810 1. 아이디어 일반 좌석은 하나 늘어나면 컵홀더도 같이 늘어나서 왼쪽 컵홀더를 매칭시키면 커플 좌석만 남는 상태로 만들 수 있다. 이때 커플 좌석의 왼쪽 사람을 왼쪽 컵홀더에 매칭시키면 커플 좌석의 수 / 2 만큼의 사람이 남는데 맨 오른쪽에 한 명을 매칭시키면 커플 좌석의 수 / 2 - 1 만큼의 사람만 컵홀더를 사용할 수 없다.2. 문제풀이 StringTokenizer로 S를 기준으로 파싱을 해서 일반 좌석과 커플 좌석을 구분했고 ans에는 일반 좌석의 수, cnt에는 커플 좌석에서 컵홀더를 사용한 사람의 수를 기록했다.3. 코드 import java.io.*;import java.util.*;public class Main { .. 2025. 2. 13. [백준] 1343번 - 폴리오미노 [Java] https://www.acmicpc.net/problem/1343 1. 아이디어 사전순으로 앞서려면 AAAA를 최대한 일찍 사용해야 한다.2. 문제풀이 StringTokenizer로 '.'을 구분자로 설정해서 파싱을 먼저 했다. 이후 토큰들에 대해 '.'이면 넘어가고 'X'의 뭉치면 AAAA를 먼저 적용해서 4로 나눈 몫만큼 먼저 쓰고 4로 나눈 나머지만큼 B를 사용했다. 이때 AAAA와 BB 둘 다 문자가 짝수개이므로 'X'의 뭉치의 길이가 홀수면 불가능한 케이스다. 3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 12. [백준] 1781번 - 컵라면 [Java] https://www.acmicpc.net/problem/1781 1. 아이디어 그리디 알고리즘으로 해결할 수 있다.현재 날짜를 N일부터 1일까지 이동하며 해당 일에 풀 수 있는 문제 중 가장 컵라면을 많이 받는 문제들을 푸는 과정을 반복하면 된다.2. 문제풀이 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐와 컵라면 수에 대해 내림차순으로 정렬하는 우선순위 큐를 사용했다.입력을 받아 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐에 담은 후 for문으로 각 날짜에 대해 해당 날짜에 풀었을 때 컵라면을 받을 수 있는 문제들을 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐에서 컵라면 수에 대해 내림차순으로 정렬하는 우선순위 큐로 옮겼다.3. 코드 import java.io.*;import .. 2025. 2. 11. [백준] 1202번 - 보석 도둑 [Java] https://www.acmicpc.net/problem/1202 1. 아이디어 그리디 알고리즘으로 해결할 수 있다.가방들을 크기가 작은 순으로 정렬한 후 각 가방에 담을 수 있는 무게의 보석들 중 가장 가격이 높은 보석을 담는 과정을 반복하면 된다.2. 문제풀이 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐와 보석의 가격에 대해 내림차순으로 정렬하는 우선순위 큐를 사용했다.입력을 받아 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐에 담은 후 각 가방에 대해 해당 가방에 담을 수 있는 무게의 보석들을 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐에서 보석의 가격에 대해 내림차순으로 정렬하는 우선순위 큐로 옮겼다.3. 코드 import java.io.*;import java.u.. 2025. 2. 11. [백준] 13975번 - 파일 합치기 3 [Java] https://www.acmicpc.net/problem/13975 1. 아이디어 두 파일을 합치는 과정을 반복할 때 작은 두 파일을 합치는 과정을 반복해야 최소 비용으로 하나의 파일로 만들 수 있다. 이를 위해 우선순위 큐를 활용했다.2. 문제풀이 우선순위 큐에 초기 파일들을 담은 후 두 파일을 꺼내서 합친 후 다시 우선순위 큐에 넣는 과정을 반복했다. int형 오버플로우가 발생할 수 있음에 주의해야 한다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea.. 2025. 2. 11. 이전 1 2 3 다음
