AIBLOG

카운팅 정렬은 계산 복잡성이 O(n)인 알고리즘입니다.

이 게시글은 아래의 블로그를 참고했습니다. 감사합니다.

https://elrion018.tistory.com/37

카운팅 정렬 코드는 다음과 같습니다.

def counting_sort(array,max):

    counting_array = [0]*(max+1)
 
    for i in array:
        counting_array[i] += 1
 
    for i in range(max):
        counting_array[i+1] += counting_array[i]
 
    output_array = [-1]*len(array)
 
    for i in array:
        output_array[counting_array[i] -1] = i
        counting_array[i] -= 1
    
    return output_array

풀이과정

10개의 array [5,5,2,2,4,3,3,1,1,7]가 존재합니다. 이것을 정렬하기 위해 counting_array 와 output_array가 필요합니다.

1. 우선 counting_array는 array의 누적 빈도수를 의미합니다. 이것을 구해봅시다.

1) 처음에는 빈도수를 구하기 위해 0이 8개(array 의 최대값+1)인 리스트를 생성합니다.

    counting_array=[0,0,0,0,0,0,0,0]

2) 빈도수를 구합니다.

    counting_array = [0,2,2,2,1,2,0,1] (array의 빈도수) -> 0이 0개있고,1이 2개있고,..., 6이 0개 있고, 7이 1개 있는 것입니다.

3) 누적 빈도수를 구합니다.

      counting_array = [0,2,4,6,7,9,9,10] (array의 누적 빈도수)

2. output_array를 구합니다. 여기에서 처음 주어진 array가 정렬된 결과값이 나옵니다.

1) 우선 -1을 array 개수만큼 리스트로 설정합니다.

    output_array=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1] (output_array의 초기설정)

2) counting_array와 엮어서 output_array를 구해보겠습니다.(CODE를 이용해 설명하겠습니다)

CODE

  for i in array:
        output_array[counting_array[i] -1] = i
        counting_array[i] -= 1

- array의 첫번째 원소가 5일 때, counting_array[5]는 5일때의 누적빈도수를 의미합니다.

  누적빈도수가 9이기 때문에 output_array[8]은 5입니다.

  counting_array[5]는 9에서 8로 줄어듭니다.

output_array=[-1,-1,-1,-1,-1,-1,-1,-1, 5,-1]

- array의 두번째 원소가 5일 때, counting_array[5]는 5일때의 누적빈도수를 의미합니다.

  누적빈도수가 8이기 때문에 output_array[7]은 5입니다.

  counting_array[5]는 8에서 7로 줄어듭니다.

output_array=[-1,-1,-1,-1, -1,-1,-1, 5, 5,-1]

- array의 세번째 원소가 2일 때, counting_array[2]은 2일때의 누적빈도수를 의미합니다.

  누적빈도수가 4이기 때문에 output_array[3]은 2입니다.

  counting_array[2]는 4에서 3으로 줄어듭니다.

output_array=[-1,-1,-1, 2, -1,-1, -1, 5, 5,-1]

- array의 네번째 원소가 2일 때, counting_array[2]은 2일때의 누적빈도수를 의미합니다.

  누적빈도수가 3이기 때문에 output_array[2]는 2입니다.

  counting_array[2]는 3에서 2로 줄어듭니다.

output_array=[-1,-1, 2, 2, -1,-1, -1, 5, 5,-1]

- array의 다섯번째 원소가 4일 때, counting_array[4]은 4일때의 누적빈도수를 의미합니다.

  누적빈도수가 7이기 때문에 output_array[6]는 4입니다.

  counting_array[4]는 7에서 6으로 줄어듭니다.

output_array=[-1,-1, 2, 2, -1, -1, 4, 5, 5,-1]

이와 같이 계산하면 output_array는 [1,1,2,2,3,3,3,4,5,5,7]로 정렬됩니다.

#이 문제는 풀지 못했다.. 심지어 이해하기도 힘들었다. 나같은 사람을 위해 코드를 해체해봤다.

문제

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

정답 코드

