희연's 개발 일기장

동적 계획법(Dynamic Programming)

• 최적화 이론의 한 기술
• 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘
• 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용한다.
• ex. 피보나치 수열에서 중복된 연산을 미리 배열을 만들어두고 값을 저장해두면(메모이제이션) 시간 복잡도 O(N)으로 개선 가능
• 상향식 접근법 : for으로 구현, 작은 문제를 모아 큰 문제 해결, 메모제이션 사용X
• 하향식 접근법 : 재귀함수 구현, 큰 문제를 해결하기 위해 작은 재귀 함수 호출, 메모제이션 사용
• 보통 동적 계획법은 상향식 접근법을 사용

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

DP 문제 - 1463번 1로 만들기

• 정수 N이 주어질 때, 세 개의 연산을 적절히 사용해서 1을 만드려고 한다. 연산 사용 횟수의 최소값 구하기 

1. 테이블 정의하기

• D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

2. 점화식 찾기

• D[12] = ?
• 3으로 나누거나 D[12] = D[4] + 1
• 2으로 나누거나 D[12] = D[6] + 1
• 1을 빼거나 D[12] = D[11] + 1
• D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)

3. 초기값 정의하기

• D[1] = 0

n = int(input()) # 정수 N
dp = [0]*(n+1) # dp에 계산된 값을 저장해두고
dp[1] = 0

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1)
    if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1)

print(dp[n])

DP 문제 - 9095번 1,2,3 더하기

• 정수 n이 주어질 때, n을 1,2,3의 합으로 나타내는 방법의 수 구하기

1. 테이블 정의하기

• D[i] = i를 1,2,3의 합으로 나타내는 방법의 수

2. 점화식 찾기

• D[4] = ?
• 1+1+1+1, 3+1, 2+1+1, 1+2+1 // (3을 1,2,3 합으로 나타내는 방법) + 1, D[3]
• 1+1+2, 2+2 // (2를 1,2,3 합으로 나타내는 방법) + 2, D[2]
• 1+3 // (1을 1,2,3 합으로 나타내는 방법) + 3, D[1]
• D[4] = D[1] + D[2] + D[3]

3. 초기값 정의하기

• D[1] = 1, D[2] = 2, D[3] = 4 방법의 개수 
• D[i] = D[i-1] + D[i-2] + D[i-3]

tc = int(input())

for _ in range(tc):
    n = int(input())
    if n == 1:
        print(1)
    elif n == 2:
        print(2)
    elif n == 3:
        print(4)
    else:   
        dp = [0] * (n + 1)
        dp[1], dp[2], dp[3] = 1, 2, 4
        for i in range(4, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        print(dp[n])

DP 문제 - 2579번 계단 오르기

• 각 계단에 쓰여 있는 점수가 주어질 때 게임에서 얻을 수 있는 총 점수의 최대값 구하기

1. 테이블 정의하기

• D[i][j] = 현재부터 j개의 계단을 연속해서 밟고 i번째 계단에서 얻을 수 있는 점수 합의 최대값 + i번째 계단은 반드시 밟아야 한다.
• (연속된 세 계단을 모두 밟아서는 안되는 제약조건) 

2. 점화식 찾기

• D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k] // 1개의 계단을 연속해서 밟고, k번째 계단까지 최대값 
  • 1개의 계단을 밟았다 = k-1번째는 밟지 않았다. = k-2번쨰는 무조건 밟았다.
  • S[k] : k번째 계단 점수
• D[k][2] = D[k-1][1] + S[k] // 2개의 연속된 계단을 밟고, k번째 계단까지 최대값
• j는 3개 연속이 불가능하기 때문에 3 이상일 수 없다.

3. 초기값 정의하기

• D[1][1] = S[1], D[1][2] = 0
• D[2][1] = S[2], D[2][2] = S[1] + S[2]

n = int(input()) # 계단의 개수
S = [0]*(n+1)
for i in range(1, n+1):
    S[i] = int(input())

if n == 1:
    print(S[1])
elif n == 2:
    print(S[1]+S[2])
else:
    dp = [[0 for col in range(3)] for row in range(n+1)]
    dp[1][1], dp[1][2] = S[1], 0
    dp[2][1], dp[2][2] = S[2], S[1]+S[2]
    # 계단 오르기 규칙
    # 1. 한 계단 또는 두 계단 오르기 가능
    # 2. 연속 세개 계단 불가능(시작점은 포함X)
    # 3. 마지막 계단 무조건 밟기

    for i in range(3,n+1):
        dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + S[i]
        dp[i][2] = dp[i-1][1] + S[i]

    print(max(dp[n][1], dp[n][2]))

DP 문제 - 1149번 RGB거리

• 집의 색상은 빨강, 초록, 파랑 중 하나의 색상
• 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어질 때, 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값 구하기

