탐욕(greedy)6 [Baekjoon] 1049번: 기타줄 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 해결 과정 착안 기타줄의 패키지 가격과 낱개 가격을 각각 별도의 배열에 저장한 다음 오름차순으로 정렬하고, 패키지로 구매하는 경우와 낱개를 구매하는 경우를 비교하여 문제를 해결한다. 구현 필요한 기타줄의 수를 $N$이라 할 때, 다음과 같이 두 가지 조건을 비교하여 문제를 해결할 수 있다. 패키지로 구매하는 경우와 낱개로 6 개씩 구매하는 경우를 비교한다. 패키지로 구매하는 경우와 $N$.. 2023. 12. 26. [Programmers] 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 하나의 구명보트에는 최대 2 명씩 태울 수 있으므로, 구명보트를 최소로 사용하려면 가능한 한 2 명씩 탑승을 시켜야 한다. 따라서 현재 남아있는 사람을 기준으로 가장 무거운 사람을 먼저 태운 다음, 가장 가벼운 사람을 보트에 태울 수 있는지 확인하여 태울 수 있다면 같은 보트에 태우고 그렇지 않다면 새로운 보트를 준비한다. * 가장 무거운 사람이 타고 남는 공간에 가장 가벼운.. 2023. 12. 23. [Programmers] 귤 고르기 https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 각각 크기 별로 귤을 분류하여 저장할 배열을 만들어, 같은 크기의 귤마다 몇 개씩 있는지를 파악한 다음 배열을 내림차순으로 정렬하면 탐욕 알고리즘에 기반하여 문제를 쉽게 해결할 수 있다. 구현 std::unordered_map 클래스를 활용하면 귤을 크기 별로 몇 개씩 있는지 쉽게 파악할 수 있다. 이때 std::sort() 메서드를 사용해 정렬하기 위해서는 std::uno.. 2023. 12. 6. [Baekjoon] 13305번: 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 해결 과정 착안 아래와 같이 탐욕(greedy) 알고리즘에 기반하여 문제를 해결할 수 있다. 현재 위치해 있는 도시의 주유 비용을 기준으로 삼는다. 순차적으로 우측 도시를 탐색하며 현재 도시의 주유 비용보다 주유 비용이 더 저렴한 도시를 탐색한다. 탐색에 성공하면, 현재 도시에서 주유하여 해당 도시까지 한 번에 이동한다. 탐색에 실패하면, 현재 도시에서 마지막 도시까지 한 번에.. 2023. 7. 28. [Baekjoon] 1931번: 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 과정 착안 문제를 처음 접하고 어떻게 해결할 지 막연해서 꽤 오래 고민을 했다. 최대한 많은 회의에 대해 회의실을 배정하려면 어떻게 해야할지 열심히 생각해보다가, 아래와 같은 조건들이 문제 해결의 핵심이라고 생각을 했다. 처음 생각한 조건 회의 시간이 짧은 회의들을 가능한 한 많이 배정한다. 회의실이 비는 시간을 최소로 한다(단, 회의실 배정 가능한 시간에 대해 별도의 제약이 없음에 유의) 위의 조건을 만족하면서 회의를 순차적으로 배정하다보면 결과적으로 최대한 많은 회의에 대해 회의실을 배정할 수 있을.. 2023. 6. 21. [Baekjoon] 11047번: 동전 0 https://www.acmicpc.net/problem/11047 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 문제 해결 과정 착안 동전의 수를 최소화하기 위해 가능한 한 가장 높은 단위의 화폐부터 사용하여 주어지는 금액을 맞추고자 하였다. 구현 보유하고 있는 동전의 가치가 오름차순으로 주어지므로, 스택(stack) 자료 구조를 사용해 입력받는 순서로 동전의 가치가 맞추고자 하는 금액보다 작은 경우 이를 스택에 넣도록 구현하였다. 입력이 완료.. 2023. 6. 13. 이전 1 다음