def hanoi(n, a, b):
    if n > 1:									[과정A]
        hanoi(n-1, a, 6-a-b)              
                                          
    print(a, b)									[과정C]

    if n > 1: 									[과정B]
        hanoi(n-1, 6-a-b, b)

n = int(input())

print(2**n -1)                            
hanoi(n, 1, 3)

풀이

n=3 일 때,

CODE의 맨 마지막 줄에 있는 hanoi(n,1,3)은 3개의 원반이 있을 때, 기둥1에서 기둥3으로 이동하는 것을 의미한다.

먼저 hanoi(3,1,3)으로 시작한다.

CODE의 [과정A]에 따르면 hanoi(2,1,2)가 되고, [과정C]에 따르면 print(1,3)가 된다. [과정B]에 따르면 hanoi(2,2,3)이 된다.

1. hanoi(2,1,2): 2개의 원반을 기둥1에서 기둥2로 옮긴다.

>>hanoi(2,1,2)는 [과정A]에 따르면 hanoi(1,1,3)이 되고, [과정C]에 따르면 print(1,2)이 된다. [과정B]에 따르면 hanoi(1,3,2)가 된다.

1) hanoi(1,1,3): 1개의 원반을 기둥1에서 기둥3으로 옮긴다. 1번째 출력: print(1,3) 

2) print(1,2): 1개의 원반을 기둥1에서 기둥2로 옮긴다. 2번째 출력: print(1,2) 

3) hanoi(1,3,2): 1개의 원반을 기둥3에서 기둥2로 옮긴다. 3번째 출력: print(3,2) 

최종적으로 hanoi(2,1,2) 결과, 2개의 원반이 기둥1에서 기둥2로 옮겨졌다.

2. print(1,3): 나머지 1개의 원반을 기둥1에서 기둥3으로 옮긴다. 4번째 출력: print(1,3)

3. hanoi(2,2,3): 2개의 원반을 기둥2에서 기둥3으로 옮긴다.

>>hanoi(2,2,3)는 [과정A]에 따르면 hanoi(1,2,1)이 되고, [과정C]에 따르면 print(2,3)이 된다. [과정B]에 따르면 hanoi(1,1,3)이 된다.

1) hanoi(1,2,1): 1개의 원반을 기둥2에서 기둥1로 옮긴다. 5번째 출력: print(2,1) 

2) print(2,3): 1개의 원반을 기둥2에서 기둥3로 옮긴다. 6번째 출력: print(2,3) 

3) hanoi(1,1,3): 1개의 원반을 기둥1에서 기둥3로 옮긴다. 7번째 출력: print(1,3) 

오늘은 예제는 맞췄는데 시간, 메모리 초과가 뜬 문제를 가져왔습니다. 

정답이 뭔지 몰라서 더욱 답답한.. 하지만 DP를 이용한 방식, Two Pointer를 이용한 방식 모두 예제는 맞춰서.. 

나중에 좀 더 코딩을 잘하는(?) 제가 참고하도록 기록해놓겠습니다.

문제

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

코드 및 풀이

우선 'bacab'과 같이 팰린드롬인 문자열의 조건은, 

1) 시작점의 문자열과 끝점의 문자열이 같고, ('bacab'의 경우 양끝이 'b'로 같습니다)

2) 시작점, 끝점을 제외한 문자열 역시 팰린드롬입니다. ('bacab'의 경우 양끝을 제외한 'aca'역시 팰린드롬입니다) 

아래는 문제에 대한 풀이입니다.

1. Two Pointer를 이용한 방식

s='abacaba'
result={}
answer=[]
for i in range(len(s)):
  for j in range(0,2):
    left,right=i,i+j
    while left>=0 and right<len(s) and s[left]==s[right]: 
        left-=1 
        right+=1
        if s[left+1:right] not in result.keys():
            result[s[left+1:right]]=1
        else:
            result[s[left+1:right]]+=1
for i in result:
    answer.append(len(i)*result[i])
print(max(answer))

1) 팰린드롬을 Two Pointer로 구하는 원리는 아래를 참고하시면 될 것 같습니다.

https://byumm315.tistory.com/entry/%EB%A6%AC%ED%8A%B8%EC%BD%94%EB%93%9C-5-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EB%B6%80%EB%B6%84-%EB%AC%B8%EC%9E%90%EC%97%B4

