[프로그래머스 코딩 테스트] 코딩 테스트 공부 - KAKAO TECH INTERNSHIP

코딩 테스트 공부

문제 설명

알고력과 코딩력의 초기값을 가지고 입력으로 들어오는 문제들의 힘을 빌려 그 초기값을 높이고, 최종에는 입력으로 들어온 모든 문제를 풀 수 있는 알고력과 코딩력 값을 가지게 만들면 된다. 이때, 문제를 푼 최소 횟수를 리턴해 주는 코드를 짜야 한다.

 

---

 

문제 풀이

이번 문제는 생각할 거리가 많아서 코딩을 짜는 데에도 쉽게 손이 가지 않았다.

1. 요구되는 알고력과 코딩력이 가장 낮은 문제를 풀 수 있는 능력치까지 올리는 데에 걸리는 시간(능력 +1 당 시간 +1)
2. 그 다음 문제를 풀기 위해 요구되는 알고력과 코딩력을 갖추기 위한 방법 -> +1 당 시간 +1 or 이전 문제 풀이

위 두 가지 방법을 고려하여 코드를 짜야 하는데, 딕셔너리로 바꾸어 써야 하는지, 리스트를 그대로 써야 하는지 계속 고민이 됐었다.

내가 작성한 코드 

def point_loof(alp, cop, target):
    cost = 0
    while alp != target[0] or cop != target[1]:
        if alp < target[0]:
            alp += 1
            cost += 1
        elif cop < target[1]:
            cop += 1
            cost += 1
    return alp, cop, cost

def solution(alp, cop, problems):
    answer = 0
    nz = [0, 0]
    problems = sorted(problems)
    alp, cop, answer = point_loof(alp, cop, problems[0])
    while alp < problems[-1][0] and cop < problems[-1][1]:
        for i in range(len(problems)-1):
            nz[0], nz[1] = problems[i+1][0] - alp, problems[i+1][1] - cop
            nz = [0 if x < 0 else x for x in nz]
            if problems[i+1][0] > 0 or problems[i+1][1] > 0:
                if problems[i][2] == 0 and problems[i][3] != 0:
                    if problems[i][4]//problems[i][3] < 1:
                        while cop < problems[i+1][1]:
                            cop += problems[i][3]
                            answer += problems[i][4]
                            print(alp, cop)
                    else:
                        while cop < problems[i+1][1]:
                            cop += 1
                            answer += 1
                            print(alp, cop)
                            
                elif problems[i][3] == 0 and problems[i][2] != 0:
                    if problems[i][4]//problems[i][2] < 1:
                        while alp < problems[i+1][0]:
                            alp += problems[i][2]
                            answer += problems[i][4]
                            print(alp, cop)
                    else:
                        while alp < problems[i+1][0]:
                            alp += 1
                            answer += 1
                            print(alp, cop)
                elif problems[i][3] != 0 and problems[i][2] != 0:
                    if problems[i][4]//(problems[i][2]+problems[i][3]) < 1:
                        while alp < problems[i+1][0] and cop < problems[i+1][1]:
                            alp += problems[i][2]
                            cop += problems[i][3]
                            answer += problems[i][4]
                            print(alp, cop)
                    else:
                        while alp < problems[i+1][0]:
                            alp += 1
                            answer += 1
                            print(alp, cop)
                        while cop < problems[i+1][1]:
                            cop += 1
                            answer += 1
                            print(alp, cop)
                else:
                    while alp < problems[i+1][0]:
                            alp += 1
                            answer += 1
                            print(alp, cop)
                    while cop < problems[i+1][1]:
                        cop += 1
                        answer += 1
                        print(alp, cop)
    return answer

얼핏 보기만 해도 복잡한 것 같은 첫 코드.... 주요 조건으로 택한 건 위에 쓴 것과 동일하다. 오름차순으로 정렬 후 가장 첫 문제를 풀 수 있는 알고력/코딩력을 만들어 준다. 그리고 그 다음 문제부터는 알고력/코딩력을 하나씩 올리는 것과 문제를 풀며 올리는 것 중 시간 낭비가 덜한 것을 골라 학습시킨다.

