AIBLOG

문제는 아래와 같습니다.

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

풀이과정

10을 1로 만드는 과정의 최소 횟수를 구하면서 풀이를 해보겠습니다.

우선 다이나믹 프로그래밍의 상향식(Bottom up) 방법으로 구했습니다.

풀이과정의 아이디어를 표현하면 아래와 같습니다.

괄호([])안에 있는 내용은 숫자가 1이 되기까지의 과정을 나열한 것입니다. 

1을 1로 만드는 과정의 최소 횟수: 0

2를 1로 만드는 과정의 최소 횟수: 1 [2를 2로 나눈 몫: 1]

3을 1로 만드는 과정의 최소 횟수: 1 [3을 3으로 나눈 몫: 1]

4를 1로 만드는 과정의 최소 횟수: 2 [4를 2로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

5를 1로 만드는 과정의 최소 횟수: 3 [5를 1로 뺀 값: 4 -> 4를 2로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

6을 1로 만드는 과정의 최소 횟수: 2 [6을 3으로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

7을 1로 만드는 과정의 최소 횟수: 3 [7을 1로 뺀 값: 6 -> 6을 3으로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

8을 1로 만드는 과정의 최소 횟수: 3 [8을 2로 나눈 몫: 4 -> 4를 2로 나눈 몫: 2 -> 2를 2로 나눈 몫: 1]

9를 1로 만드는 과정의 최소 횟수: 2 [9를 3으로 나눈 몫: 3 -> 3을 3으로 나눈 몫: 1]

10을 1로 만드는 과정의 최소 횟수: 3 [10을 1로 뺸 값: 9 -> 9를 3으로 나눈 몫: 3 -> 3을 3으로 나눈 몫: 1]

1을 1로 만드는 최소 과정부터 10을 1로 만드는 최소 과정을 살펴보면, 겹치는 계산이 있는 것을 알 수 있습니다.

예를 들면, 10을 1로 만드는 최소 과정에서 10을 1로 뺀 값인 9를 1로 만드는 과정이 앞에서 9를 1로 만드는 최소 과정과 같은 것을 알 수 있습니다.

또한 8을 1로 만드는 최소 과정에서 8을 2로 나눈 값인 4를 1로 만드는 과정이 앞에서 4를 1로 만드는 최소 과정과 같은 것을 알 수 있습니다.

이렇게 겹치는 계산을 반영해 10의 최소 횟수를 구했습니다. 

코드를 먼저 제시하고, 구현 과정의 일부를 보여드리겠습니다.[설명은 더보기에 있습니다.]

N = 10
dp = [0,0,1,1]

for i in range(4,10+1):
    dp.append(dp[i-1]+1)
    if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])
    if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])
  
print(dp)
>>> [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]

1) i = 4 일때

N = 10
dp = [0,0,1,1]

i=4
dp.append(dp[i-1]+1) #dp=[0,0,1,1,2]
if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])

if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])
  
print(dp)
>>> [0, 0, 1, 1, 2]

2) i = 5 일때

N = 10
dp = [0,0,1,1,2]

i=5
dp.append(dp[i-1]+1) #dp=[0,0,1,1,2,3]
if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i]) 
if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])

print(dp)
>>> [0, 0, 1, 1, 2, 3]

3) i = 6 일때

N = 10
dp = [0,0,1,1,2,3]

i=6
dp.append(dp[i-1]+1) #dp=[0,0,1,1,2,3,4]
if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])

if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])
  
print(dp)
>>> [0, 0, 1, 1, 2, 3, 2]

코드

N = int(input())
dp = [0,0,1,1]

