찾아보니 jsonify를 사용해서 나타나는 오류였다 간단하게 두 가지 해결법이 있다. (내가 아는 것)

1. JSON Viewer 설치

이건 코드 수정이 필요없는 초간단 해결법이다.

나는 프론트쪽에서 말하기 전까지는 이 오류가 발생하는지 몰랐는데, 그 이유는 크롬 확장자로 JSON Viewer가 설치되어 있었기 때문이다. 이 뷰어가 설치되어 있으면 브라우저에서 제대로 나타나는 것 같다. 그래서 내 컴퓨터에선 한글이 제대로 출력되는데 왜 저쪽에서 깨진다고 하지? 싶어서 처음엔 내 잘못이 아닌줄 알았다.

JSON Viewer 설치 링크

이걸 설치하면 이런 지저분한 화면이 아닌, 이런 깔끔하고 정리된 화면을 브라우저에서 볼 수 있다.

json 파일 특성상 대부분 길고 지저분하게 생겨서 그냥 보면 불편하기 때문에 이 확장자를 설치하면 훨씬 가독성 있게 코드를 확인할 수 있어서 좋다.

그리고 프론트 측에서도 이 확장자를 설치하니 데이터가 한글로 올바르게 받아와진다고 했다. 굿굿

그러나 더 근본적인 방법은 다음과 같다.

2. json_dumps 사용

jsonify를 json_dumps로 바꾸는 것이다.

예시는 다음과 같다.

<변경 전>

    op_json = jsonify({'emotion': e_arr, 'percent': p_arr})

<변경 후>

    output_json = json.dumps({'emotion': e_arr, 'percent': p_arr}, ensure_ascii = False)

주의할 점은 뒤에

ensure_ascii = False

이 코드를 꼭 넣어줘야한다는 점이다

ERROR: Can not perform a '--user' install. User site-packages are not visible in this virtualenv.

이 에러창이 계속 떴다. 몇 가지 방법을 시도했지만 잘 안되어서 화가 났었다.

해결법은 간단했다 가상환경을 삭제하고, 다시 설치하니 된다!

윈도우 명령어는 다음과 같다

rmdir /s venv

local 환경에 gcloud를 설치하고 google cloud console에서 발급받은 json 키 파일을 저장해 GOOGLE_APPLICATION_CREDENTIALS="key.json" 형식으로 환경변수로 설정해 프로젝트를 진행하고 있었다. (speech-to-text(stt) api 사용 중)

ec2로 서버를 구축해 ubuntu 환경을 이용해 배포해보니

The Application Default Credentials are not available.
They are available if running in Google Compute Engine. 
Otherwise, the environment variable GOOGLE_APPLICATION_CREDENTIALS 
must be defined pointing to a file defining the credentials. 

이런 오류가 발생했다. 해석하기 귀찮아서 chatgpt한테 물어보니 이런 문제고,

이렇게 해결하면 된다고 했다

key.json 파일을 ec2 서버에 옮기고 환경변수 설정을 했다. ubuntu에서는 export 명령어를 사용해 환경변수를 설정한다고 한다.

export GOOGLE_APPLICATION_CREDENTIALS=/path/key.json

이렇게 챗지피티가 시키는대로 했지만 여전히 동작하지 않았다.

다른 블로그에서 ubuntu 환경변수 설정법을 다시 찾아봤다 cd ~ -> ec2의 제일 상단 폴더로 이동 sudo vi /etc/profile -> vi 편집기 접근 export 환경변수명=값 -> 환경변수 설정 source /etc/profile -> 환경변수 영구적용 echo $환경변수명 -> 환경변수 확인

이 설정을 했는데도 여전히 동작하지 않았다. 그런데 생각해보니 로컬에서 사용했을 때처럼 ubuntu에도 google cloud cli를 설치하면 될 것 같았다. 너무 쉬운 해결법이었는데 놓치고 있었다..

https://cloud.google.com/sdk/docs/install-sdk?hl=ko#rpm 이 문서를 확인해서 시키는대로만 하면 된다.

참고로 나는 amazon-linux 를 사용중이기에 Red Hat 환경이다. 다음과 같은 순서로 수행했다.

1. 무슨 말인지는 모르겠지만 일단 해당 명령어를 작성했다. gcloud CLI 저장소 정보로 DNF를 업데이트합니다. 다음 샘플 명령어는 Red Hat Enterprise Linux 8 호환 설치용입니다. Red Hat Enterprise Linux 7 호환 설치의 경우 baseUrl 값에서 el8을 el7로 바꿉니다.

sudo tee -a /etc/yum.repos.d/google-cloud-sdk.repo << EOM
[google-cloud-cli]
name=Google Cloud CLI
baseurl=https://packages.cloud.google.com/yum/repos/cloud-sdk-el8-x86_64
enabled=1
gpgcheck=1
repo_gpgcheck=0
gpgkey=https://packages.cloud.google.com/yum/doc/rpm-package-key.gpg
EOM

2. glcoud CLI 설치

sudo dnf install google-cloud-cli

공식 문서에는 이렇게 되어있으나 내 환경에서는 dnf가 작동하지 않았다. dnf를 yum으로 수정했다.

sudo yum install google-cloud-cli

3. google init을 실행해 시작

gcloud init

이렇게 하면 cmd창에 로그인 링크가 뜬다. ctrl+insert로 복사해 크롬 브라우저에 붙여넣기 한 후 구글 계정을 로그인한다. 로그인하면 인증 키를 주는데, 이걸 또 복사해 cmd 창에 shift+insert로 붙여넣기한다. 그러면 인증이 완료된다.

그리고 진행할 프로젝트를 숫자로 선택하면 끝!

도메인이 아닌 서버에서 동작하는 걸 드디어 확인할 수 있었다.. 정말 다행 ❤️❤️❤️🤓🤓🤓 원래 구글링하고 해결하면 그냥 넘어가는데, 나중에 내가 또 헷갈릴 수도 있고 이 문제의 경우 해결법이 구글링으로 안나왔어서 다른 사람들을 위해 기록한다. 다음에 좀 더 이쁘게 정리해야지.

- 문제📝

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

- 코드💻

from collections import deque
INF = 1e9 # 무한을 의미하는 값으로 10억을 설정

# 맵의 크기 N 입력
n = int(input())

# 전체 모든 칸에 대한 정보 입력
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 아기 상어의 현재 크기 변수와 현재 위치 변수
now_size = 2
now_x, now_y = 0, 0

