[TIL] Java Algorithm 2

😈 지옥의 알고리즘 섹션이 지나가고 있다.

목요일까지만 잘 마무리하면,,, 이제 웹서비스에 대한 기반 지식을 배우기 시작 할 것 같다.
알고리즘은 아무래도 장기적으로 보고 공부해야하는
컨텐츠라고 생각도들고…. 지금까지 문제를 풀면서
이해안되는 것도 억지로 이해해보려고 노력도 해봤다.

80%정도는 풀고 20% 정도는 레퍼런스 코드를 빌렸는데
얻어가는 것도 많았고, 문법의 쓰임도 조금 분명하게 쓰는 것들도 늘어났다.

---

오늘은 어제 배운 이론을
알고리즘으로 푸는 시간을 가졌다.
오늘은 내가 푼 코드를 분석하고 정리해보려한다.
자세한 문제 내용은 코드스테이츠 측의 자료이기 때문에
내가 풀었던 방식과 대략적인 맥락만 정리해본다.

Greedy 관련 문제.

탐욕 알고리즘. 이름 부터 탐욕스럽기 그지없다.
문제를 풀때 최선의 방법을 찾을 때 사용하는 알고리즘으로 배웠고
잔돈 거스름돈에 대한 문제를 적용하는 문제였다.

내가 생각했을때 롤 상점과 비슷한 것 같다.
라인전 이후 복귀한다음에
내가 가지고 있는 골드를 전부 알뜰하게 사용해야
좀 더 강한 상태로 라인전을 지속할 수 있다.
최선의 방법을 찾아 그거에 맞아 아이템을 사는 것.
이번 문제도 거스름돈도 같은 개념이다.

4260원을 받았고, 거스름돈이 500원,100원,50원,10원 이라고 가정했을떄

500원 * 8

100원 * 2

50원 * 1

10원 * 1

총 12개의 동전을 거슬러줘야 최선의 선택일 것이다.
500원짜리가 부족해 동전을 마구준다면 분명 화날 것이 분명.

public int changeMoney(int k) {
    // 1원, 5원, 10원, 50원, 100원, 500원 동전 수량만큼 반환하기
    // 큰수부터 나누어 떨어지는 몫을 구해 동전 수량에 넣기
    // 나머지값으로 다음 수의 몫을 구하
    int currentCoin = 0;
    int remainCoin = k;
    int[] coin = {500,100,50,10};
    for(int i=0; i<coin.length; i++){
        if(remainCoin>=coin[i]){
            currentCoin += remainCoin/coin[i];
            remainCoin = remainCoin%coin[i];
        }
    }
    return currentCoin;
}

coin이라는 거슬러줄 수 있는 동전의 종류와
총 거슬러줘야하는 금액을 k라는 매개변수로 전달해주게된다.
동전의 종류만큼 반복문을 실행 시키고
동전종류에따른 남은 금액을 나눠 몫을 동전 개수로 넘겨주게된다.

그리고 다시 남은 금액은 다음 동전종류와 나눠지게 되며
이렇게 쭉 진행 후 결과 반환값은 위에서 예측 했던 것과 같이 12라는 값을 얻을 수 있다.

simulate 구현 문제

배열이라는 보드게임 판위에서
말을 이동시켜 점수를 얼마나 획득했는지 추출해내는 문제였다.
이 문제는 시뮬레이터 구현에 관련된 문제인 것 같았다.
해당 지시사항대로 이행해 내가 얻은 점수를 판별하는?
문제이기 때문에 주어진 문제의 케이스만 잘 처리하면 되는 문제였다.

public Integer game(int[][] board, String operation) {
    // TODO:
    int ud = 0;
    int rl = 0;
    int count = 0;
    if(board[ud][rl]==1) count = 1;
    for(int i=0; i<operation.length(); i++){
      try{   
        int test = 0;
        if(operation.charAt(i)=='U') ud -= 1;
        if(operation.charAt(i)=='D') ud += 1;
        if(operation.charAt(i)=='R') rl += 1;
        if(operation.charAt(i)=='L') rl -= 1;
        test = board[ud][rl];
      }catch (ArrayIndexOutOfBoundsException e){ // 범위값이 벗어나면 return null 해주는 구문
        return null;
      }
      if(board[ud][rl]>0) count+=board[ud][rl];
    }
    return count;
}