1. 테이블 정의하기

• D[i][0] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 빨강
• D[i][1] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 초록
• D[i][2] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 파랑

2. 점화식 찾기

• D[k][0] = min(D[k-1][1], D[k-1][2]) + R[k] // 빨강으로 칠할 때 k-1 집은 초록 or 파랑 + R[k] 빨강 비용
• D[k][1] = min(D[k-1][0], D[k-1][2]) + G[k] // 초록으로 칠하면 빨강 or 파랑
• D[k][2] = min(D[k-1][0], D[k-1][1]) + B[k] // 파랑으로 칠하면 빨강 or 초록

3. 초기값 정하기

• D[1][0] = R[1]
• D[1][1] = G[1]
• D[1][2] = B[1]

n = int(input())  # 집 개수
R = [0] * (n + 1)
G = [0] * (n + 1)
B = [0] * (n + 1)
dp = [[0 for col in range(3)] for row in range(n + 1)]
for i in range(1, n + 1):
    color = list(input().split())
    R[i] = int(color[0])
    G[i] = int(color[1])
    B[i] = int(color[2])

if n == 1:
    print(min(R[1], G[1], B[1]))

else:
    # 초기값 설정
    dp[1][0] = R[1]
    dp[1][1] = G[1]
    dp[1][2] = B[1]
    # 집 색칠 규칙
    # 1. 1번의 집 색상은 2번의 집 색상과 같지 않아야 한다.
    # 2. N번 집의 색상은 N-1번의 집 색상과 같지 않아야 한다.
    # 3. 2(<= i <= N-1)번의 집 색상은 i-1번, i+1번 집의 색상과 같지 않아야 한다.

    for k in range(2, n + 1):
        dp[k][0] = min(dp[k - 1][1], dp[k - 1][2]) + R[k] # 이전색상 초록 or 파랑 + 현재 빨강
        dp[k][1] = min(dp[k - 1][0], dp[k - 1][2]) + G[k] # 이전색상 파랑 or 빨강 + 현재 초록
        dp[k][2] = min(dp[k - 1][0], dp[k - 1][1]) + B[k] # 이전색상 빨강 or 파랑 + 현재 파랑

print(min(dp[n][0], dp[n][1], dp[n][2]))

DP 문제 - 11726번 2xn 타일링

• 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하기

1. 테이블 정의하기

• D[i] = 2xi 크기의 직사각형을 채우는 방법의 수

2. 점화식 찾기

• D[i] = D[n-1] + D[n-2]
• 2 x 1 타일로 1개씩 채우면 남는 방법의 수 n-1
• 1 X 2 타일로 2개 채우면 남는 방법의 수 n-2

3. 초기값 정하기

• D[1] = 1
• D[2] = 2

n = int(input())
dp = [0]*1001

dp[1] = 1
dp[2] = 2

for i in range(3, 1001):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007
print(dp[n])

DP 문제 - 11659번 구간 합 구하기 4

• dp[i] = arr[1] + arr[2] + arr[3] + .. + arr[i]
• dp[i] = dp[i-1] + arr[i]

import sys
n, m = map(int, sys.stdin.readline().split()) # 수의 개수, 합을 구해야하는 횟수
arr = list(map(int, sys.stdin.readline().split()))
dp = [0]*(n+1)
# D[i] = A[1] + A[2] + .. + A[i]
# D[i] = D[i-1] + A[i]
for i in range(1, n+1):
    dp[i] = dp[i-1] + arr[i-1]

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    print(dp[j]-dp[i-1])

자료구조(Data Structure)

• 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장
• 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령
• 자료구조를 통해 효율적인 알고리즘을 사용할 수 있다.

구현에 따라

• 배열 - 일반적인 구조. 같은 타입형의 자료가 연속으로 저장된다.
• 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조
• 연결 리스트 - 노드를 단위로, 노드는 자료와 다음 노드를 가리키는 참조 값으로 구성되어 있따.
• 해시 테이블 - 개체가 해시 값에 따라 인덱싱

형태에 따라

• 선형 구조
  • 스택 - LIFO 구조, 먼저 저장된 것이 가장 마지막에 나온다. 파이썬의 리스트 사용
  • 큐 - FIFO 구조, 먼저 저장된 것이 제일 먼저 나온다. 파이썬 리스트를 사용해도 되지만, 리스트는 동적 배열로 큐의 연산을 수행하기에 효율적이지 않아 덱을 사용한다.
  • 덱 - 양쪽에서 넣고 빼고 할 수 있는 일반화된 선형 구조. 파이썬 deque 사용
    • BFS 문제
