코딩테스트
[백준] 동전 1
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍을 사용하는 문제입니다. 메모리를 많이주지 않아, 불필요한 할당을 하니 처음에 메모리 초과가 나왔는데 둘다 설명해 보도록 하겠습니다. 우선 문제부터 요약하면, n가지 종류의 동전으로 가치합을 k로 만드는 경우의 수를 return 해야 합니다. 1,2,5의 가치를 가진 동전으로 10의 가치를 만드는 경우는 10가지 이므로 10을 return 해야 합니다. 우선 아이디어는 다음과 같습..
[백준] 포도주 시식
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 요약하면, 포도주가 시식대에 놓여있는데 이중에서 3개를 연속해서 마실수 없을 때, 최대한 많은 포도주를 마시고 싶을 때, 마신 포도주의 양을 return 해야 합니다. 프로그래머스의 도둑질 문제와 유사합니다. 대표적인 dp문제인데 주로 2개짜리에 대한 이러한 문제는 유명하게 알려져 있습니다. 이 문제 또한 경우를 조금만 더 쪼개서 풀면 됩니다..
[프로그래머스] 이중우선순위큐
https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr heap을 두개 이용하는 문제입니다. 우선 문제부터 요약하면, 숫자를 넣고, 최댓값을 없애고, 최솟값을 없애는 총 3가지 명령어가 있습니다. 이때, 모든 명령어들을 처리하고 난 후의 상태를 return 해주는 문제입니다. 실제 명령어가 생긴 형태는 다음과 같고 좀더 자세한 내용은 실제 문제 링크를 이용해서 읽어 보는 것을 추천합니다. 아이디어는 두 heap을 어떻게 동기화 시킬 것이냐가 중요합니다. 잘못된 풀이들에는 1. del[index] 로 마지막 것을 그냥 없애줌 (min heap에서 가장 마지막 index가 최댓값이 아님) 2. r..
[프로그래머스] 더 맵게
https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr heap을 이용하는 문제입니다. 우선 문제부터 간단하게 요약해보면, 매번 매운음식의 array 안에서 가장 덜매운 음식과, 두번째로 덜매운 음식을 꺼내서 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 다음과 같이 섞은후 다시 넣어주는 과정을 반복해 모든 음식이 일정량 보다 매워..