# 아기 상어의 시작 위치를 찾은 뒤에 그 위치엔 아무것도 없다고 처리
for i in range(n):
    for j in range(n):
        if array[i][j] == 9:
            now_x, now_y = i, j
            array[now_x][now_y] = 0

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 모든 위치까지의 '최단 거리만' 계산하는 BFS 함수
def bfs():
    # 값이 -1이라면 도달할 수 없다는 의미 (초기화)
    dist = [[-1] * n for _ in range(n)]
    # 시작 위치는 도달이 가능하다고 보며 거리는 0
    q = deque([(now_x, now_y)])
    dist[now_x][now_y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < n and 0 <= ny and ny < n:
                # 자신의 크기보다 작거나 같은 경우에 지나갈 수 있음
                if dist[nx][ny] == -1 and array[nx][ny] <= now_size:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
    # 모든 위치까지의 최단 거리 테이블 반환
    return dist

# 최단 거리 테이블이 주어졌을 때, 먹을 물고기를 찾는 함수
def find(dist):
    x, y = 0, 0
    min_dist = INF
    for i in range(n):
        for j in range(n):
            # 도달이 가능하면서 먹을 수 있는 물고기일 때
            if dist[i][j] != -1 and 1 <= array[i][j] and array[i][j] < now_size:
                # 가장 가까운 물고기 한 마리만 선택
                if dist[i][j] < min_dist:
                    x, y = i, j
                    min_dist = dist[i][j]
    if min_dist == INF: # 먹을 수 있는 물고기가 없는 경우
        return None
    else:
        return x, y, min_dist # 먹을 물고기의 위치와 최단 거리

result = 0 # 최종 답안
ate = 0 # 현재 크기에서 먹은 양

while True:
    # 먹을 수 있는 물고기의 위치 찾기
    value = find(bfs())
    # 먹을 수 있는 물고기가 없는 경우, 현재까지 움직인 거리 출력
    if value == None:
        print(result)
        break
    else:
        # 현재 위치 갱신 및 이동 거리 변경
        now_x, now_y = value[0], value[1]
        result += value[2]
        # 먹은 위치에는 이제 아무것도 없도록 처리
        array[now_x][now_y] = 0
        ate += 1
        # 자신의 현재 크기 이상으로 먹은 경우, 크기 증가
        if ate >= now_size:
            now_size += 1
            ate = 0

- 비교 분석📖

아기 상어는 먹을 수 있는 물고기 중에서 가장 가까운 물고기를 먼저 먹는다고 했다. 가장 가까운 물고기는 최단 거리 알고리즘을 이용해서 찾을 수 있다. 현재 상어는 전체 N X N 공간에서 상, 하, 좌, 우 위치로 이동이 가능하므로 5장 'DFS/BFS'에서 다룬 '미로 탈출'문제와 유사하게 BFS를 이용하여 최단 거리를 찾으면 효과적이다.

따라서 매번 현재 위치에서 도달 가능한 다른 위치까지의 최단 거리를 구한 뒤에, 먹을 물고기의 위치를 찾는 과정을 반복하도록 하자. 다만, 문제에서는 '자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다', '자신의 크기보다 작은 물고기만 먹을 수 있다'와 같은 실수하기 쉬운 세부 조건이 있으므로, 구현 과정에서 실수가 없도록 각별한 주의가 필요하다.

핵심 아이디어는 BFS를 이용하여 최단 거리를 구하는 것이고, 세부 조건을 잘 이해해 구현 실수만 피한다면 정답 판정을 받을 수 있다. 본 코드에서는 세부 기능을 함수 여러 개로 나누어서 가독성을 높이고자 하였다.

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책을 기반으로 작성한 글입니다.

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

코드💻

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i+1))

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재 음식 시간 + 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]

비교 분석📖

분명히 복습까지 했던 문제로 기억하는데 우선순위 큐로 해결하는 것임을 파악하지 못했다. 이상한 방법으로 빙빙 돌려 풀고 있었다. 다른 일들로 알고리즘 공부에 몇 주 소홀했더니 바로 티가 나는 것 같다.. 그리디 알고리즘 관련 문제이다. 문제를 이해하는 것이 역시나 어려웠지만 그래도 우선순위 큐에 대한 코드를 몇 번 작성했어서 그런지 코드를 보고 이해할 수 있었다.

- 정의

- 자료구조

- 동작 과정

- 연결성

- 코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

- 문제점

👩‍🏫 서로소 집합 자료구조(개선)

- 경로 압축

- 코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')
© 2021 GitHub, Inc.

👩‍🏫 사이클 판별

- 동작 과정

- 코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

cycle = False # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 이코테 유튜브 강의 영상을 기반으로 작성한 글입니다.

- 문제

- 코드💻

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n, m = map(int, input().split())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # A와 B가 서로에게 가는 비용은 1이라고 설정
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
x, k = map(int, input().split())

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

# 도달할 수 없는 경우, -1을 출력
if distance >= 1e9:
    print("-1")
# 도달할 수 있다면, 최단 거리를 출력
else:
    print(distance)

- 해설📖

전형적인 플로이드 워셜 알고리즘 문제이다. 현재 문제에서 N의 범위가 100 이하로 매우 한정적이다. 따라서 플로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있기 때문에, 구현이 간단한 플로이드 워셜 알고리즘을 이용하는 것이 유리하다.

이 문제의 핵심 아이디어는 1번 노드에서 X를 거쳐 K로 가는 최단거리는 (1번 노드에서 X까지의 최단거리 + X에서 K까지의 최단거리)라는 점이다.

📝문제2. 전보

- 문제

- 코드💻

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수, 시작 노드를 입력받기
n, m, start = map(int, input().split())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    x, y, z = map(int, input().split())
    # X번 노드에서 Y번 노드로 가는 비용이 Z라는 의미
    graph[x].append((y, z))

def dijkstra(start):
   q = []
   # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
   heapq.heappush(q, (0, start))
   distance[start] = 0
   while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
    # 도달할 수 있는 노드인 경우
    if d != 1e9:
        count += 1
        max_distance = max(max_distance, d)

# 시작 노드는 제외해야 하므로 count - 1을 출력
print(count - 1, max_distance)

- 해설📖

한 도시에서 다른 도시까지의 최단 거리 문제로 치환할 수 있으므로 다익스트라 알고리즘을 이용해서 풀 수 있다. 또한 N과 M의 범위가 충분히 크기 때문에, 우선순위 큐를 이용하여 다익스트라 알고리즘을 작성해야 한다. 결과적으로 앞서 다루었던 다익스트라 알고리즘의 소스코드에서 마지막 부분만 조금 수정하여 답안 코드를 만들 수 있다.

모든 내용은 '이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 유튜브 강의를 기반으로 작성한 글입니다.

👩‍🏫다익스트라 알고리즘

- 동작 과정

- 특징

- 코드

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

- 성능 분석

👩‍🏫우선순위 큐

- 힙(Heap)

👩‍🏫다익스트라 알고리즘(개선)

- 동작 과정

- 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

- 성능 분석

👩‍🏫플로이드 워셜 알고리즘

- 동작 과정

- 코드

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

- 성능 분석

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 이코테 유튜브 강의 영상을 기반으로 작성한 글입니다.

- 문제

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

- 코드💻

n = int(input()) 
t = [] 
p = [] 
dp = [0] * (n+1)
max_value = 0

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)

for i in range(n-1, -1, -1):
    time = t[i] + i
    if time <= n:
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
    else:
        dp[i] = max_value

print(max_value)

- 해설📖

https://velog.io/@ji-vvon/06-3.-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4#--%ED%95%B4%EC%84%A4-2

📝문제2. 백준 18353번(병사 배치하기)

- 문제

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

- 코드💻

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

dp = [1] * n
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))

- 해설📖

https://velog.io/@ji-vvon/06-4.-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4#--%ED%95%B4%EC%84%A4-1

📝문제3. 금광

- 문제

- 코드💻

def maxGold(arr, x, y):

    for j in range(1, y):
        for i in range(x):
            if i == 0:
                left_top = 0
            else:
                left_top = arr[i-1][j-1]
            if i == x-1:
                left_btm = 0
            else:
                left_btm = arr[i+1][j-1]
            left = arr[i][j-1]
            arr[i][j] = max(left_top, left, left_btm)+arr[i][j]

    finals=[]
    for i in range(x):
        finals.append(arr[i][y-1])
    return max(finals)

t = int(input())

for _ in range(t):
    n,m = map(int, input().split())
    arr=[]
    temp = list(map(int, input().split()))
    for i in range(0, len(temp), m):
        arr.append(list(temp[i:i+m]))
    print(maxGold(arr,n,m))

📝문제4. 편집 거리 문제

- 문제

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

- 코드💻

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

- 해설📖

📝문제2. 백준 1149번(RGB거리)

- 문제

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

- 코드💻

import sys
input = sys.stdin.readline 
n = int(input())

array = [[0 for _ in range(3)] for __ in range(n)]  # 3xn 배열
table = [[0 for _ in range(3)] for __ in range(n)]  # 3xn 배열

for i in range(n):
    array[i][0], array[i][1], array[i][2] = list(map(int, input().split()))
table[0] = array[0]

