드디어 때가 왔다...
취준을 하다보면 빼놓을 수가 없는 단계가 있다.
코딩테스트
이번 주간은 알고리즘에 대해 공부하면서 문제에 접근할 수 있는 풀이 방법을 머리에 익혀두는 시간을 가진다. 그 중에서도 첫 타자로 완전탐색과 그리디 알고리즘을 먼저 간략하게 정리하도록 하겠다.
완전탐색
완전탐색이라는 이름에서 짐작할 수 있듯이 전체 경우의 수를 모두 확인하는 방법이다.
휴대폰 잠금 비밀번호가 숫자 4자리라면 101010*10=10000가지 조합을 다 검사해보는 것과 같다.
순차적인 탐색 방법을 주로 사용하므로 이때까지 자주 썼던 for문이나 while문같이 반복동작을 제시된 범위 내에서 수행해 정답을 찾는 방식이 된다.
확실한 정답을 찾을 수 있다는 점에서 장점이 되겠지만 빅데이터의 시대에는 적절하지 못하다.(물론 문제 유형이나 상황에 따라 강력한 어필이 될 수도 있지만) 찾아야 하는 데이터 양이 많거나 문제가 복잡할 수록 반복 동작을 많이많이 수행해야 하기 때문에 연산 속도가 길어지거나 성능이 저하될 가능성이 크다.
실제로 지난번 물류 과제 프로젝트를 작성할 때 수많은 반복문을 적어놨더니 실행할 때 걸리는 시간이 늘어나서 프로그램이 무겁다는 걸 실감했다.
모델을 공부할 때 폭포수 모델을 먼저 배우듯이 성능이 안 좋은 완전탐색 알고리즘을 먼저 학습했다. 그렇다면 이제 여러가지 문제 상황에 적합한 방법을 배워야 하겠지??
그리디 알고리즘
Greedy Algorithm은 문제를 나눠서 각 단계에서 최적의 해결방법을 선택하는 방식이다.
단계별로 최적의 선택을 하므로 결합했을 때 전체적인 시야에서는 최적의 선택이 아니게 될 수 있다. 그래서 적용할 수 있는 문제 유형이 한정적이다. = 문제 유형을 익혀두면 '아, 이 문제는 그리디 알고리즘으로 접근하면 되겠구나!'라고 판단할 수 있다.
아래의 조건을 만족해야 그리디 알고리즘을 사용할 수 있다.
- 탐욕 선택 속성...?
각 단계에서 선택한 방법은 최종 답의 최적성을 유지해야 한다.- 최적 부분 구조
전체 문제의 최적해가 문제를 나눈 각 부분 문제의 최적해를 결합해서 얻을 수 있어야 한다.
처음에 이 내용을 봤을 땐 1번과 2번이 부분 ↔ 전체를 서로 오가며 적합성을 유지할 수 있어야 한다는 내용이라고 생각했다. 이러면 너무 확대해석이고 이 둘을 구분해서 보는게 중요하다.
탐욕 선택 속성은 문제 해결 과정 속에서 각 단계별 선택의 정당성을 보장하는게 중요하다. 최종 선택이 결정되었을 때 과정을 돌아봐도 최선의 선택을 했다는 걸 보일 수 있어햐 한다.
최적 부분 구조는 전체 문제가 단계별로 구분해 최적의 답을 구할 수 있는 문제 구조인지 점검하는게 중요하다. 이 조건 때문에 적용할 수 있는 문제 유형이 적은게 아닐까?
해결 방법 실습
철수는 물건을 구매하고 거스름돈을 받아야 합니다. 가게에는 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정할 때, 특정 금액을 거슬러주기 위한 최소한의 동전 개수를 구하는 프로그램을 작성해보세요.
입력
첫째 줄에 거슬러 주어야 할 금액 N이 주어집니다. (0 ≤ N ≤ 10,000)
사용할 수 있는 동전의 종류: 500원, 100원, 50원, 10원
출력
거스름돈 N원을 만들기 위한 최소 동전 개수를 출력합니다.
아직 위 문제의 코드를 다 완성 못해서 두 가지 다 작성한 뒤 수정해보도록 하겠다.
(25. 10. 01)
완전탐색 풀이 코드
public class BruteForce {
public static int main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("거슬러 줘야 하는 금액을 입력하세요.(0 ≤ N ≤ 10,000)");
int[] coins = new int[]{500, 100, 50, 10};
int num = input.nextInt();
int minCoins = Integer.MAX_VALUE;
int[] maxCoins = new int[coins.length];
for(int i = 0; i < coins.length; i++){
maxCoins[i] = num/coins[i];
}
//500*i + 100*j + 50*k + 10*l = N
for(int i = 0; i <= maxCoins[0]; i++){
for(int j = 0; j <= maxCoins[1]; j++){
for(int k = 0; k <= maxCoins[2]; k++){
for(int l = 0; l <= maxCoins[3]; l++){
int sum = coins[0]*i + coins[1]*j + coins[2]*k + coins[3]*l;
if(sum == num) {
minCoins = Math.min(minCoins, i+j+k+l);
}
}
}
}
}
System.out.println("최소 동전 갯수: " + minCoins);
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}
}그리디 알고리즘 풀이 코드
public class GreedyAlgorithm {
public static int Solution(int money, int[] coins) {
int remain = money;
int countCoins = 0;
for(int i = 0; i < coins.length; i++){
countCoins += remain/coins[i]; //사용한 동전의 개수를 합산
remain %= coins[i]; //동전이 가질 수 있는 최대 금액을 제한 나머지 금액 저장
}
return countCoins;
}
public static void main(String[] args) {
//elements 초기화
int[] coins = new int[]{500, 100, 50, 10};
int money = 0;
Scanner input = new Scanner(System.in);
System.out.println("거스름돈을 입력해 주세요.");
money = input.nextInt();
System.out.println(Solution(money, coins));
}
}풀이 방법이나 설정했던 요소들은 코드 위에 주석으로 달아놨다.
전체 코드 - GitHub
