프로그래머스 'N으로 표현' 문제풀이 - Henry's Algorithm

 

 

안녕하세요

알고리즘을 좋아하는 개발자 Henry입니다!ㅎㅎ

 

최근에 회사를 다니면서 바쁘고 피곤해서 코딩 문제를 못풀었었는데,

다시 조금씩 풀어보려고 키보드를 잡았습니다!

 

오늘은 프로그래머스에서 동적계획법을 사용해서 푸는 문제를 풀어보았습니다.

N으로 표현이라는 문제를 처음 접했을 때,

아래와 같이 풀었습니다.

 

def solution(N, number):
    answer = 0
    li = []
    dynamic(N,N,number, li, 1)
    return min(li) if len(li) != 0 else -1

def dynamic(N, cur, number, li, cnt):
    if cnt > 8:
        return
    if number == cur:
        li.append(cnt)
        return
    dynamic(N, int(str(cur)+str(N)), number, li, cnt+1) # N->N
    dynamic(N, cur+N, number, li, cnt+1) # N -> +
    dynamic(N, cur-N, number, li, cnt+1) # N -> -
    dynamic(N, cur//N, number, li, cnt+1) # N -> // 소수점은 무시하기 때문에
    dynamic(N, cur*N, number, li, cnt+1) # N -> *

 

 

그러나 위의 코드는 정확도 55점을 받았습니다.

 

알고보니 사칙연산에서 곱셈과 나눗셈을 먼저 계산을 해주는 로직이 빠져 있었습니다.

 

동적계획법을 사용해서 문제를 풀지 않아서 발생하는 이유였습니다.

여기서 잠깐!동적 계획법이란??>> 동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다.

 

찾아보니까 아래의 링크에서 자세하게 설명해주고 있습니다.https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)

 

 

사실 동적계획법에 대해서 정확한 개념을 모르고 있었다.

 

큰 문제를 작게 쪼개어 작은 문제들을 풀어나가는 느낌으로만 이해하고 있었는데,위의 글을 통해서 동일한 작은 문제를 한번씩만 계산하는 원리가 숨어있다는 것을 알게 되었다.

 

그러나 바로 코드에 적용하는 것은 쉽지 않았다.그래서 몇번 고민한 결과 결국 구글링의 도움을 받아 아래 사이트와 동일한 방법으로 문제를 풀게 되었다.

 

https://gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현

def solution(N, number):
    answer = -1
    if number == N:
        return 1
    
    _li = [set() for i in range(8)]
    for i in range(len(_li)):
        _li[i].add(int(str(N)*(i+1)))
        
    for i in range(1,8):
        for j in range(i):
            for op1 in _li[j]:
                for op2 in _li[i-j-1]:
                    _li[i].add(op1+op2)
                    _li[i].add(op1-op2)
                    _li[i].add(op1*op2)
                    if op2 != 0:
                        _li[i].add(op1//op2)
        if number in _li[i]:
            answer = i+1
            break
    
    return answer

 

 

이번 기회를 통해서 동적계획법에 대해서 조금 더 알게 된 것 같아서 감사했다.

앞으로도 꾸준히 코딩 문제를 풀고 싶고, 알고리즘 공부를 하고 싶다.