• 비선형 구조
  • 그래프 - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다. 무향 그래프, 유향 그래프가 있다.
  • 트리 - 뿌리와 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점으로 이루어진 구조. 부모 자식 관계는 간선으로 표시
    • 이진 트리 - 자식이 최대 두개
      • 힙(heap) - 이진트리의 일종으로 최대값과 최소값을 찾아내는 연산을 빠르게 하기 위해 완전 이진트리(complete binary tree) + 힙 속성(property)를 만족한다. 파이썬 heapq 사용 
        • 우선순위 큐(Priority Queue) : 먼저 저장된 데이터가 먼저 나오는 것이 아니라, 우선순위가 높은 순서대로 나가는 형태의 자료구조. 힙을 이용해서 구현한다.
        • 최소값, 최대값 문제
        • 다익스트라 문제
      • heap property : A가 B의 부모노드이면, A의 키 값과 B의 키 값에는 대소관계가 성립한다.

스택 문제 - 1874번 스택 수열

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

#n = 8 # 정수의 개수, 최대 정수값
#arr = [4,3,6,8,7,5,2,1]
n = int(input())
stack = []
maxIdx = 1
answer = []
flag = False

# push 오름차순
for i in range(n):
    x = int(input())
    while maxIdx <= x:
        stack.append(maxIdx)
        answer.append('+')
        maxIdx += 1

    if stack[-1] == x:
        stack.pop()
        answer.append('-')

    else: #stack[-1] != x:
        flag = True
        break


if flag:
    print('NO')
else:
    for x in answer:
        print(x)

큐 문제 - 1158번 요세푸스 문제

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

from collections import deque
# n, k = 7, 3 # 사람 수, 제거하는 사람 위치
n, k = map(int,input().split())
queue = deque() # 덱으로 큐 생성
answer = '<'

# 요소 삽입
for x in range(1, n+1):
    queue.append(x)

while queue:
    for x in range(k-1):
        element = queue.popleft() # 맨 왼쪽에 있는 값 꺼내서
        queue.append(element) # 맨 뒤로 삽입
    answer += str(queue.popleft()) + ', '

print(answer[:-2]+'>')

큐 문제 - 1966번 프린터 큐

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

from collections import deque

tc = int(input()) # 테스트 케이스 수
for _ in range(tc):
    n, m = map(int, input().split()) # 문서 개수, 찾을 위치
    arr = list(map(int, input().split())) # 문서 중요도 배열
    pq = deque() # 덱으로 큐 생성

    # (인덱스, 중요도) 값으로 덱 요소 삽입
    for x in range(len(arr)):
        pq.append((x, arr[x]))
    importList = sorted(arr, reverse=True)  # 중요도 순서
    importIdx = 0
    cnt = 0
    while pq:
        element = pq.popleft()
        if importList[importIdx] == element[1]:  # 중요도 순서가 맞는 경우
            importIdx += 1
            cnt += 1
            if element[0] == m:  # 찾는 인덱스와 일치할 경우
                print(cnt)
                break
        else:
            pq.append(element)  # 맨 왼쪽 오른쪽에 삽입

덱 문제 - 2346번 풍선 터뜨리기

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

import sys
from collections import deque

n = int(input())
dq = deque(enumerate(map(int, input().split())))
answer = []

while dq:
    idx, nextIdx = dq.popleft()
    answer.append(idx+1)

    if nextIdx > 0:
        dq.rotate(-(nextIdx-1))
    else:
        dq.rotate(-nextIdx) # rotate = d.appendleft(d.pop()) : 오른쪽 끝값을 왼쪽 끝으로 보낸다.

print(*answer)

우선순위 큐 문제 - 11286번 절댓값 힙

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

import heapq
import sys

n = int(input())  # 연산의 개수 18
# arr = [1, -1, 0, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0, 0, 0, 0, 0, 0]  # 연산에 대한 정보
# 0 x : 배열에서 절댓값이 가장 작은 값 출력하고 값 제거
# 1 x : 값을 넣는 연산
heap = []

for i in range(n):
    x = int(sys.stdin.readline())
    if x != 0:  # 값 넣기
        heapq.heappush(heap, (abs(x), x))
    else:
        # 배열에서 절댓값이 가장 작은 값 출력하고 값 제거
        # 같은 값이 여러개면 가장 작은 수 출력
        # 배열이 비어있으면 0 출력
        if len(heap) == 0:
            print(0)
        else:
            element = heapq.heappop(heap) # heappop : 가장 작은 값 제거 + return
            print(element[1])

우선순위 큐 문제 - 1715번 카드 정렬하기

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

import heapq
n = int(input()) # 숫자 카드 묶음 개수
heap = []
answer = 0

for _ in range(n):
    x = int(input())
    heapq.heappush(heap, x)

while len(heap)!=1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    answer += a + b
    heapq.heappush(heap, a+b)

print(answer)

해시(Hash)