for i in range(n):
    table[i][0] = min(table[i - 1][1], table[i - 1][2]) + array[i][0]
    table[i][1] = min(table[i - 1][0], table[i - 1][2]) + array[i][1]
    table[i][2] = min(table[i - 1][0], table[i - 1][1]) + array[i][2]
min_cost = min(table[n - 1][0], table[n - 1][1], table[n - 1][2])

print(min_cost)

- 해설📖

참고 블로그 : https://cotak.tistory.com/11 https://seungjuitmemo.tistory.com/29

📝문제3. 백준 2156번(포도주 시식)

- 문제

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

- 코드💻

n = int(input())
wine_list = [int(input()) for x in range(n)]

dp = [0]
dp.append(wine_list[0])
if(n > 1):
    dp.append(wine_list[0] + wine_list[1])

# 연속 3잔을 마시지 않아야 하므로
# 1 : 이번 포도주를 먹고 이전 포도주를 먹지 않은 경우
# 2 : 이번 포도주를 먹고 이전 포도주도 먹은 경우
# 3 : 이번 포도주를 먹지 않아야 하는 경우
# 위 세가지 경우를 고려하여 max

for i in range(3, n + 1):
    # wine_list는 0부터 시작하므로 i - 1로 해준다.
    case_1 = wine_list[i - 1] + dp[i - 2]
    case_2 = wine_list[i - 1] + wine_list[i - 2] + dp[i - 3]
    case_3 = dp[i - 1]
    max_value = max(case_1, case_2, case_3)

    dp.append(max_value)

print(dp[n])

- 해설📖

참고 블로그 : https://hwiyong.tistory.com/257

- 문제

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

- 코드💻

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 가장 긴 증가하는 부분 수열 문제로 변환
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 dp 테이블 초기화
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))

- 해설📖

이 문제의 기본 아이디어는 '가장 긴 증가하는 부분 수열(LIS)'로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다. '가장 긴 증가하는 부분 수열' 문제란, 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다.

예를 들어 하나의 수열 array = {10, 20, 10, 30, 20 , 50}가 있다고 하자. 이때 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50}이 될 것이다. 'D[i] = array[i]'를 마지막 원소로 가지는 부분 수열의 최대 길이'라고 정의 하면, 가장 긴 증가하는 부분 수열을 계산하는 점화식은 다음과 같다. 이때 dp 테이블의 값은 모두 1로 초기화한다.

*모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i] *

최종적으로 테이블의 값은 [1, 2, 1, 3, 2, 4]이고, 이렇게 테이블에 남아 있는 값 중에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이이다. 현재 예시에서는 4가 최장 길이가 된다.

현재의 문제는 병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치를 하고자 한다. 따라서 이 문제를 '가장 긴 감소하는 부분 수열'의 길이를 계산하는 문제로 간주하고, 입력으로 주어진 원소의 순서를 뒤집은 뒤에 '가장 긴 증가하는 부분 수열' 문제를 풀 때의 점화식을 그대로 적용하면 해결할 수 있다.

https://sigcho.tistory.com/123

-> LIS 라는 개념이 잘 이해가 가지 않는다..

📝문제2. 못생긴 수

- 문제

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... }순으로 이어지게 됩니다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다.

입력 조건

• 첫째 줄에 n이 입력됩니다. (1 <= n <= 1,000)

출력 조건

• n번째 못생긴 수를 출력합니다.

입력 예시1 10 출력 예시1 12

입력 예시2 4 출력 예시2 4

- 코드💻

n = int(input())

ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1

# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈 값을 초기화
next2, next3, next5 = 2, 3, 5

# 1부터 n까지의 못생긴 수들을 찾기
for l in range(1, n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2, next3, next5)
    # 인덱스에 따라서 곱셈 결과를 증가
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5

# n번째 못생긴 수를 출력
print(ugly[n - 1])

- 해설📖

이 문제는 가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,,,}와 같이 끊임없이 존재한다. 이때 못생긴 수에 2, 3 혹은 5를 곱한 수 또한 '못생긴 수'에 해당한다는 점이 포인트이다.

2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대하여 각각 '가장 작은 못생긴 수'부터 오름차순으로 하나씩 확인하면서, 각 배수를 곱한 값도 '못생긴 수'가 될 수 있도록 처리하면 정답 판정을 받을 수 있다.

예를 들어 먼저 못생긴 수로 1이 있다고 해보자. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

• 2의 배수 : 1 x 2 = 2
• 3의 배수 : 1 x 3 = 3
• 5의 배수 : 1 x 5 = 5

이로써 우리는 새롭게 2, 3, 5 또한 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 5}가 된다.

첫 번째로 못생긴 수인 1에 이어서 그다음으로 못생긴 수는 2가 된다. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

• 2의 배수 : 2 x 2 = 4
• 3의 배수 : 2 x 3 = 6
• 5의 배수 : 2 x 5 = 10

이로써 우리는 4, 6, 10이 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 4, 6, 10}이 된다. 이렇게 못생긴 수들을 작은 수부터 차례대로 확인하면서, 각 못생긴 수에 대해서 2의 배수, 3의 배수, 5의 배수를 고려한다는 점을 기억하여 효율적으로 소스코드를 작성하면 다음과 같이 작성할 수 있다.

📝문제3. 편집 거리

- 문제

- 코드💻

str1 = "sunday"
str2 = "saturday"

n = len(str1)
m = len(str2)
dp = [[0] * (1+m) for _ in range(1+n)]
for i in range(1, n+1):
  dp[i][0] = i
for j in range(1, m+1):
  dp[0][j] = j
for i in range(1, n+1):
  for j in range(1, m+1):
    if str1[i-1] == str2[j-1]:
      dp[i][j] = dp[i-1][j-1]
    else:
      dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1

print(dp[n][m])

- 해설📖

1. https://bgspro.tistory.com/36
2. https://soooprmx.com/%ED%8E%B8%EC%A7%91%EA%B1%B0%EB%A6%AC-%EB%8B%A8%EC%96%B4%EC%9D%98-%EC%9C%A0%EC%82%AC%EB%8F%84-%EB%B6%84%EC%84%9D/
3. https://oboki.net/workspace/python/algorithm-edit-distance/

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 유튜브 강의를 기반으로 작성한 글입니다.

- 문제

- 코드💻

def maxGold(arr, x, y):

    for j in range(1, y):
        for i in range(x):
            if i == 0:
                left_top = 0
            else:
                left_top = arr[i-1][j-1]
            if i == x-1:
                left_btm = 0
            else:
                left_btm = arr[i+1][j-1]
            left = arr[i][j-1]
            arr[i][j] = max(left_top, left, left_btm)+arr[i][j]

    finals=[]
    for i in range(x):
        finals.append(arr[i][y-1])
    return max(finals)

t = int(input())

for _ in range(t):
    n,m = map(int, input().split())
    arr=[]
    temp = list(map(int, input().split()))
    for i in range(0, len(temp), m):
        arr.append(list(temp[i:i+m]))
    print(maxGold(arr,n,m))

- 해설📖

1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우

이 경우 중 가장 많은 금을 가지고 있는 경우를 테이블에 저장해주어 문제를 해결할 수 있다.

참고 블로그 https://velog.io/@keroro3030/%EC%9D%B4%EA%B2%83%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4-Q31.%EA%B8%88%EA%B4%91-%ED%8C%8C%EC%9D%B4%EC%8D%ACDP

📝문제2. 백준 1932번(정수 삼각형)

- 문제

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

- 코드💻

from sys import stdin
n = int(stdin.readline())
dp = []
for _ in range(n):
    dp.append(list(map(int, stdin.readline().split())))

for i in range(1, n):
    for j in range(i+1):
        # 왼쪽 위에서 내려오는 경우
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i-1][j-1]
        # 바로 위에서 내려오는 경우
        if j == i:
            up = 0
        else:
            up = dp[i-1][j]
        # 최대 합을 저장
        dp[i][j] = dp[i][j] + max(up_left, up)