위 코드를 진행하면 테스트 케이스 1 번 문제만 정답  처리가 되고 2 번 문제는 오답이 나온다. 아무래도 일단은 코드 틀만 짜 보자는 생각으로 주절주절 적은 것이니까 헛점이 많을 것이라 보고... 허점을 보완해 보려고 한다.

 

남이 작성한 코드

def solution(alp, cop, problems):
    answer = 0
    inf = [999999]
    max_alp, max_cop = [0, 0]
    for i in problems:
        max_alp = max(max_alp, i[0])
        max_cop = max(max_cop, i[1])
    dp = [inf * 151 for _ in range(151)]
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    dp[alp][cop] = 0
    for i in range(alp, max_alp + 1):
        for k in range(cop, max_cop + 1):
            if i < max_alp:
                dp[i + 1][k] = min(dp[i + 1][k], dp[i][k] + 1)
            if k < max_cop:
                dp[i][k + 1] = min(dp[i][k + 1], dp[i][k] + 1)
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if i >= alp_req and k >= cop_req:
                    new_alp = min(i + alp_rwd, max_alp)
                    new_cop = min(k + cop_rwd, max_cop)
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][k] + cost)
    return dp[new_alp][new_cop]

위의 이미 복잡해진 코드를 도저히 수정할 자신이 없어서 힌트를 확인해 봤더니 'DP' 즉, 동적 프로그래밍(동적 계획법)을 활용하면 쉽게 풀 수 있는 문제였다고 한다. 동적 프로그래밍의 여지는 위의 코드를 짜면서 충분히 느낄 수 있었을 텐데, 코딩 테스트를 너무 오래 쉬어서 그런지 전혀 감도 잡지 못했었다.

1. 반복되는 작업이 많은가.
2. 최적의 경우의 수를 구하는 문제인가.

이 두 가지 경우에 모두 부합하는 문제라면 동적 프로그래밍을 고려해 보는 것이 좋다.

동적 프로그래밍에서는 점화식을 찾아내는 것이 중요한데, 오랜만에 접하는 알고리즘들이어서 그런지 머리가 안 굴러 가서 힌트를 통해 점화식을 확인했다.

• 알고리즘을 공부하여 알고력을 1 높이는 경우:
  dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
• 코딩을 공부하여 코딩력을 1 높이는 경우:
  dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)
• 문제 하나를 선택하여 알고력과 코딩력을 높이는 경우:
  dp[i+alp_rwd][j+cop_rwd] = min(dp[i+alp_rwd][j+cop_rwd], dp[i][j]+cost) (단, i >= alp_req이고 j >= cop_req)

위 힌트는 카카오에서 직접 올린 풀이에 나와 있는 점화식이다.

쉽게 말해 dp라는 2차원 배열(알고력과 코딩력의 최대값은 문제에서 주어지니 그거에 맞는 크기로 배열 생성해 놓기)에 알고력 행, 코딩력 열마다 해당 능력치에 다다를 때까지 최소한의 시간이 얼마나 걸렸는지를 고려하는 식이다. 일단 위 식에서 2중 for문을 통해 능력치 1을 올릴 때마다 시간 1을 추가해 주는, 기본적으로 걸리는 시간을 dp 배열에 넣어 준다.

그리고 문제에서 요구하는 능력치의 배열값에 다다르면 if문 안으로 들어가서 문제를 풀었을 때의 걸리는 시간과 단순히 +1을 하며 +1의 시간을 추가한 것 중 최소 시간을 골라 리스트에 넣어 주는 수순을 밟는다.

마지막 return에서는 주어진 문제 중 요구되는 가장 높은 능력치의 배열값에 들어 있는 것을 꺼내 주면 된다.

 

---

 

이 문제를 통해 배울 수 있었던 점

잊고 있었던 동적 프로그래밍에 대해 다시 상기할 수 있는 시간이었던 것 같다. 코딩 테스트를 코앞에 두고 이제야 코테의 기본 중 기본이라고 할 수 있는 DP를 새롭게 공부하다니.... 아마 이번 코딩 테스트는 글렀다고 보면 되겠지. 그래도 할 수 있는 데까지 열심히 해 보자는 의미에서 포기하지 않고 업로드까지 진행해 본다.그리고 코딩 테스트가 끝나면 다시 공부를 시작해야겠다. 동적 프로그래밍의 예제들도 찾아보고, 가능하다면 책도 구비해 공부해 보는 것이 좋을 것 같다.