스택 (LIFO)

stack=[]

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)

print(f'1st: {stack}')
stack.pop()
print(f'2nd: {stack}')
stack.append(1)
stack.append(4)

stack.pop()
print(f'3rd: {stack}')


print(f' 최상단: {stack[::-1]}') # 최상단 원소부터 출력
print(f' 최하단 : {stack}') # 최하단 원소부터 출력

1st: [5, 2, 3, 7]
2nd: [5, 2, 3]
3rd: [5, 2, 3, 1]
최상단: [1, 3, 2, 5]
최하단 : [5, 2, 3, 1]

큐 (FIFO) :deque 라이브러리

from collections import deque

queue=deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)

print(f'1st: {queue}')
queue.popleft() #popright도 가능 
print(f'2nd: {queue}')

queue.append(1)
queue.append(4)

queue.popleft()
print(f'3rd: {queue}')

# 역순
queue.reverse()
print(f'reversed: {queue}')

1st: deque([5, 2, 3, 7])
2nd: deque([2, 3, 7])
3rd: deque([3, 7, 1, 4])
reversed: deque([4, 1, 7, 3])

• 리스트만 반환하는게 아니라 deque도 같이 반환

BFS DFS

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

BFS: 가까운것부터 찾는다. 빠르다
DFS: 모든것

재귀함수(Recursive fnc): dfs에 이용

• 재귀함수에서 종료조건을 반드시 명시한다.

def recursive_fnc(i):
    # 100번째 호출시 종료 되도록 조건 명시
    if i==100:
        return
    print(f'{i}번째 재귀함수에서 {i+1}번째 재귀함수 호출')
    recursive_fnc(i+1)
    print(f'{i}번째 재귀함수를 종료')
recursive_fnc(1)

팩토리얼 구현

# 반복적으로 구현한 n!
def factorial_iterative(n):
    res=1
    # 1부터 n까지의 수를 차례로 곱하기
    for i in range(1, n+1):
        res*=i
    return res

# 재귀적으로 구현한 n!
def factorial_iter(n):
    if n<=1: # 0!과 1!은 1이므로 
        return 1
    return n* factorial_iter(n-1)

print('반복적', factorial_iterative(5))
print('재귀적', factorial_iter(5))

반복적 120
재귀적 120

유클리드호제법( 최대공약수 계산)

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b, a%b)
print(gcd(192,162))

6

• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택프레임에 쌓임> 구현상 스택 라이브러리 대신 재귀함수 이용 多

DFS: 깊이우선 탐색: 스택

• 스택 자료구조(or 재귀함수) 이용
• 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드 꺼냄
  
• 시작노드인 '1'을 스택에 삽입하고 방문처리
  
  
• 숫자는 8까지. 2차원리스트 노드는 9개

# dfs 메소드 정의
def dfs(graph, v, visitied):
    # 현재노드를 방문처리
    visited[v]=True
    print(v,end=' ')
    # 현재노드와 연결된 다른 노드를 재귀적으로 방문 
    for i in graph[v]: # 노드별로 연결된 숫자들
        if not visited[i]:
            dfs(graph, i, visited)

            
            
# 노드정보 2차원 리스트
graph=[
    [], # 인덱스 0은 비워둔다 
    [2,3,8], # 인덱스 1의 내용 
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 노드가 방문된 정보 (1차원 리스트)
visited=[False]*9

            
dfs(graph, 1, visited)

1 2 7 6 8 3 4 5

BFS : 너비우선탐색 :큐

• 가까운 노드부터 우선탐색
• 큐에서 노드를 꺼낸 뒤 해당노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
  
  
  

from collections import deque


def bfs(graph, start, visited):
    queue=deque([start])
    visited[start]=True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v=queue.popleft()
        print(v,end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입 
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
            
# 노드정보 2차원 리스트
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 노드가 방문된 정보 (1차원 리스트)
visited=[False]*9

            
bfs(graph, 1, visited)

1 2 3 8 7 4 5 6

음료수 얼려먹기 : DFS or BFS

• n * m 크기의 얼음틀, 구멍 뚫린부분은 0, 칸막이 부분은 1. 아이스크림 갯수 구하라 (0 부분)
• 입력조건:
  - 첫번째 줄에 얼음 틀의 세로 길이 N과 가로길이 M이 주어짐( 1 <=N, M<=1,000)
  • 두번째 줄부터 N+1번째 줄까지 얼음틀의 형태가 주어짐
  • 이때 구멍이 뚫려있는 부분은 0, 그렇지 않으면 1
• 출력조건: 한번에 만들 수 있는 아이스크림 갯수 출력
• 입력예시
  4 5
  00110
  00011
  11111
  00000
• 출력에시
  3

• 방문되지 않은 지점의 수를 카운트

n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result) # 정답 출력

3
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] # graph