print(max(dp[n-1]))

- 해설📖

책에 있는 코드인데 개인적으로는 https://jiwon-coding.tistory.com/120 이 블로그에 있는 코드가 좀 더 이해하기 쉬웠던 것 같다.

📝문제3. 백준 14501번(퇴사)

- 문제

https://www.acmicpc.net/problem/14501 굉장히 자본주의적인 문제인듯..

- 코드💻

n = int(input()) # 전체 상담 개수
t = [] # 각 상담 소요 기간
p = [] # 각 상담 금액
dp = [0] * (n+1)
max_value = 0

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1):
    time = t[i] + i
    # 상담이 기간 안에 끝나는 경우
    if time <= n:
        # 점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value

print(max_value)

- 해설📖

뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다. 즉, 뒤쪽부터 매 상담에 대하여 '현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i])'을 계산하면 된다. 이후 계산된 각각의 값 중에서 최댓값을 출력하면 된다.

dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익 이라고 하면 점화식은 dp[i] = max(p[i] + dp[t[i] + i], max_value)가 된다. 이때 max_value는 뒤에서부터 계산할 때 현재까지의 최대 상담 ㄱ므액에 해당하는 변수이다.

모든 내용은 '이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 유튜브 강의를 기반으로 작성한 글입니다.

- 문제

정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

a. x가 5로 나누어떨어지면, 5로 나눈다.

b. X가 3으로 나누어 떨어지면, 3으로 나눈다.

c. X가 2로 나누어 떨어지면, 2로 나눈다.

d. X에서 1을 뺀다.

정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 이 연산을 사용하는 횟수의 최솟값을 출력하시오.

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

1. 26 - 1 = 25 (d)
2. 25 / 5 = 5 (a)
3. 5 / 5 = 1 (a)

입력 첫째 줄에 정수 X이 주어진다. (1<=X<=30,000) 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

입력 예시 26 출력 예시 3

- 나의 코드💻

from sys import stdin
x = int(stdin.readline())
count = 0

while x != 1:
    if x % 5 == 0:
        x = x // 5
        count += 1
    elif x % 3 == 0:
        x = x // 3
        count += 1
    elif x % 2 == 0:
        x = x // 2
        count += 1
    else:
        x -= 1
        count += 1

print(count)

-> 틀렸다. 너무 생각없이 작성한듯..

- 코드💻

from sys import stdin
x = int(stdin.readline())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 3001

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

print(d[x])

...

- 해설📖

• 다이나믹 프로그래밍 문제이다. (보텀업 방식, 피보나치와 비슷함)
• 보텀업 : 반복문을 이용해 작은 문제부터 차근차근 답을 도출
• 점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다.
• 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해서만 점화식을 적용할 수 있다. 더불어 두 수 중에서 단순히 더 작은 수를 구하고자 할 때는 파이썬의 min() 함수를 이용하면 간단하다.

이해가 잘 안가서 x = 6 인 경우를 가정해 코드 속 내용을 직접 작성해보았다.

[반복문] 1) i = 2 d[0], d[1] = 0, 0 d[2] = d[1] + 1 = 1 이다.

2는 2로 나누어 떨어지므로 d[2] = min(d[2], d[2//2]+1) = min(1, 1) = 1이 된다.

2) i = 3 d[3] = d[2] + 1 = 2 3은 3으로 나누어 떨어지므로 d[3] = min(d[3], d[3//3]+1) = min(2, 1) = 1이 된다.

3) i = 4 d[4] = d[3] + 1 = 2 4는 2, 3, 5로 나누어 떨어지지 않으므로 d[4] = 2이다.

4) i = 5 d[5] = d[4] + 1 = 3 5는 5로 나누어 떨어지므로 d[5] = min(d[5], d[5//5] + 1) = min(3, 1) = 1이 된다.

5) i = 6 d[6] = d[5] + 1 = 2 6은 2로 나누어 떨어지므로 d[6] = min(d[6], d[6//2] + 1) = min(d[6], d[3]+1) = min(2, 2) = 2 6은 3으로 나누어 떨어지므로 d[6] = min(d[6], d[6//3] + 1) = min(d[6], d[2]+1) = min(2, 2) = 2

-> x인 경우 답은 2가 된다.

📝문제2. 개미 전사

- 문제

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.

{1, 3, 1, 5}

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다.

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3<=N<=100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)

출력

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

입력 예시 4 1 3 1 5

출력 예시 8

- 코드💻

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])

- 해설📖

왼쪽부터 차례대로 식량 창고를 턴다고 가정하면 된다. 왼쪽부터 차례대로 식량창고를 털지 안 털지를 결정하는 경우와 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정할 때, 단 2가지 경우에 대해서만 확인하면 된다.

a. (i-1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없다. b. (i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다.

따라서 a와 b 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다.

여기서 알아둘 점은 왼쪽부터 (i-3)번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 왜냐하면 한 칸 이상 떨어진 식량창고는 항상 털 수 있기 때문이다.

📝문제3. 바닥 공사

- 문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000)

출력 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

입력 예시 3

출력 예시 5

- 코드💻

n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3
for i in range(3, n+1):
    d[i] = (d[i-1] + 2 * d[i-2]) % 796796

print(d[n])

- 해설📖

다이나믹 프로그래밍의 타일링 문제 유형이다. 다이나믹 프로그래밍에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가는데, 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다.

이 문제는 그림으로 그려 생각하면 어렵지 않게 풀 수 있다. 예를 들어 N이 3일 때 바닥을 덮기로 채울 수 있는 모든 경우의 수는 다음과 같다.

또한 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

1. 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
2. 왼쪽부터 i-2까지 길이가 덮개로 채워져 있으면 1x2덮개 2개를 넣는 경우, 혹은 2x2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다. 또한 이 문제 역시 왼쪽부터 N-2 미만의 길이에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2x2의 직사각형 형태이기 때문이다. 다시 말해 바닥을 채울 수 있는 형태는 위에서 언급한 경우밖에 없다.

📝문제4. 효율적인 화폐 구성

- 문제

- 코드💻

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

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

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

- 해설📖

내 생각엔 문제 해결 아이디어를 차근차근 떠올려보고 점화식을 세우는 것이 중요한 것 같다.

모든 내용은 '이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 유튜브 강의를 기반으로 작성한 글입니다.

-> '다이나믹' 프로그래밍 != '동적' 할당

- 다이나믹 프로그래밍의 조건

👩‍🏫 피보나치 수열

- 소스 코드

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

- 시간 복잡도

- 해법

- 메모리제이션(캐싱)

- 탑다운 VS 보텀업

- 소스 코드(탑다운)

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    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))

- 소스 코드(보텀업)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

- 동작 분석

- 시간 복잡도

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

- 다이나믹 프로그래밍 문제 접근법

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 이코테 유튜브 강의 영상을 기반으로 작성한 글입니다.

- 문제

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

- 코드💻

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 모든 단어를 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어를 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    for word in words: # 모든 단어를 접미사 와일드카드 배열, 접두사 와일드카드 배열에 각각 삽입
        array[len(word)].append(word)  # 단어를 삽입
        reversed_array[len(word)].append(word[::-1])  # 단어를 뒤집어서 삽입

    for i in range(10001): # 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
        array[i].sort()
        reversed_array[i].sort()

    for q in queries: # 쿼리를 하나씩 확인하며 처리
        if q[0] != '?':  #접미사에 와일드카드가 붙은 경우
            res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else: # 접두사에 와일드카드가 붙은 경우
            res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?','z'))
        # 검색된 단어의 개수를 저장
        answer.append(res)

    return answer

📝문제2. 백준 17266번(어두운 굴다리)

- 문제

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

- 코드💻

from sys import stdin
# n : 굴다리의 길이, m : 가로등의 개수, x : m개의 설치할 수 있는 가로등의 위치
n = int(stdin.readline())
m = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