• 데이터를 다루는 방법 중 하나로, O(N) 시간 복잡도를 가진 연산을 O(1) 시간 복잡도로 해결할 수 있다.
• key-value 형태로 데이터가 저장된다.

해시 함수(Hash function)

• 임의의 길이를 갖는 임의의 데이터를 고정되 길이의 데이터로 매핑하는 단방향 함수
• 해시 값 : 해시 함수를 적용하여 나온 값, 해시 코드, 해시섬(sum), 체크섬 등으로 불린다.
• 해시 충돌(hash collision) : 서로 다른 키가 같은 해시가 되는 경우 

해시 테이블(Hash Table)

• 연관 배열 구조(associative array)를 사용해서 데이터를 key, value으로 저장하는 자료구조
  • 연관 배열 구조 : 키 1개와 값 1개가 1:1으로 연관되어 있는 자료구조

딕셔너리(Dictionary)

• dictionary는 해시 테이블(hash table)

Set

- 순서가 없는 데이터의 집합

- 중복 허용 X

- HashSet, TreeSet

Map

- key, value가 한 쌍으로 이루어지는 데이터의 집합

- 순서가 없는 데이터의 집합

- key 중복 허용 X, value는 중복 허용

- HashMap, TreeMap, Hashtable, Properties

Hash

- 순서가 없다.

Tree

- 트리 구조로, 순서 유지

HashMap vs HashSet vs TreeMap vs TreeSet

해시 문제 - 7785번 회사에 있는 사람

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

from collections import defaultdict
#n = 4 # 출입 기록 수
# arr = ['Baha enter', 'Askar enter', 'Baha leave', 'Artem enter']

# enter 출근, leave 퇴근
# 대소문자 구분
# 현재 회사에 있는 모든 사람을 구하는 프로그램 작성
n = int(input())
dict = defaultdict(str)

for x in range(n):
    name, opt = input().split()
    if dict[name] == 'enter' and opt == 'leave':
        del dict[name]
    else:
        dict[name] = opt

for x in sorted(dict.keys(),reverse=True):
    print(x)

해시 문제 - 14425번 문자열 집합

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

from collections import defaultdict
n, m = map(int, input().split())
answer = 0
S = defaultdict(int)
for x in range(n):
    key = input()
    S[key] = 1

for x in range(m):
    key = input()
    if S[key]:
        answer += 1
print(answer)

투포인터

• 배열에서 이중 for문으로 O(N^2) 시간복잡도를 가진 탐색을 하는 문제에서 포인터 2개를 사용해 O(N)으로 해결하는 알고리즘

슬라이딩 윈도우(Sliding Window)

• 투 포인터와 비슷하지만, 고정 사이즈의 윈도우를 이동시키는 알고리즘
• 정렬된 배열이 아니여도 사용 가능

구간합(prefix sum)

• 수열에서 특정 구간의 합
• i ~ j 번째 인덱스 값들의 값

부분합(partial sum)

• 0 ~ n 번째 인덱스 값들의 합

누적합(prefix)

• 수열의 특정 구간의 값을 구하는 요청이 여러개인 경우 시간 복잡도를 O(N^2)에서 O(N)으로 줄이기 위해 사용된다.

누적합의 성질

• 1차원 배열 공간 복잡도는 O(n), 2차원의 공간 복잡도 O(n^2)
• 계산은 O(1) 시간 복잡도
• 합을 구하는 도중에 배열의 값이 변경되면 세그먼트 트리 사용

sumArr[0] = arr[0]
sumArr[i] = sumArr[i-1] + arr[i]
sumArr[n] = arr[0] + arr[1] + ... + arr[n-1] + arr[n]
sumArr[j]-sumArr[i] = arr[i] + arr[i+1] + ... + arr[j-1] + arr[j]

누적합 문제 예시 - 1차원 배열

• index 3~5의 값
  • arr[3] + arr[4] + arr[5] = 6 + 10 + 3 = 19
  • sumArr[5] - sumArr[2] = 31 - 12 = 19 

누적합 문제 예시 - 2차원 배열

• 2차원 배열

• 첫 번째로 행끼리 누적합을 구해준다.

• 두 번째로 열끼리 누적합을 구해준다.

• (3,3)에서 (4,4) 노란색 부분의 합을 구하려고 할 때
• sumArr[x2][y2] - sumArr[x2][y-1] - sumArr[x1][y2] + sumArr[x1-1][y1-1]
• sumArr[4][4](전체) - sumArr[4][2](초록색) - sumArr[2][4](파란색) + sumArr[2][2] = 노란색 구역의 합
• 빨간색 영역은 초록색과 파란색 영역의 누적합을 뺄 때 제거된다. 
• 두 영역에서 빨간색 영역을 두 번 빼줬기 때문에 한 번 더해준다.

투포인터 문제 - 2230번 수 고르기

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

