본문 바로가기

그리디 알고리즘

[백준 2212] 센서 (JAVA)

CodingTEST 2023. 10. 19. [백준 2212] 센서 (JAVA) 백준 2212번 문제 - 센서 문제 분석 주어진 N개의 센서들을 K개의 집중국과 연결해라 집중국 유지비 문제로 인해 집중국의 수신 가능 영역의 길이의 합을 최소화 해야함 해결 키 포인트 센서 값을 오름차순으로 정렬 근처 값과의 차이 값을 구하기 차이 값을 오름차순 정렬 인덱스 0번 값 부터 N-K값까지 다 더한다 코드 import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(S..

[백준 13164] 행복 유치원 (JAVA)

CodingTEST 2023. 10. 18. [백준 13164] 행복 유치원 (JAVA) 백준 13164번 문제 - 행복 유치원 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 문제 분석 주어진 N명의 원생들을 K개의 조로 나눈다. 나누어진 조 비용 : 조에서 가장 큰 사람 키 - 조에서 가장 작은 사람 나누어진 조 비용의 합을 출력해라 해결 키 포인트 해결 방식 1 - 실패 최대 차이 값 = (가장 큰 값 - 가장 작은 값) / K 조의 비용이 최대 차이 값을 넘기지 않게만 조를 나누고 그 차이 값들을 더한다 해결 방식 2 - 성공 근처 값과의 차이 값을 구하기 차이 값을 오름차순 정렬 인덱..

[프로그래머스] 체육복 (JAVA)

CodingTEST 2023. 10. 11. [프로그래머스] 체육복 (JAVA) 프로그래머스 - [Level 1] 체육복 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 체육복이 도둑맞아 여분 체육복이 있는 친구들은 친구에게 옷을 나눠줘 체육수업을 들어야한다. 여분을 가진 사람은 체육복은 앞 뒤 사람에게만 빌려줄 수 있고, 자신이 도둑맞았을 경우는 자신이 입어야한다. 이때 체육수업을 들을 수 있는 학생의 최댓 값을 출력 해결 키 포인트 여분을 가져온 사람, 도난받은 사람 리스트는 순서대로 되어 있지 않다 정렬이 필수 ! 도난당한 학생들만 확인 본인 혹은 위 아래 애 중에 여분 옷을 가져온 애가 있는지 확인 → 있을 경우 여분..

[백준 1541] 잃어버린 괄호 (JAVA)

CodingTEST 2023. 8. 13. [백준 1541] 잃어버린 괄호 (JAVA) 백준 1541번 문제 - 잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 분석 문자열이 주어지면 해당 문자열이 실제로 계산될 때 괄호를 사용해 최솟값을 만들어 출력해라 해결 키 포인트 그리디 알고리즘 최솟값을 만들기 위해서는 최대로 많은 수가 - 되야 한다. 즉, 괄호를 - 앞 뒤에 두어야 함 - 앞 뒤 문자열, + 앞 뒤 문자열을 나누기 위해 split 를 사용 s.split("-") s.split("\\+") s.split("+")로 하면, java.util.regex.Patter..

[백준 1931] 회의실 배정 (JAVA)

CodingTEST 2023. 8. 12. [백준 1931] 회의실 배정 (JAVA) 백준 1931번 문제 - 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 분석 회의 시작, 끝 시간이 주어지고, 이를 토대로 회의실 사용표를 정한다. 이때 한 회의실에 몇개의 회의가 주어지는지를 구하고, 최대 회의 수를 출력해라. 해결 키 포인트 그리디 알고리즘 회의 시간에 따라 오름차순 정렬 회의 끝 시간으로 정렬 회의 끝 시간이 같을 경우, 시간 시간으로 정렬 그리디 알고리즘 (탐욕 알고리즘) 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 쉽게 말해, 지금의 최선 = 전체의 최선 뒤에 사진에서 서울에서 부산까지의 최소거리를 구하고자할 때, 서울에서..

[백준 1744] 수 묶기 (JAVA)

CodingTEST 2023. 8. 12. [백준 1744] 수 묶기 (JAVA) 백준 1744번 문제 - 수 묶기 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 분석 수열이 주어졌을 때, 순서와 상관없이 더하거나 곱해 최대 값을 알아내 출력해라 곱하는 것은 한번 혹은 안하는 것만 가능하다 해결 키 포인트 Arrays.sort() 사용 그리디 알고리즘 사용 양수와 음수 다르게 계산 양수: 큰 수끼리 곱한다. 음수: 작은 수끼리 곱한다. 그리디 알고리즘 (탐욕 알고리즘) 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 쉽게 말해..

[백준 1715] 카드 정렬하기 (JAVA)

CodingTEST 2023. 8. 12. [백준 1715] 카드 정렬하기 (JAVA) 백준 1715번 문제 - 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 분석 모든 카드를 합치기 위해 사용되는 합치는 최소 횟수를 구하고 출력해라. 해결 키 포인트 그리디 알고리즘 사용 가장 작은 수들끼리 먼저 합치는 것이 이 문제의 핵심 하지만, 시간도 메모리도 여유롭지 않다 List 사용 - 메모리, 시간 초과 ArrayList 사용 - 시간 초과 뽑아내고 넣고 정렬하고의 반복으로 메모리, 시간 초과가 난다 우선순위 큐 사용으로 메모리, 시간을 최소화한다. 그리디 알고리..

[백준 11047] 동전 0 (JAVA)

CodingTEST 2023. 8. 12. [백준 11047] 동전 0 (JAVA) 백준 11047번 문제 - 동전 0 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 분석 가능한 동전 가치 n개를 오름차순으로 입력 받고, 앞서 입력받은 k 값을 만들기 위한 최소한의 동전 수를 구해 출력해라. 해결 키 포인트 그리디 알고리즘 이용 입력 받고, 동전을 확인할 때는 내림차순으로 확인 그리디 알고리즘 (탐욕 알고리즘) 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 쉽게 말해..

이전 1 다음

티스토리툴바