# 가로등이 1개인 경우
if len(array) == 1:
    # 해당 가로등의 위치와 시작점, 끝점과의 두 거리 중 더 큰 값을 높이로 선정
    height = max(array[0] - 0, n - array[0])

# 가로등이 여러 개인 경우
else:
    # 초기 높이 : 시작점과 첫 가로등 사이의 거리
    height = array[0]
    for i in range(len(array)):
        # 끝에 가장 가까운 가로등이 비춰야 할 거리(?)
        if i == (len(array) - 1):
            tmp = n - array[-1]
        else:
            # 마주하는 가로등의 거리 (양 끝의 가로등 제외)
            a = array[i+1] - array[i]
            # 해당 거리를 2로 나눈 나머지가 홀수인 경우
            # 가로등의 높이가 1이 더 높아야만 사이의 모든 거리를 비출 수 있음
            if a % 2:
                tmp = a // 2 + 1
            # 해당 거리를 2로 나눈 나머지가 짝수인 경우
            else:
                tmp = a // 2
        height = max(height, tmp)

print(height)

📝문제3. 백준 13702번(이상한 술집)

- 문제

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

- 코드💻

from sys import stdin
n, k = map(int, stdin.readline().split())
array = []
for _ in range(n):
    array.append(int(stdin.readline()))
array.sort()

start, end = 0, max(array)
result = 0
while start <= end:
    mid = (start + end) // 2
    count = 0
    for x in array:
        a = x // mid
        count += a
    if count < k:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

새로운 문제를 풀기보다는 어려웠던 문제들을 다시 풀고 따라쳐보며 복습해봤다!

- 문제

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

- 나의 코드💻

import math
from sys import stdin
n = int(stdin.readline())
m = math.sqrt(n)
print(math.ceil(m))

- 비교 분석📖

이진 탐색으로 어떻게 풀어야할지 통 모르겠어서 구글에 math 라이브러리를 검색해서 풀었다.

https://jinho-study.tistory.com/689 이진 탐색으로 푼 코드이다. 근데 수학? 이라 그런지 그 코드가 자세히 이해가 가진 않는다.

📝문제2. 백준 13702번(이상한 술집)

- 문제

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

- 코드💻

from sys import stdin
# n : 주전자의 개수, k : 총 사람 수
n, k = map(int, stdin.readline().split())
array = []
for _ in range(n):
    array.append(int(stdin.readline()))
array.sort()

start, end = 0, max(array)
result = 0
while start <= end:
    mid = (start + end) // 2
    count = 0
    for x in array:
        a = x // mid
        count += a
    if count < k:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

- 비교 분석📖

파라메트릭 서치 문제 같아서 이전에 풀었던 파라메트릭 관련 문제들을 참고하면서 풀었다. 문제가 갑자기 헷갈려 중간에 막혔는데 이 블로그를 참고해서 풀어낼 수 있었다. https://blog.naver.com/kellygirl4028/222452314549

📝문제3. 백준 15732번(도토리 숨기기)

- 문제

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

- 코드💻

from sys import stdin
# n : 상자의 개수, k : 규칙의 개수, d : 도토리의 개수
n, k, d = map(int, stdin.readline().split())
array = []
for _ in range(k):
    array.append(list(map(int, stdin.readline().split())))

def dotori(pivot):
    total = 0
    for start, end, step in array:
        beta = min(end, pivot)
        if start <= beta:
            calc = (beta - start) // step + 1
            total += calc
    return total

def solution():
    lo, hi = 1, 1000000
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2

        if dotori(mid) >= d:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

print(solution())

- 비교 분석📖

https://handhand.tistory.com/178 참고 블로그

- 문제

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

- 나의 코드💻

from sys import stdin
# n : 지방의 수, m : 총 예산
n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
array.sort()

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        if x > mid:
            total += mid

    if total > m:
        end = mid - 1

    else:
        result = mid
        start = mid + 1

print(result)

- 정답 코드💻

from sys import stdin
# n : 지방의 수, m : 총 예산
n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
array.sort()

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0  # start : 가장 적은 금액 0
end = max(array)  # end : 가장 큰 금액 max(array)

while start <= end:
    total = 0 # 총 지출액
    mid = (start + end) // 2
    for x in array:
        total += min(mid, x)

    if total > m: # 지출액이 예산보다 크면
        end = mid - 1

    else: # 지출액이 예산보다 작으면
        start = mid + 1

print(end)

- 비교 분석📖

05-1 에서 했던 떡볶이떡 문제랑 비슷한 것 같아 그렇게 해보려고 했는데 잘 코드가 작성되지 않았다. 이런저런 블로그들을 참고하며 코드를 수정했는데 떡볶이떡 문제랑 흐름이 비슷한 것은 맞는 것 같다.

📝문제2. 백준 17266번(어두운 굴다리)

- 문제

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

- 나의 코드💻

코드를 입력하세요

공유기 설치 문제와 비슷한 것 같아 그런 식으로 풀어보려고 했는데 구체적인 구현이 잘 되지 않았다.

- 정답 코드💻

from sys import stdin
# n : 굴다리의 길이, m : 가로등의 개수, x : m개의 설치할 수 있는 가로등의 위치
n = int(stdin.readline())
m = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

# 가로등이 1개인 경우
if len(array) == 1:
    # 해당 가로등의 위치와 시작점, 끝점과의 두 거리 중 더 큰 값을 높이로 선정
    height = max(array[0] - 0, n - array[0])

# 가로등이 여러 개인 경우
else:
    # 초기 높이 : 시작점과 첫 가로등 사이의 거리
    height = array[0]
    for i in range(len(array)):
        # 끝에 가장 가까운 가로등이 비춰야 할 거리(?)
        if i == (len(array) - 1):
            tmp = n - array[-1]
        else:
            # 마주하는 가로등의 거리 (양 끝의 가로등 제외)
            a = array[i+1] - array[i]
            # 해당 거리를 2로 나눈 나머지가 홀수인 경우
            # 가로등의 높이가 1이 더 높아야만 사이의 모든 거리를 비출 수 있음
            if a % 2:
                tmp = a // 2 + 1
            # 해당 거리를 2로 나눈 나머지가 짝수인 경우
            else:
                tmp = a // 2
        height = max(height, tmp)

print(height)

- 비교 분석📖

참고 블로그 : https://velog.io/@meganatc7/%EB%B0%B1%EC%A4%80-17266.-%EC%96%B4%EB%91%90%EC%9A%B4-%EA%B5%B4%EB%8B%A4%EB%A6%AC

📝문제3. 백준 2613번(숫자구슬)

- 문제

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

- 나의 코드💻

코드를 입력하세요

- 정답 코드💻

코드를 입력하세요

- 비교 분석📖

https://develoger.kr/2613%EB%B2%88-%EC%88%AB%EC%9E%90%EA%B5%AC%EC%8A%AC/

이해하기 좀 어려운 문제같다..

- 문제

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

- 나의 코드💻

코드를 입력하세요

- 정답 코드💻

1. 블로그 참고

from sys import stdin
# n : 집의 개수 / c : 공유기의 개수
n, c = map(int, stdin.readline().split())
house = []
for _ in range(n):
    house.append(int(stdin.readline()))
house.sort()

# 해당 거리를 유지하며 공유기가 몇 개 설치될 수 있는가?
def router_counter(distance):
    count = 1
    cur_house = house[0]  # 시작점
    for i in range(1, n):  # 모든 집을 돈다
        if cur_house + distance <= house[i]: # 이전 집에서 해당거리보다 멀리 떨어진 집이라면
            count += 1
            cur_house = house[i]  # 공유기가 설치된 집 갱신
    return count

# start : 첫집, end : 첫집과 끝집의 차이
start, end = 1, house[-1] - house[0]

while start <= end:
    mid = (start + end) // 2

    if router_counter(mid) >= c:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1

print(answer)