2) 팰린드롬을 구하며 result 딕셔너리에 키(key)를 저장했습니다. 이때, 딕셔너리에 값(value)이 존재하면 1을 더했고 존재하지 않으면 키(key)를 만들고 값을 1로 지정했습니다. result 는 아래와 같습니다.

{'a': 4, 'aba': 2, 'abacaba': 1, 'aca': 1, 'b': 2, 'bacab': 1, 'c': 1}

3) for문을 이용해 result에서 키(key)의 길이와 해당하는 값(value)을 곱해 answer 리스트에 저장했습니다.

이후 가장 큰 값을 출력했습니다. answer 리스트는 아래와 같습니다.

[4, 2, 6, 1, 3, 5, 7]

4) 정답은 7입니다.

2. DP(다이나믹 프로그래밍)를 이용한 방식

s='abacaba'
n=len(s)
dp = [[0] * n for _ in range(n)]
answer=[]
answer_1=[]

for num_len in range(n):
    for start in range(n - num_len):
        end = start + num_len
        # 시작점과 끝점이 같다면 글자수가 1개이므로 무조건 팰린드롬
        if start == end:
            dp[start][end] =1
            answer.append(s[start:end+1])
        # 시작점의 글자와 끝점의 글자가 같다면
        elif s[start] == s[end]:
        	# 두 글자짜리 문자열이라면 무조건 팰린드롬
            if start + 1 == end: 
                dp[start][end] = 1
                answer.append(s[start:end+1])
            # 가운데 문자열이 팰린드롬이라면 팰린드롬
            elif dp[start+1][end-1] == 1: 
                dp[start][end] = 1
                answer.append(s[start:end+1])
                
from collections import Counter
for i in Counter(answer):
    answer_1.append(len(i)*Counter(answer)[i])
print(max(answer_1))

1) 문자열 길이의 행과 열을 가진 DP Table dp를 만듭니다. 

2) 이중for문을 통해 시작점과 끝점사이 길이가 0일때부터 n일때까지 범위를 지정합니다. 

따라서 길이가 0인 부분문자열부터 n인 부분문자열까지 확장하는 방식으로 팰린드롬을 찾습니다.

이것은 크기가 작은 부분문자열부터 팰린드롬 유무를 확인하고 문자열의 크기를 조금씩 크게 만들면서 팰린드롬 유무를 확인한다는 점에서 DP의 Bottom - Up 방식과 유사합니다.

DP에서 문제가 팰린드롬 유무를 찾기라면 작은 문제를 풀면서 큰 문제의 해답을 찾는다는 점에서 유사합니다.

2-1) 예를 들면, 길이가 7인 'abacaba'가 팰린드롬인지 알려면, 양 끝점을 봅니다.

양 끝점이 'a'로 같기 때문에, 팰린드롬일 가능성이 있습니다.

이제, 양 끝점을 제외한 나머지 문자열'bacab'가 팰린드롬인지 알아야 됩니다.

그런데, 우리는 이미 앞에서 길이가 5인 부분 문자열에 있는 팰린드롬들을 구했습니다.

따라서 'bacab'가 팰린드롬임을 알 수 있습니다. 

가운데에 있는 'bacab'가 팰린드롬이기 때문에, 'abacaba' 역시 팰린드롬입니다.

3) 문자열 안에 있는 부분문자열이 팰린드롬인 경우, dp[시작점][끝점]에 1을 부여합니다.

아래의 그림의 0번째 줄을 예로 들면, 0번째 원소와 2번째 원소가 1입니다. 즉, 시작위치가 0, 끝위치가 2인 원소 'aba'가 팰린드롬임을 의미합니다.

4) 문자열 안에 있는 부분문자열이 팰린드롬인 경우, 해당 문자열을 answer 리스트에 저장합니다.

answer 리스트는 다음과 같습니다.

['a', 'b', 'a', 'c', 'a', 'b', 'a', 'aba', 'aca', 'aba', 'bacab', 'abacaba']