n, m = 5, 3  # 정수 개수, 두 개의 정수 차이 최소 기준
arr = [1, 2, 3, 4, 5]
#n, m = map(int, input().split())
#arr = [int(input()) for _ in range(n)]
arr.sort()
lt = 0
rt = 0
minValue = float('inf')
# print(arr)
while rt != n and lt <= rt:
    value = arr[rt] - arr[lt]
    if value >= m:  # m 이상일 때
        minValue = min(minValue, value)
        lt += 1
    else:  # m 이상이 아닐 때
        rt += 1
print(minValue)

투포인터 문제 - 1806번 부분합

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

#n, s = 10, 15
#arr = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]
n, s = map(int,input().split())
arr = list(map(int,input().split()))

lt = 0
rt = 0
minLen = float('inf')
value = 0

while True:
    # 수들의 합이 s를 넘으면 최소값을 계산
    # 안넘으면 rt 값 증가
    if value >= s:
        minLen = min(minLen, (rt - lt))
        value -= arr[lt]
        lt += 1
    elif rt == n:
        break
    else: # value < s:
        value += arr[rt]
        rt += 1

if minLen == float('inf'):
    minLen = 0

print(minLen)

누적합 문제 - 11660번 구간 합 구하기 5

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

import sys
# n, m = 4, 3 # 표의 크기, 연산 횟수
n, m = map(int, input().split())
arr = [[0]*(n+1)] + list([0]+list(map(int, input().split())) for _ in range(n))
sumArr = [[0]*(n+1) for _ in range(n+1)]

# 누적합 배열 만들기
for i in range(1, n+1):
    for j in range(1, n+1):
        sumArr[i][j] = sumArr[i-1][j] + sumArr[i][j-1] - sumArr[i-1][j-1] + arr[i][j]

# 계산 하기 - (x1, y1) 부터 (x2, y2) 합 구하기
# 전체 - 영역1 - 영역2 + (영역1과 영역2에서 두번 빼줬기 때문에 더해줘야 하는 영역)
for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    res = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1]
    print(res)

그리디(Greedy)

• 현재 상황에서 가장 최적의 답을 선택하는 알고리즘
• 최종적으로 최적의 해가 나온다는 보장이 없다.
• 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성의 문제에 적합하다.
  • 최적 부분 구조 예시 : (서울과 대구의 최단 경로) + (대구와 부산의 최단 경로) = 서울과 부산의 최단 경로
• 한 번의 선택이 다음 선택에 무관해야 하고, 매 순간의 최적해가 문제에 대한 최적해여야 한다.
• 활용 예시
  • 거스름돈, 다익스트라 알고리즘, 허프만 코드, 크루스칼 알고리즘

그리디 문제 - 11047번 동전 0

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

# n, k = 10, 4200  # 동전 종류, 구하려는 값 - 동전의 최소 개수 구하기
# arr = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
n, k = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr = sorted(arr, reverse=True)
cnt = res = 0

for x in arr:
    if k >= x:
        cnt = k // x
        res += cnt
        k = k - (x * cnt)
    if k <= 0:
        break
print(res)

그리디 문제 - 1931번 회의실 배정

- 최대 회의 횟수 구하기

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