-> 쉽게 설명이 되어 있는데 내가 아직 부족해서 그런지 뭔가 100프로 이해가 가지는 않는다. 그래서 책의 풀이를 참고했다. 출처 : https://claude-u.tistory.com/448

2. 이코테 책 예시 코드

   n, c = list(map(int, input().split()))
   array = []
   for _ in range(n):
    array.append(int(input()))
   array.sort()
   

start = array[1] - array[0] # 집의 좌표 중에 가장 작은 값 end = array[-1] - array[0] # 집의 좌표 중에 가장 큰 값 result = 0

while(start <= end): mid = (start + end) // 2 # mid는 가장 인접한 두 공유기 사이의 거리(gap)을 의미 value = array[0] count = 1 # 현재의 mid값을 이용해 공유기를 설치 for i in range(1, n): # 앞에서부터 차근차근 설치 if array[i] >= value + mid: value = array[i] count += 1 if count >= c: # c개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가 start = mid + 1 result = mid # 최적의 결과 저장 else: # c개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소 end = mid - 1

print(result)

### - 비교 분석📖
이 문제는 '가장 인접한 두 공유기 사이의 거리'의 최댓값을 탐색해야 하는 문제로 이해할 수 있다. 이때 각 집의 좌표가 최대 10억이므로 이진 탐색을 이용하면 문제를 해결할 수 있다. 따라서 이진 탐색으로 '가장 인접한 두 공유기 사이의 거리'를 조절해가며, 매 순간 실제로 공유기를 설치하여 c보다 많은 개수로 공유기를 설치할 수 있는지 체크하여 문제를 해결할 수 있다. 

다만, '가장 인접한 두 공유기 사이의 거리'의 최댓값을 찾아야 하므로, c보다 많은 개수로 공유기를 설치할 수 있다면 '가장 인접한 두 공유기 사이의 거리'의 값을 증가시켜서, 더 큰 값에 대해서도 성립하는지 체크하기 위해 다시 탐색을 수행한다. 이 문제는 '떡볶이 떡 만들기' 문제와 유사하게 이진 탐색을 이용해 해결할 수 있는 파라메트릭 서치 유형의 문제로 이해할 수 있다. 

예를 들어 5개의 집이 있고, 각 좌표를 담은 수열이 {1, 2, 4, 8, 9}와 같다고 해보자. 또한 설치할 공유기의 최소 개수 c = 3이라고 하자. 이때 가장 인접한 두 공유기 사이의 거리(gap)는 1부터 8까지의 수가 될 수 있다.