5) answer 리스트 안에 있는 중복 문자열과 빈도수를 구하기 위해 collections에서 Counter를 임포트합니다.

문자열의 길이와 빈도수를 곱한 후, 가장 큰 값을 출력합니다. Counter 함수를 적용한 결과는 다음과 같습니다.

Counter({'a': 4, 'aba': 2, 'abacaba': 1, 'aca': 1, 'b': 2, 'bacab': 1, 'c': 1})

6) 정답은 7입니다.

참고

https://velog.io/@himi/%EB%B0%B1%EC%A4%80-10942.-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC

오늘은 '파이썬 알고리즘 인터뷰'를 참고했습니다.

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

문제는 아래와 같습니다.

https://leetcode.com/problems/longest-palindromic-substring/

풀이 과정

저는 투포인터가 중앙을 중심으로 확장하는 형태로 풀이했습니다. 'babab'를 통해 가장 긴 팰린드롭을 구하는 풀이를 설명드리겠습니다.우선 [그림1]과 같이 길이가 2, 3인 두 개의 투포인터를 'babab'에 배치합니다.

여기서 A와 같이 투포인터가 가리키는 시작점과 끝점의 원소가 같다면, 팰린드롭을 의미합니다. [그림 1]에서 'bab', 'aba' 가 있습니다.

하지만 'aba' (A)의 경우, 다른 팰린드롭과 다르게 양옆에 문자열이 있어서 양옆으로 투포인터를 확장할 수 있습니다. 확장하면 'babab'가 됩니다. 이 역시 양끝이 서로 같기 때문에 팰린드롭입니다. 

우리는 가장 긴 팰린드롭을 구해야되기 때문에, 'babab' 안에 있는 팰린드롭에서 가장 긴 길이의 투포인터를 구합니다.

코드

def answer(self,s):

	#팰린드롬 판별 및 투 포인터 확장
	def expand(left,right):
		while left>=0 and right<len(s) and s[left]==s[right]: #팰린드롬인 경우
    		left-=1 #투 포인터 양옆으로 확장
       		right+=1
    	return s[left+1:right]
	
    #해당 사항이 없을 때 빠르게 리턴
	if len(s)<2 or s==s[::-1]:
		return s
	
    result=''
	
    #슬라이딩 윈도우 우측으로 이동
	for i in range(len(s)-1):
		result=max(result,expand(i,i+1),expand(i,i+2),key=len)
 	return result

하나의 노드로부터 시작해 차례대로 모든 노드들을 한 번씩 방문하는 그래프 탐색에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있습니다. 

오늘은 DFS에 대해서 알아보겠습니다.

DFS는 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색합니다.

이 그림을 통해 DFS의 원리를 알아보겠습니다. 노드 1에서 시작해서 차례대로 노드 7까지 순회합니다. 진행되는 방향을 보면 한 가지의 끝까지 탐색하고, 그 다음 가지를 순차적으로 탐색합니다. 전체적으로 위에서 아래로 깊게 탐색이 진행되는 것을 볼 수 있습니다. 

그림을 자세히 설명하자면 1부터 시작해서 막다른 곳에 다다를 때까지 연속으로 진행되는 탐색이 총 3번에 걸쳐 진행됩니다.

1->2->5->6까지 진행하고 그 다음 5로 되돌아갔다가 다음번 탐색은 7->3, 다시 되돌아 나가 마지막으로 시작 지점까지 올라가서 4를 탐색하고 종료합니다. 즉, 최종 결과는 1->2->5->6->7->3->4 입니다.

예를 들면, 미로에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 길을 찾는 것이라고 할 수 있습니다. DFS는 전체 정점을 맹목적으로 탐색할 때 사용합니다. DFS의 구현은 재귀 구조, 스택을 이용합니다.

1. DFS를 재귀 구조로 구현하는 방법을 알아보겠습니다.

Python CODE

graph_list = {1: set([2, 3, 4]),
              2: set([5]),
              3: set([5]),
              4: set([]),
              5: set([6, 7]),
              6: set([]),
              7: set([3])}

root_node = 1