n = int(input())  # 회의 수 - 회의가 겹치지 않게 진행할 수 있는 회의 최대 개수 구하기
arr = [[0] * 2 for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    arr[i][0] = a # 회의 시작 시간
    arr[i][1] = b # 회의 끝나는 시간

#n = 11
#arr = [[1, 1], [1, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
#n = 3
#arr = [[1,1],[1,1],[0,1]]
arr.sort(key=lambda x: (x[1], x[0])) # 두번째 값이 같은 경우, 첫번째 값으로 오름차순
time = cnt = start = end = 0

for element in arr:
    start = element[0]
    end = element[1]
    if time <= start:
        time = end
        cnt += 1
print(cnt)

그리디 문제 - 11000번 강의실 배정

- 최소 강의실 개수 구하기

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

# 최소 강의실 개수 구하기
import heapq
import sys

input = sys.stdin.readline
N = int(input())  # 수업의 개수

class_list = []

for _ in range(N):
    x, y = map(int, input().split())
    class_list.append([x, y])

class_list.sort()
heap = []
heapq.heappush(heap, class_list[0][1])  # 첫 번째 강의 끝나는 시간
# heap 최소 힙 유지 = 0 번째 인덱스는 가장 작은 값

for idx in range(1, N):
    start, end = class_list[idx]
    if start < heap[0]: # 빠른 시작 시간 < 앞에서 가장 빨리 끝나는 값
        heapq.heappush(heap, end) # 새 강의실 추가
    else: # 강의실 유지, 강의 시간 갱신
        heapq.heappop(heap)
        heapq.heappush(heap, end)
print(len(heap))

그리디 문제 - 2217번 로프

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

# n = 2  # 로프의 개수
# arr = [10, 15]  # 로프가 버틸 수 있는 최대 중량
n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr = sorted(arr, reverse=True)
maxRes = 0

# 내림차순으로 들을 수 있는 로프 개수 * 현재 무게를 계산해서 최대값을 구해준다.
for k in range(n):
    maxRes = max(arr[k]*(k+1), maxRes)
print(maxRes)

그리디 문제 - 1026번 보물

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

# n = 5  # 정수의 개수
# arrA = [1, 1, 1, 6, 0]  # A 정수 배열
# arrB = [2, 7, 8, 3, 1]  # B 정수 배열

n = int(input())
arrA = list(map(int, input().split()))
arrB = list(map(int, input().split()))

# S = A[0] * B[0] + A[1] * B[1] + ...+ A[N-1] * B[N-1]
# 계산 값을 가장 작게 만들기 위해서는 각 배열을 오름차순, 내림차순 해준다.
arrA.sort()
arrB.sort(reverse=True)
res = 0

for x in range(n):
    res += arrA[x]*arrB[x]

print(res)

그리디 문제 - 8980번 택배

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

# 트럭 한 대로 배송할 수 있는 최대 박스 수 출력
N, C = map(int, input().split())  # 마을의 수, 트럭 용량
M = int(input())  # 박스 정보 개수
info = []
res = 0

for _ in range(M):
    # 박스를 보내는 마을, 박스를 받는 마을, 보내는 박스의 개수
    from_box, to_box, num_box = map(int, input().split())
    info.append((from_box, to_box, num_box))

sort_info = sorted(info, key=lambda x: x[1]) # 가장 빨리 받는 순서대로 정렬
remain = [0] * (N+1) # 남은 상자

for item in sort_info:
    start, end, box = item[0], item[1], item[2]
    max_box = box
    for i in range(start, end): # 시작점부터 도착지까지 보낼 수 있는 박스 개수
        max_box = min(max_box, C - remain[i])
    # print(max_box, C-remain[i])
    for j in range(start, end):
        remain[j] += max_box
    res += max_box
print(res)

https://hhiyeon.tistory.com/252

https://hhiyeon.tistory.com/253

https://hhiyeon.tistory.com/254

https://hhiyeon.tistory.com/255

이분 탐색(binary search)

• 순차 탐색 O(n)의 시간 복잡도를 O(logn)으로 줄일 수 있다.
• 오름차순으로 정렬된 정수의 리스트에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 좁혀가면서 탐색하는 방법

이분 탐색 문제 - 1920번 수 찾기 

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

n = 5
a = [4, 1, 5, 2, 3]
m = 5
b = [1, 3, 7, 9, 5]
a = sorted(a)
maxVal = a[-1] # 최대값

for element in b:
    lt = 0
    rt = n - 1
    res = 0

	# 최대값보다 구해야하는 수가 작은 경우만 이분 탐색
    if maxVal >= element:
        while lt <= rt:
            mid = (lt + rt) // 2
            print(element, lt, rt, mid, a[mid], res)
            if a[mid] == element:
                res = 1
                break
            elif a[mid] < element:
                lt = mid +1
            else:
                rt = mid -1
    print(res)

이분 탐색 문제 - 1654번 랜선 자르기

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

# k, n = 4, 11  # 이미 가지고 있는 랜선 개수, 필요한 랜선 개수 n
# kArr = [802, 743, 457, 539] # 랜선은 길이가 모두 다르다.
k, n = map(int, input().split())
kArr = []

for i in range(k):
    kArr.append(int(input()))
kArr = sorted(kArr) # 이분 탐색을 위한 정렬
lt = 0
rt = kArr[-1]
maxLen = 0

while lt <= rt:
    mid = (lt+rt)//2
    total = 0
    for size in kArr: # 구할 수 있는 랜선 개수 구하기
        total += (size//mid)

    if total >= n: # 랜선의 개수가 더 많을 경우
        maxLen = max(maxLen, mid) # 최대값 갱신
        lt = mid +1
    else:
        rt = mid -1 # 랜선의 개수가 부족할 경우 
print(maxLen)

이분 탐색 문제 - 2110번 공유기 설치

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

import sys

n, c = map(int, sys.stdin.readline().split())  # 집의 개수, 공유기 개수
x_arr = []

for _ in range(n):
    x = int(sys.stdin.readline())  # 집의 좌표
    x_arr.append(x)

x_arr.sort()

res = 0
start = 1  # 최소 거리 1
end = x_arr[-1] - x_arr[0]  # 최대 거리 = 가장 먼거리

while start <= end:
    mid = (start + end) // 2  # 중간값 = 현재 가능한 공유기 사이의 거리
    temp = x_arr[0]  # 이전 집의 좌표
    cnt = 1

    for i in range(1, n):
        if x_arr[i] - temp >= mid:  # 가능한 거리(mid) 이상으로 공유기를 설치할 수 있는 집에 공유기 설치
            cnt += 1
            temp = x_arr[i]

    if cnt >= c:  # c개 이상의 공유기를 설치할 수 있는지 확인
        start = mid + 1  # 가능하면 mid 증가
        res = mid
    else:
        end = mid - 1  # 불가능하면 mid 감소

print(res)

LIS 알고리즘

• 최장 증가 부분 수열
• 일반적으로 DP(동적 계획법)으로 푸는 알고리즘
• 임의의 수열이 주어질 때, 이 숭려에서 몇 개의 수들을 제거해서 부분 수열을 만든다.
• 이 때 부분수열들을 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다.

예시 코드

• 아래의 배열이 주어졌을 때

arr = [3,5,7,9,2,1,4,8]

• 아래처럼 부분 수열을 만들 수 있다.
• 이 중에 3,5,7,8이 LIS

arr = [3,7,9,1,4,8]
arr = [7,9,1,8]
arr = [3,5,7,8]
arr = [1,4,8]

일반적인 DP 풀이 방법 - O(n^2)

dp = [1]*n
for i in range(n):
	for j in range(i):
    	if arr[i] > arr[j]:
    		dp[i] = max(dp[i], dp[j]+1)

이분 탐색 이용 - O(nlogn)

# 수열 A가 주어질 때, 가장 긴 증가하는 부분 수열 구하기
n = 6
arr = [10,20,10,30,20,50]
lis = [0]

for case in arr:
    if lis[-1] < case:
        lis.append(case)
    else:
        left = 0
        right = len(lis)

        while left < right:
            mid = (left+right)//2
            if lis[mid] < case:
                left = mid + 1
            else:
                right = mid
        lis[right] = case
print(lis[1:])

백준 풀이 코드

https://hhiyeon.tistory.com/168

https://hhiyeon.tistory.com/166

완전탐색

- 모든 경우의 수를 계산하는 방법

백트래킹

- 주어진 문제에서 답을 구하기 위해 가능한 경우의 수를 탐색하는 방법

- 해를 찾는 도중에 찾는 해가 아닌 경우 되돌아가서 해를 찾는다.

백트래킹 문제 

1. N과 M(1) 15649번

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

n, m = 4, 2
#n, m = map(int, input().split())
s = [] # 수열을 저장하는 리스트

def dfs():
    if len(s) == m: # 리스트의 길이가 m개인 경우
        print(' '.join(map(str, s))) # 리스트의 모든 숫자들을 출력
        return 
    for i in range(1, n+1): # 1부터 n+1
        if i not in s: # 리스트 안에 i(1~4) 가 없으면 
            s.append(i) # 리스트에 i(1~4) 추가
            dfs() # 다음 레벨
            s.pop() # 마지막으로 넣었던 i 제거
dfs()



n, m = 4,2
stack = []

def dfs(start):
    if len(stack) == m:
        # print(stack)
        print(' '.join(map(str, stack)))
        return 
    for x in range(1, n+1):
        if x not in stack:
            stack.append(x)
            dfs(start+1)
            stack.pop()
dfs(1)

3. N과 M(3) 15650번

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

n, m = map(int, input().split())
stack = []

def dfs(start):
    if len(stack) == m:
        print(' '.join(map(str, stack)))
        return
    else:
        for x in range(start, n+1):
            if x not in stack:
                stack.append(x)
                #print(stack)
                dfs(x+1)
                stack.pop()
dfs(1)

3. N과 M(3) 15651번

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

# n, m = map(int, input().split())
n, m = 4,2 
stack = []

def dfs():
    if m == len(stack):
        print(' '.join(map(str, stack)))
        return
    for x in range(1, n+1):
        stack.append(x)
        dfs()
        stack.pop()
dfs()

4. N과 M(4) 15652번

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

#n, m = map(int, input().split())
s = [] 

def dfs(start):
    if len(s) == m: # 리스트의 길이가 m개인 경우
        print(' '.join(map(str, s))) # 리스트의 모든 숫자들을 출력
        return 
    for i in range(start, n+1): # start으로 1,1 2,2, 3,3
        s.append(i) # 리스트에 i(1~4) 추가
        dfs(i) # 다음 레벨
        s.pop() # 마지막으로 넣었던 i 제거
dfs(1)

5. N과 M(5) 15654번

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

n, m = map(int, input().split())
# n, m = 4, 2 # n개의 수를 입력받고, m개의 중복없는 수열을 구하기
# arr = [9,8,7,1]
arr = list(map(int, input().split()))
arr = sorted(arr) # 사전순 출력
stack = []

def dfs():
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return
    for x in range(0, n):
        if x not in stack:
            stack.append(x)
            dfs()
            stack.pop()
dfs()

6. N과 M(6) 15655번

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

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 4
arr = [1231, 1232, 1233, 1234]
arr = sorted(arr)
stack = []

def dfs(start):
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return
    for x in range(start, n):
        if x not in stack:
            stack.append(x)
            dfs(x+1)
            stack.pop()
dfs(0)

7. N과 M(7) 15656번

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

n, m = map(int, input().split())
arr = list(map(int, input().split()))
#n, m = 4, 2
#arr = [9,8,7,1]
arr = sorted(arr) # 사전순 출력
stack = []

def dfs(start):
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return

    for x in range(0, n):
        # 중복 상관 X
        stack.append(x)
        dfs(start+1)
        stack.pop()

dfs(0)

8. N과 M(8) 15657번

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

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))