![](https://images.velog.io/images/ji-vvon/post/f4cbf4b3-6670-46a2-b75e-1b3b62eb8ee9/image.png)

**step1.** 범위가 1부터 8까지이므로, gap의 값을 중간에 해당되는 4로 설정한다. 다만, 이 경우, 공유기를 2개밖에 설치할 수 없다. 따라서 c = 3보다 작기 때문에, gap을 좀 더 줄일 필요가 있다. 따라서 범위가 [1, 8]이었으므로, 범위를 [1,3]으로 수정한다. (공유기를 앞에서부터 차례로 설치할 때, 공유기가 설치되는 위치는 하늘색으로 색칠하였다.)
![](https://images.velog.io/images/ji-vvon/post/1d19a942-7505-4343-9a5f-e253234fe251/image.png)

=> gap이 뭔지 잘 모르겠다.. gap이 4인데 왜 1이랑 8에 공유기가 설치되는 거지? gap이 공유기 사이의 거리라고 했는데 그럼 7 아닌가? 

**step2.** 범위가 1부터 3까지이므로, gap의 값을 중간에 해당하는 2로 설정한다. 이 경우, 공유기를 3개 설치하게 된다. 따라서 c = 3 이상의 값이기 때문에, 현재의 gap을 저장한 뒤에 gap의 값을 증가시켜서 gap이 더 커졌을 때도 가능한지 확인할 필요가 있다. 따라서 범위가 [1, 3]인 상태에서 범위를 [3,3]으로 수정한다. 
![](https://images.velog.io/images/ji-vvon/post/91cc7037-7ee8-494f-b8bb-9c8bed1fb953/image.png)

**step 3.** 범위가 3부터 3까지이므로, gap의 값을 중간에 해당하는 3으로 설정한다. 이 경우, 공유기를 3개 설치하게 된다. 따라서 c = 3 이상의 값이기 대문에, 현재의 gap을 저장한 뒤에 gap의 값을 증가시켜서 gap이 더 커졌을 때도 가능한지 확인할 필요가 있따. 하지만 현재 범위가 [3,3]이므로, 더이상 범위를 변경할 수 없다. 따라서 gap = 3이 최적의 경우이다.
![](https://images.velog.io/images/ji-vvon/post/8007e494-e50f-4948-aebf-183e98e4f300/image.png)


=> 이해해보려고 책 해설의 그림을 ppt로 옮겨봤는데 그래도 여전히 잘 모르겠다.. gap에 대한 이해가 잘 안간다. 나중에 다시 확인해야겠다. 머리가 안굴러가는 느낌..😥 조금만 어려워지면 문제들이 잘 이해가 가지 않는 것 같다.. 좀 더 머리를 굴려봐야겠다.

---

## 📝문제2. 프로그래머스 60060번(가사 검색)
### - 문제
https://programmers.co.kr/learn/courses/30/lessons/60060

### - 나의 코드💻
```python
코드를 입력하세요

- 정답 코드💻

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 모든 단어를 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어를 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    for word in words: # 모든 단어를 접미사 와일드카드 배열, 접두사 와일드카드 배열에 각각 삽입
        array[len(word)].append(word)  # 단어를 삽입
        reversed_array[len(word)].append(word[::-1])  # 단어를 뒤집어서 삽입

    for i in range(10001): # 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
        array[i].sort()
        reversed_array[i].sort()

    for q in queries: # 쿼리를 하나씩 확인하며 처리
        if q[0] != '?':  #접미사에 와일드카드가 붙은 경우
            res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else: # 접두사에 와일드카드가 붙은 경우
            res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?','z'))
        # 검색된 단어의 개수를 저장
        answer.append(res)

    return answer

- 비교 분석📖

먼저 각 단어를 길이에 따라서 나눈다. 이후에 모든 리스트를 정렬한 뒤에, 각 쿼리에 대해서 이진 탐색을 수행하여 문제를 해결할 수 있다. 예를 들어 문제의 예시와 같이 전체 단어가 ["frodo", "front", "frost", "frozen", "frame", "kakao"]로 구성되어 있다고 해보자. 이때 각각의 리스트를 길이에 따라서 나누면 다음과 같다.

• 길이가 5인 단어 리스트 : ["frodo", "front", "frost", "frame", "kakao"]
• 길이가 6인 단어 리스트 : ["frozen"]

이후에 각 리스트를 정렬하면 다음과 같다.

• 길이가 5인 단어 리스트 : ["frame", "frodo", "front", "frost", "kakao"]
• 길이가 6인 단어 리스트 : ["frozen"]

이때 "fro??"라는 쿼리가 들어왔다고 가정하면 "fro??"는 길이가 5이므로 길이가 5인 단어 리스트에서 "fro"로 시작되는 모든 단어를 찾으면 된다. 이때 구체적으로 이진탐색을 이용해서 "fro"로 시작되는 마지막 단어의 위치를 찾고, "fro"로 시작되는 첫 단어의 위치를 찾아서 그 위치의 차이를 계산하면 될 것이다. 이처럼 이진 탐색을 수행하는 경우 특정한 단어가 등장한 횟수를 계산할 수 있다.

혹은 "fro??"라는 쿼리가 들어왔을 때, count_by_range() 함수를 이용하여 "froaa"보다 크거나 같으면서 "frozz"보다 작거나 같은 단어의 개수를 세도록 구현하면 매우 간단하다. 이는 '정렬된 배열에서 특정 수의 개수 구하기' 문제와 유사한 접근 방법이다.

다만, 이 문제에서는 와일드카드 "?"가 접두사에서도 등장할 수 있다고 했다. 만약 "????o"라는 쿼리가 들어왔다고 가정해보자. 이는 기존의 리스트인 ["frame", "frodo", "front", "frost", "kakao"] 를 이용해 처리할 수 없을 것이다. 따라서 접두사에 와일드카드가 등장하는 것을 처리하기 위해 기존 단어를 뒤집은 단어를 담고 있는 리스트 또한 별도로 선언해야 한다. 현재 예시에서는 길이가 5인 뒤집힌 단어 리스트는 ["emarf", "oakak", "odorf", "tnorf", "tsorf"]이다. 결과적으로 접두사에 와일드카드가 등장하는 경우, 뒤집힌 단어 리스트를 대상으로 이진 탐색을 수행하면 된다.

=> 이코테 책의 해설 풀이를 그대로 옮겨적으며 이해했다. 이해는 가는데 이 생각을 어떻게 떠올릴 수 있는지 잘 모르겠다..

*참고 문법 replace : 문자열 변경 함수. 문자열 안에서 특정 문자를 새로운 문자로 변경. '변수. replace(old, new, [count])' 형식으로 사용.

• old : 현재 문자열에서 변경하고 싶은 문자

• new: 새로 바꿀 문자

• count: 변경할 횟수. 횟수는 입력하지 않으면 old의 문자열 전체를 변경한다. 기본값은 전체를 의미하는 count=-1로 지정되어있다.

  (출처 : https://ooyoung.tistory.com/77)

📝문제3. 백준 1365번(꼬인 전깃줄)

- 문제

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

- 나의 코드💻

코드를 입력하세요

- 정답 코드💻

코드를 입력하세요

- 비교 분석📖

앞의 문제들에 시간을 너무 많이 할애해서.. 꼭 나중에 다시 풀어야지.. 어제의 반도체 설계 문제와 비슷한 유형이라고 하는 것 같다.

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책을 기반으로 작성한 글입니다.

- 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)이므로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받습니다.

입력 조건

• 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 ≤ N ≤ 1,000,000), (-10⁹ ≤ x ≤ 10⁹)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10⁹ ≤ 각 원소의 값 ≤ 10⁹)

출력 조건

• 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

입력 예시 1 7 2 1 1 2 2 2 2 3

출력 예시 1 4

입력 예시 2 7 4 1 1 2 2 2 2 3

출력 예시 2 -1

- 나의 코드💻

from sys import stdin
n, x = map(int, stdin.readline().split())
array = list(map(int, stdin.readline().split()))
print(array.count(x))

-> 시간 복잡도를 고려하지 않고 작성함

- 정답 코드💻

1. 이진 탐색 예시 1

   from sys import stdin
   

정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드

def count_by_value(array, x): # 데이터의 개수 n = len(array)

# x가 처음 등장한 인덱스 계산
a = first(array, x, 0, n-1)

# 수열에 x가 존재하지 않는 경우
if a == None:
    return 0  # 값이 x인 원소의 개수는 0이므로 0 반환

# x가 마지막으로 등장한 인덱스 계산
b = last(array, x, 0, n-1)

# 개수를 반환
return b - a + 1

처음 위치를 찾는 이진 탐색 메서드

def first(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 해당 값을 가지는 원소 중에서 가장 왼쪽에 있는 경우에만 인덱스 반환 if (mid == 0 or target > array[mid - 1]) and array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작거나 같은 경우 왼쪽 확인 elif array[mid] >= target: return first(array, target, start, mid-1) # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: return first(array, target, mid+1, end)

마지막 위치를 찾는 이진 탐색 메서드

def last(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 해당 값을 가지는 원소 중에서 가장 오른쪽에 있는 경우에만 인덱스 반환 if (mid == n-1 or target < array[mid + 1]) and array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return last(array, target, start, mid - 1) # 중간점의 값보다 찾고자 하는 값이 크거나 같은 경우 오른쪽 확인 else: return last(array, target, mid + 1, end)

n, x = map(int, stdin.readline().split()) array = list(map(int, stdin.readline().split()))

값이 x인 데이터의 개수 계산

count = count_by_value(array, x)

값이 x인 원소가 존재하지 않는다면

if count == 0: print(-1)

값이 x인 원소가 존재한다면

else: print(count)

2. 이진 탐색 예시 2(bisect 이용)
```python
from sys import stdin
from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value] 인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

n, x = map(int, stdin.readline().split())
array = list(map(int, stdin.readline().split()))

# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)

참고 :

- 비교 분석📖

시간 복잡도 O(logN)으로 동작하는 알고리즘을 요구하고 있는 문제이다. 따라서 일반적인 선형 탐색으로는 해결할 수 없다. 다행히 모든 원소가 정렬된 채로 입력되므로 이진 탐색을 이용하여 값이 x인 원소의 개수를 시간 내에 찾아낼 수 있다.

원소들은 모두 정렬되어 있기 때문에, 수열 내에 x가 존재한다면 연속적으로 나열되어 있을 것으로 예상할 수 있다. 따라서 x가 처음 등장하는 인덱스와 x가 마지막으로 등장하는 인덱스를 각각 계산한 뒤에, 그 인덱스의 차이를 계산하여 문제를 해결할 수 있다. 그러므로 이진 탐색 함수를 2개 작성하여 문제를 해결한다.

예를 들어 [1, 1,** 2, 2, 2, **2, 3] 으로 7개의 원소를 갖는 정렬된 수열이 있을 때, '2'가 등장하는 첫 위치와 마지막 위치를 찾는 것이다.

하나는 데이터가 존재한다면 가장 첫 번째 위치를 찾는 이진 탐색 함수이며, 다른 하나는 데이터가 존재한다면 가장 마지막 위치를 찾는 이진 탐색 함수이다. 이 2개를 각각 실행한 뒤에 답을 도출할 수 있다. 이러한 방법은 이진 탐색을 요구하는 고난이도 문제에서 자주 사용할 수 있는 테크닉으로, 이 문제에서 사용된 코드를 잘 이해하면 도움이 될 것이다.

-> 아직 이진 탐색 코드는 좀 어려운 것 같다. 그나마 비교적 수월하게 느껴지는 bisect 라이브러리를 잘 이용해봐야겠다.

📝문제2. 고정점 찾기

- 문제

고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2]=2이므로, 고정점은 2가 됩니다.

하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 만약 고정점이 없다면 -1을 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 조건

• 첫째 줄에 N이 입력됩니다. (1≤N≤1,000,000)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤각 원소의 값 ≤10^9)

출력 조건

• 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

입력 예시 1 5 -15 -6 1 3 7 출력 예시 1 3

입력 예시 2 7 -15 -4 2 8 9 13 15 출력 예시 2 2

입력 예시 3 7 -15 -4 3 8 9 13 15 출력 예시 3 -1

- 나의 코드💻

from sys import stdin

n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))


