욕심쟁이 알고리즘2 [BOJ] 백준 18310번 - 안테나(with Java) 알고리즘 잘못된 아이디어를 떠올려서 시간초과가 난 이유에 대해서 고민하다가 결국 풀지 못하고 구글링을 통해서 해결하였다. 처음에는 각각의 집에 대해서 다른 집들과의 거리의 합을 비교해서 합이 최소인 집을 구하는 방식으로 접근하였다. 하지만 입력이 최대 20만에 도달했기 때문에 시간복잡도는 O(N^2)로 시간초과가 나게 돼서 풀이에 실패하였다. 구글링을 통해서 다른 사람들이 푼 코드를 참고해보니 풀이가 의외로 간단하였다. 집들을 전부 오름차순으로 정렬시킨 후에 중간에 위치한 집을 찾는 것이 전부였다. 알고리즘을 위와 같이 짜게 되면, 어떤 테스트케이스가 주어져도 각각의 집에 대한 합이 최소값을 이루게 된다. 소스코드 문제링크 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200.. 2021. 12. 14. [BOJ] 백준 11047번 - 동전 0(with Java) 알고리즘 욕심쟁이 알고리즘의 대표적인 문제로 원래는 동적계획법을 사용해야 최적의 해를 도출할 수 있지만, 주어지는 동전이 특이하기 때문에 욕심쟁이 알고리즘을 사용해야만 최적의 해를 도출할 수 있다. 왜 그런지는 추후에 설명하기로 하겠다. K원보다 작거나 같은 경우에 대해서 동전의 값을 빼고 K를 업데이트하는 과정을 K가 0이 될 때까지 반복해주면 풀 수 있다. 문제에서 요구하는 것은 K원을 최소로 만드는 동전의 개수이므로, 횟수를 세기 위한 변수 cnt를 이용해서 K에서 값을 빼줄 때마다 cnt를 1씩 증가시켜주면 문제에서 요구하는 답을 도출할 수 있다. 소스코드 문제링크 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개.. 2021. 8. 1. 이전 1 다음