def recursive_dfs(v,discovered=[]):
  discovered.append(v)
  for w in graph_list[v]:
    if w not in discovered:
      discovered=recursive_dfs(w,discovered)
  return discovered
recursive_dfs(1)

graph_list는 앞의 그래프를 딕셔너리로 나타낸 것입니다.

재귀 구조로 구현하는 과정은 아래와 같습니다.(CODE 해석)

1) 시작 노드를 방문한 후, 방문 기록(discovered)에 삽입합니다.

2) 시작 노드와 인접한 노드를 w로 지정합니다.

3) 재귀함수 recursive_dfs()에 w와 discovered를 삽입합니다.[이 때, w가 여러 개인 경우 가장 작은 w를 넣습니다]

    재귀함수에서 일어나는 과정은 아래와 같습니다.

    3-1) w 노드를 방문한 후, discovered에 삽입합니다.

    3-2) w 노드와 인접한 노드들 중 discovered에 없고(방문한 적이 없고) 가장 작은 노드를 선택합니다.

    3-3) 이것을 새로운 w노드로 지정합니다.

    3-4) 재귀함수 recursive_dfs()에 w와 discovered를 삽입합니다.

4) 모든 노드를 방문할 때 까지 3-1~3-4 과정을 반복합니다.

    4-1) 이 때, 중간에 끊기는 경우가 있습니다. 바로 3-2)에서 w노드와 인접한 노드가 없거나 모두 방문한 경우입니다.

   4-2) 이런 경우 직전 w노드로 돌아가서 해당 w노드와 인접하면서 방문한 적이 없는 노드를 새로 방문하고 3-1에서 다시 시작합니다.

           [예를 들면, 앞의 그림에서 1->2->5->6 에서 끊김을 알 수 있습니다. 이때 5 노드로 다시 돌아가서 방문한 적이 없는 7을

           새로 방문하는 것입니다. 이후 7은 w노드가 되고 discovered에 삽입됩니다.]

5) 완성한 discovered가 DFS로 구한 경로입니다.

2. DFS를 Stack으로 구현하는 방법을 알아보겠습니다.

Python CODE

graph_list = {1: set([2, 3, 4]),
              2: set([5]),
              3: set([5]),
              4: set([]),
              5: set([6, 7]),
              6: set([]),
              7: set([3])}

root_node = 1

def iterative_dfs(start_v):
  discovered=[]
  stack=[start_v]
  while stack:
    v=stack.pop()
    if v not in discovered:
      discovered.append(v)
      for w in graph_list[v]:
        stack.append(w)
  return discovered
iterative_dfs(1)

Stack으로 구현하는 과정은 아래와 같습니다.(CODE 해석)

1) 시작 노드를 방문한 후, Stack에 삽입합니다.

2) 가장 최근에 Stack에 삽입된 원소를 꺼내서 v로 지정합니다.

3) v가 한번도 방문한 적이 없는 노드인 경우 방문기록(discovered)에 삽입합니다.

     3-1) v가 방문한 적이 있는 노드인 경우 2 과정으로 돌아가서 계산합니다.

4) v와 인접한 노드들을 차례로 Stack에 삽입합니다. 

5) 2~4 과정을 Stack이 비어있을 때까지 반복합니다.

참고

https://velog.io/@sohi_5/algorithmDFS

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

그래프의 각 정점을 방문하는 그래프 탐색에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있습니다. 

오늘은 BFS에 대해서 알아보겠습니다.

BFS는 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

두 정점 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다.

BFS의 특징은 어떤 정점을 방문했었는지 여부를 반드시 검사 해야 하며 이를 지키지 않을 경우 무한루프에 빠질 위험이 있습니다. 따라서 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용합니다.

BFS 알고리즘을 먼저 보여드린 후, Python으로 구현한 코드를 제시하겠습니다.

1. BFS 알고리즘 - 순서