미로탈출 문제 :BFS

• 입력조건: 첫째줄에 두 정수 N,M(4<=N,M<=200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수( 0 1) 로 미로 정보가 주어집니다. 각각의 수들은 공백없이 붙어서 입력으로 제시됩니다. 또한 시작칸과 마지막칸은 항상 1입니다.
• 출력조건: 첫째줄에 최소 이동칸의 갯수를 출력
• 입력예시:
  5 6
  101010
  111111
  000001
  111111
  111111
• 출력예시: 10

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

다이나믹 프로그래밍(동적계획법)

• 탑다운 바텀업

최적부분구조 (optimal substructure)
- 작은문제를 모아서 큰 문제 해결
중복되는 부분문제(overlapping subproblem)
-동일 작은문제 반복적 해결

피보나치수열

• 피보나치 수열이 계산되는 과정
  

  # 피보나치수열 단순재귀 
  def fibo(x):
     if x==1 or x==2:
         return 1
     return fibo(x-1)+fibo(x-2)
  print(fibo(7))

  13

  메모이제이션(memoization) :하향식 (탑다운)

• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
• 값을 기록해서 캐싱(caching)이라고도 함
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업:
• 보텀업 결과저장용 리스트 :dp테이블

  피보나치 (메모이제이션) :탑다운

  
  d=[0]*100
  def fibo(x):
     if x==1 or x==2:
         return 1
     if d[x] !=0:
         return d[x]
     d[x]=fibo(x-1)+fibo(x-2)
     return d[x]
  print(fibo(99))

  218922995834555169026

  피보나치 : 바텀업

  d=[0]*100
  d[1]=1
  d[2]=1
  n=99
  for i in range(3,n+1):
    d[i]=d[i-1]+d[i-2]
  print(d[n])
  

  218922995834555169026

  메모이제이션 피보나치 시간복잡도 O(N)

  
  # 메모이제이션 이용시 피보나치 수열 함수시간 복잡도 O(N)

d=[0]*100
def fibo(x):
    print(f'f({x})', end=' ')
    if x==1 or x==2:
        return 1
    if d[x]!=0:
        return d[x]
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]
fibo(6)

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)
8

다이나믹 프로그래밍 vs 분할정복:

• 분할정복에서 동일한 문제가 부분적으로 반복되지 않음

• 분할정복: 퀵정렬

• 가장 먼저 그리디, 구현, 완전탐색 등의 아이디어로 해결되는지 검토
  => 다른 풀이방법이 떠오르지 않으면 다이나믹프로그래밍

• 일단 재귀함수로 비효율적인 완전탐색 프로그램을 작성한 뒤(탑다운)
  작은 문제에서 구한답이 큰 문제에서 그대로 사용 된다면 코드개선

• 일반적인 코테에서는 기본유형 다이나믹프로그래밍 문제가 출제되는 편

  개미전사

• 인접한 곳으로 갈 수 없음

• 입력조건:
  -첫째줄에 식량창고의 개수 N이 주어짐( 3<=N<=100)
  -둘째줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수K가 주어짐(0<=K<=1000)

• 출력조건:
  -첫째줄에 개미전사가 얻을 수 있는 식량의 최대값을 출력하라

• 입력예시:
  4
  1 3 1 5