def fixed_dot(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == mid:
        return mid
    elif array[mid] > mid:
        return fixed_dot(array, start, mid - 1)
    else:
        return fixed_dot(array, mid + 1, end)


result = fixed_dot(array, 0, n - 1)
if result == None:
    print(-1)
else:
    print(result)

- 정답 코드💻

from sys import stdin

def fixed_dot(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 고정점을 찾은 경우 인덱스 반환
    if array[mid] == mid:
        return mid
    # 중간점이 가리키는 위치의 값보다 중간점이 작은 경우 왼쪽 확인
    elif array[mid] > mid:
        return fixed_dot(array, start, mid - 1)
    # 중간점이 가리키는 위치의 값보다 중간점이 큰 경우 오른쪽 확인
    else:
        return fixed_dot(array, mid + 1, end)


n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

result = fixed_dot(array, 0, n - 1)
if result == None:
    print(-1)
else:
    print(result)

- 비교 분석📖

이미 배열이 정렬되어 있으므로 바로 이진탐색을 적용할 수 있는 문제이다. 참고로 이진 탐색을 수행할 때는 '찾고자 하는 값'이 '중간점'과 동일하다고 가정하고, 탐색을 수행하면 된다. 그래서 중간점이 가리키는 위치의 값보다 중간점이 작은 경우에는 왼쪽 부분을 탐색하고, 중간점이 가리키는 위치의 값보다 중간점이 큰 경우에는 오른쪽 부분을 탐색하는 것을 반복하면 된다.

-> 월요일 스터디 자료에 있는 기본 이진탐색 코드를 보면서 작성해봤다. 사실 그 과정을 완전히 이해하지는 못했고, 잘 모르겠어서 코드를 비슷한대로 따라쳤다.. 다행히 옳게 작성한 것 같다. 그런데 고정점이 여러개인 경우는 없는건가? 배열을 이용해 고정점이 여러개인 상황을 고려하려고 했는데 그러면 출력할때 for문이 생기는데 괜찮은건가??...

📝문제3. 백준 2352번(반도체 설계)

- 문제

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

문제 반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

입력 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력 첫째 줄에 최대 연결 개수를 출력한다.

예제 입력 6 4 2 6 3 1 5 예제 출력 3

- 나의 코드💻

from sys import stdin
n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

def design(array, start, end):
    if start > end:
        return None
    mid = (start + end) //2
    if

-> 포기..

- 정답 코드💻

코드를 입력하세요

- 비교 분석📖

lis 문제라고 하는데, 개념이 낯설기도 하고 코드 이해가 잘 가지도 않는다. 마음이 급해져서 그런지 잘 머리에 들어오지 않아 추후 다시 복습하겠다..!

참고 블로그 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=adamdoha&logNo=221622180884

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책을 기반으로 작성한 글입니다.

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다.

순차 탐색은 이름처럼 순차로 데이터를 탐색한다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메소드를 이용할 때도 내부에서는 순차 탐색이 수행된다.

- 코드💻

def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우 
        if array[i] == target:
            return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

이처럼 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점이 특징이다. 따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다.

👩‍🏫 이진 탐색

이진 탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있는 특징이 있다.

이진 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

- 예시

중간점의 데이터 8이 더 크므로 중간점 이후의 값은 확인할 필요가 없다. 끝점을 [4]의 이전인 [3]으로 옯긴다. 중간점에 위치한 데이터 2는 찾으려는 데이터 4보다 작으므로 이번에는 값이 2 이하인 데이터는 더 이상 확인할 필요가 없다. 따라서 시작점을 [2]로 변경한다. 중간점에 위치한 데이터 4는 찾으려는 데이터 4와 동일하므로 이 시점에서 탐색을 종료한다.

- 시간 복잡도

- 코드💻

1. 재귀 함수로 구현한 이진 탐색 소스코드

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)


# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

mid = (start + end) // 2 는 중간점을 의미한다. 2로 나눈 몫만 구하기 위해 몫 연산자(//)를 이용한 것이다. 앞서 그리디 부분에서 '큰 수의 법칙' 문제를 풀 때에는 나눈 뒤에 몫을 구하기 위해 int() 함수를 이용했다. 기능 면에서는 두 코드 모두 나눈 몫을 구하는 코드이다. 이처럼 같은 기능이라 하더라도 다양한 방법으로 구현이 가능하다는 점을 기억하자.

2. 반복문으로 구현한 이진 탐색 소스코드

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

- 파이썬 이진 탐색 라이브러리

값이 특정 범위에 속하는 데이터 개수 구하기

- 파라메트릭 서치

최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다.

• 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용해 해결할 수 있다.

- 코딩 테스트에서의 이진탐색

참고할 소스코드가 없는 상태에서 이진 탐색의 소스코드를 구현하는 것은 상당히 어려운 작업이 될 수 있다. 코드가 짧으니 이진 탐색을 처음 접했다면, 여러 차례 코드를 입력하며 자연스럽게 외워보자. 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 가급적 외우는 것을 권한다.

더불어 코딩 테스트의 이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다. 따라서 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접해보길 권한다. 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다.

- 빠르게 입력받기

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 예를 들어 데이터의 개수가 1,000만개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해 보자. 이렇게 입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. 이와 같은 문제는 sys 라이브러리 readline() 함수를 이용하면 시간 초과를 피할 수 있다.

import sys
# 하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().strip()

# 입력받은 문자열 그대로 출력
print(input_data)

sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다. 소스 코드에 readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다.

👩‍🏫 트리 자료구조

이진 탐색은 전제 조건이 데이터 정렬이다. 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 따라서 데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다.

트리 자료구조는 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다. 트리 자료구조는 몇 가지 주요한 특징이 있다.

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드라고 한다.
• 트리에서 일부를 뗴어내도 트리 구조이며 이를 서브 트리라 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다르기에 적합하다.

정리하자면 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다.

- 이진 탐색 트리

이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.

모든 트리가 다 이진 탐색 트리는 아니며, 이진 탐색 트리는 다음과 같은 특징을 가진다.

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.

즉, 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야 이진 탐색트리라 할 수 있다.

이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료 구조에 가까우며, 이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮다.

이진 탐색 트리에서 데이터 조회는 동작 원리만 살펴보면 간단하게 느껴진다. 공식에 따라 루트 노드부터 왼쪽 자식 노드 혹은 오른쪽 자식 노드로 이동하며 반복적으로 방문한다. 자식 노드가 없을 때까지 원소를 찾지 못했다면, 이진 탐색 트리에 원소가 없는 것이다.

📝문제1. 부품 찾기

- 문제

문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N=5 [8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3 [5, 7, 9]

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

입력조건

• 첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 10억 이하이다.

출력조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

입력 예시 5 8 3 7 9 2 3 5 7 9 출력 예시 no yes yes

- 코드💻

1. 이진 탐색

먼저 매장 내 n개의 부품을 번호를 기준으로 정렬한다. 그 이후에 m개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사하면 된다. 이때 매장의 부품들은 정렬이 되어 있기 때문에 이진 탐색을 수행하여 찾을 수 있다.

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None


# n : 가게의 부품 개수
n = int(input())
array = list(map(int, input().split()))
array.sort()

# m : 손님이 확인 요청한 부품 개수
m = int(input())
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    result = binary_search(array, i, 0, n-1)
    if result != None:
        print('yes', end=' ')
    else:
        print('no', end=' ')

2. 계수 정렬

이진 탐색 외에도 계수 정렬의 개념을 이용하여 문제를 풀 수도 있다. 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인하면 된다.

n = int(input())
array = [0] * 1000001

for i in input().split():
    array[int(i)] = 1

m = int(input())
x = list(map(int, input().split()))

for i in x:
    if array[i] == 1:
        print('yes', end=" ")
    else:
        print('no', end=" ")

*3. 집합 자료형 * 또는 이 문제는 단순히 특정한 수가 한 번이라도 등장했는지를 검사하면 되므로 집합 자료형을 이용해서 문제를 해결할 수 있다. set() 함수는 집합 자료형을 초기화할 때 사용한다. 이러한 집합 자료형은 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적으로 사용할 수 있다.

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

m = int(input())
x = list(map(int, input().split()))

for i in x:
    if i in array:
        print('yes', end=" ")
    else:
        print('no', end=" ")

📝문제2. 떡볶이 떡 만들기

- 문제

문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이 (H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기를 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm 이다, 손님은 6cm만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1000000, 1 <= M <= 2000000000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

입력예시 4 6 19 15 10 17 출력예시 15

- 해설

- 코드💻

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력받기
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행(반복적)
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때의 떡볶이 양 계산
        if x > mid:
            total += x - mid
    # 떡볶이 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡볶이 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
    else:
        result = mid  # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

# 정답 출력
print(result)

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 이코테 유튜브 강의 영상을 기반으로 작성한 글입니다.