1. 시작 정점을 방문한 후 방문된 정점을 큐에 삽입합니다.(방문한 정점 체크)
2. 시작 정점의 이웃 정점을 모두 방문할때까지 방문된 정점을 큐에 삽입하는 과정을 반복합니다.
3. 큐에서 꺼낸 정점을 방문합니다.
4. 큐에서 꺼낸 정점과 인접한 정점들을 모두 방문합니다.
5. 이 때, 인접한 정점 중 새로 방문되는 점이 있다면, 큐에 삽입합니다.
6. 만약, 인접한 정점 중 새로 방문되는 점이 없다면, 큐에 삽입하는 과정 없이 [과정 3]으로 돌아갑니다.
7. 큐가 빈 공간이 될 때까지 [과정 3~6] 을 반복합니다.

2. BFS 알고리즘 - 예시

우선 그래프는 [그림 1]과 같습니다.

왼쪽은 그래프 그림, 오른쪽은 그래프 수식입니다. (수식에서 1: set([3,4])는 1은 3과 4를 가리킴을 의미합니다)

아래는 BFS가 진행되는 과정입니다.

과정은 (1)부터 (6)으로 구성됩니다. 초록색 동그라미는 현재 머무는 정점, 파란색 동그라미는 이미 방문한 정점을 의미합니다.

(1) 먼저, 시작점을 정합니다. 저희는 1로 정했습니다. 시작점 1을 큐와 방문기록에 삽입합니다.

(2) 1을 큐에서 뺍니다. 이후 1에서 인접한 접점 3과 4에 방문합니다. 방문한 점을 큐와 방문기록에 삽입합니다.

(3) 3을 큐에서 뺍니다. 이후 3에서 인접한 접점 1과 5에 방문합니다.

    하지만 1은 이미 방문한 점이기 때문에 넘어가고, 5에 방문합니다. 5를 큐와 방문기록에 삽입합니다.

(4) 4를 큐에서 뺍니다. 이후 4에서 인접한 접점 1에 방문합니다.

      하지만 1은 이미 방문한 점이기 때문에 통과하고 다음 단계인 (5)로 넘어갑니다.

(5) 5를 큐에서 뺍니다. 이후 5에서 인접한 접점 2와 6에 방문합니다. 2와 6을 큐와 방문기록에 삽입합니다.

(6) 방문기록은 최단이동경로와도 같습니다. 완성했습니다.

3. BFS 알고리즘 - CODE

앞의 예시를 파이썬으로 구현하면 아래와 같습니다.

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

from collections import deque

def iterative_bfs(graph, start_v):
    discovered=[start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
          if w not in discovered:
            discovered.append(w)
            queue.append(w)
    return discovered
  
print(iterative_bfs(graph_list, root_node))

출처

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

오늘은 문제를 주어진 시간 안에 다 풀지 못하고 다른 분들이 올려주신 코드를 리뷰하게 되었습니다.

코드에서 사용되는 함수가 유용하고 알고리즘이 간단하다는 점에서 향후 문제를 풀 때 도움이 될 것 같습니다.

그래서 기록용으로 게시글을 올렸습니다.

문제는 아래와 같습니다.

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

코드는 다음과 같습니다.

출처: https://programmers.co.kr/learn/courses/30/lessons/43165/solution_groups?language=python3 

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s=list(map(sum,product(*l)))
    return s.count(target)
solution([1,1,1,1,1],3)

풀이과정

설명을 위해 중간에 print 함수를 추가했습니다.

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(product(*l))
    ss=list(map(sum,product(*l)))
    print(l)
    print(s)
    print(ss)
    return ss.count(target)
solution([1,1,1,1,1],3)

 [1,1,1,1,1]을 numbers로, 3을 target으로 할 때, solution 함수의 print(l), print(s), print(ss), 결과값은 아래와 같습니다.

• print(l)을 통해 numbers의 각 숫자와 마이너스 형태를 취한 숫자를 튜플 형태로 나타냈습니다.
• list(product(*l))을 통해 (1,1,1,1,1) 부터 (-1,-1,-1,-1,-1) 까지 1과 -1로 구성할 수 있는 배열을 튜플 형태로 나타냈습니다.
• 마지막으로 map과 sum 함수를 이용해 앞에서 구한 배열을 합쳤습니다. 예를 들면, (1,1,1,1,1)은 5가 되는 것입니다.
• 결과값으로 ss에서 target인 개수를 반환했습니다.

문제는 아래와 같습니다.

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