• 출력예시: 8
  

  점화식
  ai=max(a(i-1), a_(i-2)+k_i)

  n=int(input())
  
  array=list(map(int, input().split()))
  
  # dp테이블 초기화
  d=[0]*100
  
  # 다이나믹 프로그래밍 진행(보텀업)
  d[0]=array[0]
  d[1]=max(array[0],array[1])
  for i in range(2,n):
      d[i]=max(d[i-1],d[i-2]+array[i])
  
  print(d[n-1])

  8

  1로 만들기

• 정수x가 주어졌을때, 4가지 연산을 통해 x를 1로 만들기

  • 5로 나눠떨어지면 5로 나눔
  • 3으로 나눠떨어지면, 3으로 나눔
  • 2로 나눠떨어지면, 2로 나눔
  • x에서 1을 뺀다.

• 입력조건: 첫째줄에 정수 x가 주어집니다( 1<=x<=30,000)

• 출력조건: 첫째줄에 연산을 하는 횟수의 최솟값을 출력합니다

• 입력예시: 26

• 출력예시: 3

  점화식
  ai=min(a(i-1), a_i/2, a_i/3, a_i/5) +1 (단, 해당수의 배수여야 적용)

  x=int(input())
  d=[0]*30001
  
  # 다이나믹 프로그래밍 진행(보텀업)
  for i in range(2, x+1):
      # 현재수에서 1을 빼는 경우
      d[i]=d[i-1]+1
      if i%2==0:
          d[i]=min(d[i],d[i//2]+1)
      if i%3==0:
          d[i]=min(d[i],d[i//3]+1)
      if i%5==0:
          d[i]=min(d[i],d[i//5]+1)
  print(d[x])

  3

효율적인 화폐 구성

• a_i: 최소화폐 개수
• k: 각 화폐단위
• 점화식:
  -a(i-k) 만드는 방법이 있는 경우: a_i=min(a_i, a(i-k)+1)
  -a_(i-k) 만드는 방법이 없는 경우: a_i=INF

n,m=map(int,input().split())

array=[]
for i in range(n):
    array.append(int(input()))

#dp초기화
d=[10001]*(m+1)


# 다이나믹 프로그래밍 진행 (보텀업)
d[0]=0
for i in range(n):
    for j in range(array[i], m+1):
        
        # (i-k) 만드는 방법이 없는 경우
        if d[j-array[i]] !=10001:
            d[j]=min(d[j], d[j- array[i]]+1)

# 최종적으로 M원을 만드는 방법이 없는 경우 
if d[m]== 10001:
    print(-1)
else:
    print(d[m])

5

금광

# 테스트케이스 입력
for tc in range(int(input())):
    n,m=map(int, input().split())
    array=list(map(int, input().split()))
    dp=[]
    idx=0
    for i in range(n):
        dp.appedn(array[idx:idx+m])
    
    # 다이나믹 프로그래밍 진행
    for j in range(1,m):
        for i in range(n):
            # 왼쪽 위에서 오는 경우
            if i==0: left_up=0
            else: left_up=dp[i+1][j-1]
            # 왼쪽 아래에서
            if i==n: left_down=0
            else: left_down=dp[i+1][j-1]
            # 왼쪽에서 오는 경우
            left=dp[i][j-1]
            dp[i][j]=dp[i][j]+ max(left_up, left_down, left)
    result=0
    for i in range(n):
        result=max(result, dp[i][m-1])
    print(result)

병사 배치하기

• 시간: O(N^2) 이하 복잡도여야 함
• LIS (가장 긴 증가하는 부분수열) : 전형적인 다이나믹 프로그래밍
  
  

n=int(input())
array=list(map(int, input().split()))

# 순서를 뒤집어 '최장 증가 부분 수열 문제'로 변환
array.reverse()

dp=[1]*n
# LIS 수행
for i in range(1,n):
    for j in range(0,i):
        if array[j]< array[i]:
            dp[i]=max(dp[i], dp[j]+1)
# 열외해야 하는 병사 최소수
print(n-max(dp))