해당 문제에서는 주어진 배열의 점수가 매겨져있다.
그리고 이동명령을 내리는 문자열이 주어지며
0,0위치에서 시작하고 U,R,L,D라는 이동 명령을 통해 배열판을 이동하며
이동시 해당판에 점수가 있으면 그 점수를 획득하여

최종적으로 이동명령을 완료 했을때의 점수를 합산해주는 문제다.
여기서 문제는 게임판을 벗어났을 경우 null로 리턴해주는
예외처리를 해야한다.

DP 문제

동적 계획법에 관한 문제다.
복잡한 문제를 여러개의 작은문제로 나눠 해결하는 풀이법이다.
가장 대표적인 예로는 피보나치 수열을 예로든다.
아래의 글을 참고하여 공부를 했었고 예제로 적절하다고 생각한다.

동적 계획법(Dynamic Programming) Reference

이번 문제와 같은 경우는 동적 계획법을 적용해야하는 문제였고
잔돈을 거슬러주는데 가지고 있는 동전의 종류에서
해당 잔돈을 거슬러줄 수 있는 경우의 수가 몇가지가 되는가?
이 부분이 핵심 문제 였고, 나는 아래와 같이 표현했다.

public long dp(int money, int[] type) {
    // 목표금액의 경우의수를 담기위한 배열
    long[] numberOfCase = new long[money+1];
    // 첫번째 인덱스는 자기자신의 숫자의 경우에 수로 1로 고정
    numberOfCase[0] = 1;

    // 동전 타입을 순회할 포문
    for(int coin=0; coin<type.length ; coin++){
      for(int noc=1; noc<numberOfCase.length; noc++){
        // 동전 타입이 해당 경우의수 보다 크거나 같을 경우에만 경우의수를 체크
        // 즉 10원의 타입 동전이 들어왔을 경우 10원 이상의 경우에만 조건문실행가능
        if(type[coin]<=noc){
          // 해당 동전타입으로 만들수 있는 케이스를 각 케이스별로 저장 10원으로는 20원,30원,40원.... 
          // 쭉쭉 만들 수 있기 때문에 해당하는 원에 1씩 증가시키기
          numberOfCase[noc] = numberOfCase[noc]+numberOfCase[noc-type[coin]];
        }
      }
    }
	return numberOfCase[money];
}

예제로

50원을 거슬러줘야하고
10원,20원,50원 이라는 잔돈을 가지고 있다고 가정하면
얼만큼의 경우의 수로 동전을 지불해야하는가?

50  - 경우의 수 1

20   20   10  - 경우의 수 2

20  10  10  10  - 경우의 수 3

10   10   10  10  10 - 경우의 수 4

위와 같이 3개의 잔돈으로 4가지의 지불 경우의 수가 나오게된다.

1. 50원으로 지불
2. 20원 2개 + 10원 1개
3. 20원 1개 + 10원 3개
4. 10원 5개

여기서 우리가 알 수 있는 것은 동전 종류별로 문제를 나누어 풀 수 있다는 점이다.
결과적으로 위의 코드를 실행 시키면
하위 문제(동전 종류별로 경우의 수 체크)들을 나누어 풀고
그것을 결합해서 최종적으로 잔돈에대한
동전 지불 경우의 수가 나오게되는 것이다.

---

사실 아직 동적계획법에 대해 심도깊은 이해는
어려운 상태이다. 어느정도 맥락과 사용법은 알겠지만
다른 응용된 문제가 나왔을 때, 내가 이문제를
동적계획법을 적용해 풀 수 있을지는 아직 미지수이다..
오늘의 공분는 여기까지!

오늘의 커피량: ☕️ ☕️ ☕️
오늘의 점심: 라면