[DP] 백준 풀이 기록 JAVA (Feat. do it 알고리즘 코딩테스트)

tmi)

최근 do it 알고리즘 코딩테스트 자바 편을 보며 코테 공부를 하고 있다. 

작년 8월까지 동아리 활동을 하고, 9~12월 인턴활동을 한 다음 인턴 퇴사 후 한달정도 쉬다가 토익보고 오픽보고 자소서 쓰고 취준활동을 했다. 인성검사, 코테...도 보고 면접까지 가 본 회사도 있지만 아직 취준 중인 백수..이다 ㅎㅎ

---

 

혼자서 공부하면 잘 못하는데 그래도 이 책은 열심히!! 마지막 12장을 남겨두고 거의 다 끝나간다! 그 와중에 동적계획법이 너무 어려워서 ........ 간만에 블로그도 쓸 겸, 공부한 내용 정리도 할 겸 자주 보려고 쓰는 글.. .(아무레도 인텔리제이 키는거보다 블로그 글 보는게 더 손이 자주가니까!)

솔직히 거의 책보면서 코드를 이해하는 수준이다 내 지식으로 만들려면 일단 이해먼저 해야겠지..

 

| chap 11 동적계획법 | 1163 |
| chap 11 동적계획법 | 14501 |
| chap 11 동적계획법 | 2193 |
| chap 11 동적계획법 | 11726 |
| chap 11 동적계획법 | 10844 |
| chap 11 동적계획법 | 13398 |
| chap 11 동적계획법 | 9252 |
| chap 11 동적계획법 | 1915 |
| chap 11 동적계획법 | 1328 |
| chap 11 동적계획법 | 2342 |
| chap 11 동적계획법 | 11049 |
| chap 11 동적계획법 | 2098 |
| chap 11 동적계획법 | 14003 |

동적계획법 

- 큰 문제를 반복되는 작은 문제로 나눌 수 있으며, 작은 문제들의 결과값은 항상 같다. 

- 작은 문제들은 한번씩만 계산하여 그 값을 저장해두고, 추후 재사용(메모제이션 기법)

- 재귀함수 방식으로 구현해나가는 top-down / 반복문 돌리는 bottom-up 

 

# 1163 

점화식 DP[i] = i 에서 1로 만드는데 걸리는 최소 연산 횟수 

- 1을 뺀다 -> DP[i] = DP[i-1] + 1 (연산 1번 수행했으므로 더하기 1) 

- 2로 나눈다 -> DP[i] = DP[i/2] + 1

- 3로 나눈다 -> DP[i] = DP[i/3] + 1

이 3가지 옵션들을 비교하며 최소 연산을 계산

DP[1] = 0;
for (int i = 2; i <= n; i++) {
	DP[i] = DP[i-1] + 1;
    if (i % 3 == 0) {
    	DP[i] = Math.min(DP[i], DP[i/3] + 1);
    }
   	if (i % 2 == 0) {
    	DP[i] = Math.min(DP[i], DP[i/2] + 1);
    }
}

 

# 14501 

점화식 

- DP[i] : i번째 날 부터 퇴사날까지 얻을 수 있는 최대 수익

 

해당 일에 잡히는 상담이 퇴사 전에 끝나는 경우 진행할건지 말건지를 결정해야 한다. 

1 ) 해당 날에 상담을 진행한 경우 -> 이 상담이 끝날 때까지는(time[i]동안) 다른 수익이 없다. DP[i + time[i]] + price[i] 

2 ) 상담 진행하지 않은 경우 -> DP[i+1]과 동일할 것! 

DP[i] = Math.max(DP[i+1], DP[i + time[i]] + price[i]);

for (int i = n; i > 0; i--) {
	if (time[i] + i <= n+1) {	
    // 제시간안에 상담이 끝나는 경우
    	DP[i] = Math.max(DP[i+1], DP[time[i] + i] + price[i]);
    } 
    else {
    	DP[i] = DP[i+1];
    }
}

 

 

---

# 2098 외판원 순회

- 리스트 형태의 데이터를 1개의 자료형에 저장하는 방법 : bit 사용하면 된다

- 이진수로 도시의 방문 여부를 저장 (ex 1010 : 2, 4 도시 방문한거, 총 도시 4개 이런식으로 ) 

- 2번 도시를 추가로 방문한다 : 1 << 2하고 & 연산자 

 

이 문제에서는 cycle여부를 파악하는걸 간과하면 안된다. 이거때문에 계속 시간초과 났었다.

처음에는 사이클이 끊겨서 출발지로 도달할 수 없는 경우와 아직 방문하지 않은 경우 둘다 Integer.MAX_VALUE값으로 해놨었다.

근데 그러면 notCycle(돌아올 수 없는 경우)도 아직 방문하지 않은 곳으로 간주되어 계속 탐색해서 시간초과가 나는 것 같다. 

 

따라서 진짜 아직 방문 안한 도시인건지, 가봤지만 못 돌아가는 건지 구분해야할 것 같다. 

📝 notCycle이 더 작은값이어야 Math.min()함수를 통해 갱신이 된다. 

public static int notCycle = 1000000 * 16 + 1;
public static int notVisited = notCycle * 2;

 

// 메인함수에서 DP배열 notVisited로 초기화하고 TSP 수행
for (int i = 0; i < n; i++) {
	for (int j = 0; j < 1<<n; j++) {
    	DP[i][j] = notVisited;
    }
}
System.out.println(TSP(0, 1));


static int TSP (int c, int v) {
        // 모든 도시를 방문한 경우
        if (v == (1 << n) - 1) {
            if (cityInfo[c][0] != 0) {
                return cityInfo[c][0];
            }
            else {
                return notCycle;
            }
        }
        // 이미 최소 비용이 계산이 되어 있다면(notVisited가 아니라면)
        if (DP[c][v] != notVisited) {
            return DP[c][v];
        }
        for (int i = 0; i < n; i++) {
            // 갈 수 있고, 아직 방문을 안 했을 경우
            if (cityInfo[c][i] != 0 && (v & (1 << i)) == 0) {
                DP[c][v] = Math.min(DP[c][v], TSP(i, (v | (1 << i))) + cityInfo[c][i]);
            }
        }
        return DP[c][v];
    }