n, m = 4, 2
arr = [9,8,7,1]
arr = sorted(arr)
stack = []

def dfs(start):
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return
    
    for x in range(start, n):
        stack.append(x)
        dfs(x)
        stack.pop()
dfs(0)

9. N과 M(9) 

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

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))

n, m = 4, 2
arr = [9,7,9,1]
arr = sorted(arr)
visited = [False]*n # 사용한 원소 체크
stack = []
answer = []

def dfs(v):
    if len(stack) == m:
        answer.append(tuple(stack))
        return
    
    for x in range(0, n):
        if visited[x]:
            continue
        stack.append(arr[x])
        visited[x] = True # 사용
        dfs(v+1)
        visited[x] = False # 사용끝
        stack.pop() 
dfs(0)

# 오름차순, set 중복제거
for x in sorted(list(set(answer))):
    print(*x) # 튜플 출력

10. N과 M(10) 15664번

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

n, m = map(int, input().split())
arr = list(map(int, input().split()))
#n, m = 4,2
#arr = [999,1,23,5]
#arr = [9,7,9,1]
arr = sorted(arr) # 오름차순
stack = []

def dfs(v):
    if len(stack) == m:
        print(stack)
        return

    prev = 0
    for x in range(v, n):
        if prev != arr[x]:
            stack.append(arr[x])
            prev = arr[x]
            dfs(x+1)
            stack.pop()