for i in range(4,N+1):
    dp.append(dp[i-1]+1)
    if i%2 == 0:    dp[i] = min(dp[i//2]+1, dp[i])
    if i%3 == 0:    dp[i] = min(dp[i//3]+1, dp[i])
  
print(dp[N])

오늘은 이코딩 강의와 '파이썬 알고리즘 인터뷰' 책을 참고해 다이나믹 프로그래밍을 설명하겠습니다.

https://www.youtube.com/watch?v=5Lu34WIx2Us 

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791189909178 

1. 다이나믹 프로그래밍이란?

다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘입니다.

다이나믹 프로그래밍은 문제가 아래의 조건을 만족할 때 사용할 수 있습니다.

- 최적 부분 구조: 큰 문제를 부분 문제로 나눌 수 있고 문제의 최적 해결 방안은 부분 문제에 대한 최적 해결 방안으로 구성됩니다.

- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 수 있습니다.

2. 피보나치 수열을 이용한 다이나믹 프로그래밍 예시

다이나믹 프로그래밍은 상향식(Bottom up)과 하향식(Top down)으로 구성됩니다.

피보나치 수열을 구하는 코드를 다이나믹 프로그래밍의 상향식, 하향식 방법으로 나타내보겠습니다.

1) 상향식 방법

def fib(n):
    dp=[0]*(n+1)
    dp[1]=1
    
    for i in range(2,n+1):
    	dp[i]=dp[i-1]+dp[i-2]
    return dp[n]

상향식 방법론은 작은 하위 문제부터 차례대로 정답을 풀어나가며 큰 문제의 정답을 만듭니다. 

위의 코드를 참고해, 상향식 방법론으로 5번째 피보나치 수 구하는 방식을 자세히 설명하겠습니다.

1. 처음에 dp[0], dp[1]을 설정합니다. 이것은 곧 0번째 피보나치 수, 1번째 피보나치 수 입니다.
2. dp[2]=dp[1]+dp[0]로 dp[2]를 구합니다. 이것은 곧 2번째 피보나치 수입니다.
3. for문 안에서 2와 같은 연산을 반복하면, dp[3], dp[4], dp[5] 까지 구할 수 있습니다. 이들은 곧 3, 4, 5번째 피보나치 수입니다.
4. 마지막에 dp[5]를 반환하면서 계산을 마칩니다.

피보나치 수열에서의 상향식 방법론은 5번째 피보나치 수를 구하기 위해 0부터 4번째 피보나치 수를 차례대로 계산했습니다.

상향식 방법론은 데이터를 테이블 형태로 만들면서 문제를 풀이한다고 하여 타뷸레이션 방식이라고도 합니다.

2) 하향식 방법

def fib(n):
    dp=[0]*(n+1)
    if n<=1:
    	return n
    if dp[n]:
    	return dp[n]
    dp[n]=fib(n-1)+fib(n-2)
    return dp[n]

하향식 방법론은 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나갑니다. 

위의 코드를 참고해, 하향식 방법론으로 5번째 피보나치 수 구하는 방식을 자세히 설명하겠습니다.

1. 5번째 피보나치 수, fib(5)를 구하기 위해 0으로 구성된 크기 6의 리스트 [0,0,0,0,0,0]를 생성합니다.
2. 이후 dp[5]=fib(4)+fib(3)을 연산해 dp[5]를 반환하면, fib(5)를 구할 수 있습니다.
3. fib(4)를 구하기 위해 dp[4]=fib(3)+fib(2)를 연산하고 dp[4]를 반환합니다.
4. fib(3)을 구하기 위해 dp[3]=fib(2)+fib(1)을 연산하고 dp[3]을 반환합니다.
5. 이를 통해 dp[5]=fib(4)+fib(3)을 연산할 수 있습니다.
6. 3,4 과정을 반복하면 fib(0), fib(1)을 연산해야 하는 순간이 올 것입니다.
   여기서 fib(0), fib(1)은 0, 1번째 피보나치 수로 각각 0과 1 값입니다.
7.  3,4 과정을 반복하면 fib(0)~fib(5)를 구할 수 있습니다. 
    하지만 dp[4]=fib(3)+fib(2), dp[5]=fib(4)+fib(3)과 같이 fib(3)이 두 번 연산되는 경우가 생깁니다.
    이런 불필요한 계산을 방지하고자, fib(3)을 계산할 때, dp[3]이 존재하면 dp[3]을 반환하기로 했습니다.
    이렇게 계산을 한다면, dp[3]=fib(2)+fib(1)을 두 번 하지 않아도 됩니다.
8. 결과적으로 5번째 피보나치 수인 fib(5)가 연산됩니다.

피보나치 수열에서의 하향식 방법론은 5번째 피보나치 수를 구하기 위해 4번째부터 0번째 피보나치 수를 차례대로 계산했습니다.

하향식 방법론은 기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식으로, 메모이제이션 방식이라고도 합니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42626

이번 문제는 Heap을 이용했습니다.

코드를 통해 설명하겠습니다.

CODE

문제는 다음과 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/42586

풀이과정

코드

progresses=[93, 30, 55] 

speeds=[1, 30, 5]

a=[]

b=[]

c=[]

#남은 처리 기간을 계산해서 리스트 a에 추가한다.

while progresses:

  if (100-progresses[0])%speeds[0]==0:

    a.append((100-progresses.pop(0))//speeds.pop(0))

  else:

    a.append(((100-progresses.pop(0))//speeds.pop(0))+1)

#처리 기간별 배포되는 기능의 수를 계산한다.

while a:

  b.append(a.pop(0))

  if len(b)==1:

    c.append(1)

  elif max(b[:-1])<b[-1]:

    c.append(1)

  else:

    c[-1]+=1

c

문제는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/12899

풀이는 다음과 같습니다.

1. 124나라는 우리가 사용하는 10진법 체계에서 3진법으로 바꾼 후 새로운 규칙을 더해 변형된 숫자를 이용한다.

2. 10진법에서 3진법으로 바꾸는 방식은 아래와 같다. 

(10진법 숫자 45를 3진법 숫자 1200으로 바꾸는 과정이다.)

그림에서 45를 3으로 나눈 몫(15)는 아래에, 나머지(0)은 왼쪽에 둔다. 몫을 3으로 다시 나눠서 나온 몫(5)는 아래에, 나머지(0)은 왼쪽에 둔다. 이와 같은 과정을 반복한다.

3. 124나라는 1은 1, 2는 2, 3은 4로 표현한다. 이것을 참고해 1200을 변환한다.

여기서 0은 어떻게 변환되는지 알 수 없다. 이 때 새로운 규칙이 도입된다.

새로운 규칙: 나머지가 0인 경우, 몫에서 1을 빼고, 나머지는 3으로 바꾼다.

새로운 규칙을 적용해 45라는 숫자를 변형하는 과정은 아래와 같다.

4. 마지막으로 1123에서 3을 4로 바꾸면, 최종적으로 1124가 나온다.

제 CODE는 다음과 같습니다.

dic={1:'1',2:'2',3:'4',0:''}

n=45

s=[]

ss=''

while n>=3:

  if n%3==0 and (n//3==3 or n//3==2 or n//3==1):

    n=n//3-1

    s.append(3)

    s.append(n)

  elif n%3==1 and (n//3==2 or n//3==1):

    n=n//3

    s.append(1)

    s.append(n)

  elif n%3==2 and (n//3==2 or n//3==1):

    n=n//3

    s.append(2)

    s.append(n)

  elif n%3==0:

    n=n//3-1

    s.append(3)

  elif n%3==1:

    n=n//3

    s.append(1)

  elif n%3==2:

    n=n//3

    s.append(2)  

while s:

  ss+=dic[s.pop()]

ss

문제는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/17676

풀이

def solution(lines):

    from datetime import datetime
    temp_1=[]
    answer=0
	
    #1초라는 범위 안에서 겹치는 과정이 몇 개인지 찾는 함수이다.
    def func(log, start, end): 
        cnt = 0 
        for x in log: 
            if x[0] < end and x[1] >= start: 
                cnt += 1 
        return cnt

    for e in lines:
        a=datetime.strptime(' '.join(e.split(' ')[0:2]), '%Y-%m-%d %H:%M:%S.%f') 
        #문자열을 날짜 및 시간 형태로 변환(1)
        
        b=datetime.strptime('2016-09-15 00:00:00.000', '%Y-%m-%d %H:%M:%S.%f') 
        #문자열을 날짜 및 시간 형태로 변환(2) - 기준 시간[원점]
        
        c=int((a-b).total_seconds() * 1000) 
        # a시간과 b시간의 차이를 '초'로 구한다. 밀리초로 변환하기 위해 1000을 곱한다.float 형태 -> integer 형태, 이것은 끝나는 시간이다
        
        d=c-int(float(e.split(' ')[2][:-1])*1000)+1 
        #시작 시간을 구하기 위해 c에서 그만큼을 뺀다. 
        
        temp_1.append([d,c]) 
        #[[시작시간1, 끝나는시간1],[시작시간2, 끝나는시간2], [시작시간3, 끝나는 시간3]] 식으로 정리된다.

    for x in temp_1: 
        answer = max(answer, func(temp_1, x[0], x[0] + 1000), func(temp_1, x[1], x[1] + 1000))  
        
    return answer

문제는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/67257

풀이

def solution(expression):

    from functools import reduce
    import re

	#세 개의 연산자가 있을 때 경우의 수
    cal1=[['*','+','-'],['*','-','+'],['+','*','-'],['+','-','*'],['-','+','*'],['-','*','+']]
    s=expression
	
    #세 종류의 연산자가 주어질 때 연산하기
	def func3(A,s):
        for i in re.split('['+str(A[1])+str(A[2])+']',s):
            if A[0] in i:
                s=s.replace(i,str(eval(A[0].join([str(n) for n in i.split(A[0])])))) 
        for i in re.split('['+str(A[2])+']',s):
            if A[1] in i:
                s=s.replace(i,str(eval(A[1].join([str(n) for n in i.split(A[1])]))))
        return abs(eval(A[2].join([str(n) for n in s.split(A[2])])))
	
    #두 종류의 연산자가 주어질 때 연산하기
	def func2(A,s):
        for i in re.split('['+str(A[1])+']',s):
            if A[0] in i:
                s=s.replace(i,str(eval(A[0].join([str(n) for n in i.split(A[0])])))) 
        return abs(eval(A[1].join([str(n) for n in s.split(A[1])])))
    
    #한 종류의 연산자가 주어질 때 연산하기
    def func1(A,s):
        return abs(eval(A.join([str(n) for n in s.split(A)])))
    
    #연산자가 몇 종류 있는지 알아보기
    cal0=[]
    if '-' in s:
        cal0.append('-')
    if '+' in s:
        cal0.append('+')
    if '*' in s:
        cal0.append('*')
    
    #계산된 값들 중 최대값 반환하기
    b=[]
    if len(cal0)==3:
        for a in cal1:
            b.append(func3(a,s))
        return max(b)
    if len(cal0)==2:
        for a in [cal0[::-1],cal0]:
            b.append(func2(a,s))
        return max(b)
    if len(cal0)==1:
        return func1(cal0[0],s)

문제는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/62048

풀이

#규칙성 찾기가 가장 중요함
def solution(w,h):
    def GCD(A,B): return B if (A==0) else GCD(B%A,A)   #최대공약수구하기
    def func(A,B):return func(A//GCD(A,B),B//GCD(A,B))*GCD(A,B) if GCD(A,B)!=1 else A+B-1
    #재귀함수이용하기
    return w*h-func(w,h)

문제는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/60057

풀이

def solution(s):
    a=1
    k=[]
    b=''
    if len(s)==1:
        return 1
    for j in range(1,len(s)//2+1):
        b=''
        for i in range(0,len(s)-j+1,j) if len(s)%2==j else range(0,len(s),j):
            if s[i:i+j]==s[i+j:i+j+j]:
                a+=1
            else:
                if a>1:
                    b+=str(a)+s[i:i+j]
                    a=1
                else:
                    b+=s[i:i+j]
        k.append(len(b))
    return min(k)

문제는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/81301

풀이

def solution(s):
    kk={}
    kk_sorted=[]
    string=['zero','one','two','three','four','five','six','seven','eight','nine']
    import re
    for aa in range(len(string)):
        for i in [m.start() for m in re.finditer(string[aa], s)]:
            kk[i]=aa
        for j in [m.start() for m in re.finditer(str(aa), s)]:
            kk[j]=aa
    for i in sorted(kk.items()):
        kk_sorted.append(str(i[1]))
    return int(''.join(kk_sorted))

1단계. string에 해당하는 문자열의 위치를 찾고 딕셔너리 형태로 변환합니다.

Ex) {3: 'one'} : 세번째 위치에 one이 있다.

2단계. number에 해당하는 문자열의 위치를 찾고 딕셔너리 형태로 변환합니다.

Ex) {4: 1} : 네번째 위치에 1이 있다.

3단계. 위치 기준으로 딕셔너리를 정렬합니다.

4단계. 정렬한 딕셔너리의 값을 합쳐서 숫자로 반환합니다.