4주차 2번(RGB거리)

1.문제 링크

https://www.acmicpc.net/problem/1149

2. 풀이 전 계획과 생각

• 문제에 맞게 동적계획법을 적절히 이용해보기
• 집수(N), 색깔의 개수(M)이라 가정하고 코드를 최대한 일반화하기
• 딕셔너리를 만들어 key값에 색깔 / value값에 해당 총 비용들을 저장하여 최소값을 구해보기

3-1. 유의할 점

조건

맞닿아 있는 집의 색깔은 달라야 한다.

이전에 선택한 색깔은 다음 선택에 영향을 준다.
현재 집의 최소 비용이 다음 집의 최소 비용을 보장하지 못한다.

결론

가능한 경우에 대한 비용을 모두 구한 후에,
그 중 최소값을 구해야 한다.

3-2. 활용할 동적계획법

• 방식 : memoization
• 구현방안 : 딕셔너리에 각 경우의 수에 대한 비용을 저장하기
• 중요사항 : 최대한 일반화하여 코드를 구현해보기

3-3. 경우의 수에 대한 규칙성 찾아보기

• 가능한 경우의 수에 대해 인덱스를 보았을때 규칙성 없음
• 딕셔너리 key값을 이용하여 연속된 key값이 중복일때 비용을 0으로 계산하는 방법으로 memoization후 결과구하기

3-4. 동적계획법을 이용한 풀이

아쉽지만 일반화 실패!

첫번째 집의 색깔이 선택되었을때 모든 경우의 수를 딕셔너리에 저장하고, 이 중 가능한 경우(비용)을 따로 저장하여 최소값을 구하는 것까지 구현!

#각 집에 칠하는 색깔을 배열로 구현하기 위해 일반화 필요
each_house_value = [
 [26, 40, 83], [49, 60, 57], [13, 89, 99]
]

#색깔의개수와 집의수(N)에 따른 일반화 필요
hash_table = {
    1:{1:{},
       2:{},
       3:{}},

    2:{1:{},
       2:{},
       3:{}},

    3:{1:{},
       2:{},
       3:{}}
}

#결과저장
result_array = []



def get_minimum_value(each_house_value, color, N):

    #첫번째집 색깔을 선택한 이후에 나올 수 있는 비용의 경우의 수를 모두 구한 딕셔너리
    #해당 딕셔너리를 만드는 함수
    hash_table = get_hash_table(N, color, each_house_value)

    #위에서 구한 딕셔너리에서 가능한 경우에 대한 비용만 결과배열에 추가하여
    #결과배열중 최솟값을 구하는 함수
    result = get_result_from_hash_table(N, hash_table)

    return result

def get_hash_table(N, color, each_house_value):
    if color == 1:
        for k in range(N):
            if k + 1 < N:
                for i in range(N):
                    for j in range(N):
                        value = 26 + each_house_value[k][i] + each_house_value[k+1][j]
                        hash_table[color][i+1][j+1] = value
            else:
                break

    if color == 2:
        for k in range(N):
            if k + 1 < N:
                for i in range(N):
                    for j in range(N):
                        value = 40 + each_house_value[k][i] + each_house_value[k+1][j]
                        hash_table[color][i+1][j+1] = value
            else:
                break

    if color == 3:
        for k in range(N):
            if k + 1 < N:
                for i in range(N):
                    for j in range(N):
                        value = 83 + each_house_value[k][i] + each_house_value[k+1][j]
                        hash_table[color][i+1][j+1] = value
            else:
                break
    #print(hash_table)
    return hash_table


def get_result_from_hash_table(N, hash_table):
    for k in range(1, 3+1)
        for i in range(N):
            for j in range(N):
                if i + 1 == k or i == j:
                    hash_table[k][i + 1][j + 1] = 0
                    continue
                else:
                    result_array.append(hash_table[k][i + 1][j + 1])
                    continue
    result = min(result_array)
    return result

get_minimum_value(each_house_value, 1, 3)
print(get_minimum_value(each_house_value, 1, 3))

4. 풀이하면서 고민했던 점

• 최대한 일반화하는 코드를 구현해보자

• 현재 코드는 첫번째 집 색깔을 구했을때 이지만,
  이상적인 코드는 모든 경우의 수를 구하는 코드이다!

• 모든 경우의 수를 구할때 필요한 중첩 반복문 / 중첩 딕셔너리 등 어떤 방식으로 구현할지 더 생각해보기

• 알고리즘을 구현하는데 너무 시간이 오래걸린다
  다른 방향으로 생각하는 것도 중요하지만, 시간을 절약하는 것도 매우 중요하다.
  10분내외로 생각하고 알고리즘 구현하는 것까지 가능하도록 꾸준히 연습해보자.

• 클린코드
  하나의 코드에 모든 기능을 담지말고, 기능을 최대한 분산한다.
  ▶조건을 입력받아 결과를 return하는 로직(메인함수)
  ▶모든 경우의 수를 구해주고 딕셔너리를 작성하는 로직
  ▶딕셔너리에서 가능한 경우의 수를 선별하여 비용을 저장하는 로직
  가독성이 좋은 코드, 이해가 쉬운 코드의 조건들을 생각해보자.

5. 문제를 풀고 알게된 개념 및 소감

• loop개념
  for while
  각 반복문을 사용하기 위해 알맞은 문법과 변수선언 방법 등

• 딕셔너리
  딕셔너리 선언하기, 만들기
  중첩딕셔너리 선언하기, 만들기, 접근하기

• 0/None의 개념
  0과 None은 서로 다른 개념!
  0은 있는 값, None은 없는 값으로 반복문에 대한 조건을 다룰 때
  각 분기별로 과정이 다르다!

5-1. remind

코드에 대한 이해가 우선이다. sugar syntax보다는 sugar logic!