dfs(0)

11. N과 M(11) 15665번

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

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)
stack = []

def dfs():
    if len(stack) == m:
        print(*stack)
        return
    prev = 0
    for x in range(0, n):
        if prev != arr[x]:
            stack.append(arr[x])
            prev = arr[x]
            dfs()
            stack.pop()
dfs()

12. N과 M(12) 15666번

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

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 2
arr = [9,7,9,1]
arr = sorted(arr)
stack =[]

def dfs(v):
    if len(stack) == m:
        print(*stack)
        return
    prev = 0
    for x in range(v, n):
        if prev != arr[x]:
            stack.append(arr[x])
            prev = arr[x]
            dfs(x)
            stack.pop()
dfs(0)

6603번 로또

def dfs(stack, numbers, start, k):
    if len(stack) == 6:
        print(' '.join(map(str, stack)))
        return
    for x in range(start, len(numbers)):
        dfs(stack + [numbers[x]], numbers, x + 1, k)


while True:
    num = list(map(int, input().split()))
    if num[0] == 0:
        break

    k = num[0]  # 번호 개수
    numbers = sorted(num[1:])  # 번호 리스트

    visited = [False] * len(numbers)
    dfs([], numbers, 0, k)
    print()

1182번 부분수열의합

n, s = map(int, input().split())  # 정수의 개수, 정수 S
numbers = list(map(int, input().split()))

# n, s = 5, 0
# numbers = [-7, -3, -2, 5, 8]
cnt = 0


# 크기가 양수인 부분 수열 중에서 다 더한 값이 S인 경우의 수 구하기

def dfs(idx, cost):
    global cnt
    if idx >= n:  # 인덱스가 정수 개수보다 크면 종료
        return
    cost += numbers[idx]  # 더한값 += 현재 값
    if cost == s:  # 더한 값이 s면 경우의수 + 1
        cnt += 1
    dfs(idx + 1, cost)  # 현재 원소를 포함하는 경우
    dfs(idx + 1, cost - numbers[idx])  # 현재 원소를 포함하지 않는 경우


dfs(0, 0)
print(cnt)

9663번 N-Queen

def adjacent(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True


def dfs(x):
    global result

    if x == n:
        result += 1
        return
    for i in range(n):
        if visite[i]:
            continue
        row[x] = i
        if adjacent(x):
            visite[i] = True
            dfs(x + 1)
            visite[i] = False

import sys

# n = int(sys.stdin.readline())
n = 8  # n x n 크기의 체스판
row = [0] * n
visite = [False] * n
result = 0
dfs(0)
print(result)