📖 오늘의 학습

• 코딩테스트 : 힙, 깊이/너비 우선탐색(DFS/BFS), 동적계획법 (Dynamic programming)
• 특강 : chatGPT에 관한 특강

---

코딩테스트 문제풀이

1. 힙 (Heap) - 더 맵게

• 최소/최대 원소를 빠르게 꺼낼 수 있으면 좋음
  • 힙이 적당함
• 힙 구성, 삽입, 삭제 연산을 이용하여 풀이
• heapq 의 import가 필요함
• 주어진 리스트로부터 최소힙을 구성
• 최소힙에서 최소값을 반환, 삽입하면서 문제 풀이

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 1 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scoville K return
[1, 2, 3, 9, 10, 12] 7 2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]
   모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

문제 풀이 절차

1. heapq.heapify 메소드를 이용하여 주어진 리스트를 최소힙으로 구성
2. 무한 순환문 안에서 최소힙에서 반환한 원소가 K보다 클 때 빠져나온다. 또는 최소힙에서 모든 원소를 반환했음에도 K보다 작은 경우 스코빌 지수를 K 이상으로 만들 수 없는 경우이기 때문에 순환문을 빠져나오고 -1을 리턴한다.
3. 2번의 경우가 아니라면 첫번째 최소값과 두번째 최소값을 반환하여 새로운 스코빌 지수를 만들고 그걸 최소힙에 넣는다. (넣음과 동시에 정렬되어 알맞은 위치를 찾아서 들어감..)
4. 위 과정을 반복하고 2나 3번에서 빠져나왔을 때의 answer가 정답

코드구현

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    for _ in range(len(scoville)):
        s1 = heapq.heappop(scoville)
        if s1 >= K:
            break
        else:
            if len(scoville) > 0:
                s2 = heapq.heappop(scoville)
                heapq.heappush(scoville, s1 + (s2 * 2))
                answer += 1
    else:
        return -1    
    
    return answer

2. 깊이 우선 탐색 (DFS) - 여행경로

먼저 이 문제를 풀기 위해서는 그래프의 특성과 DFS/BFS를 알아야 한다.
그래프
- 정점(vertex, node)과 간선(edge, link)으로 이루어져 있다.
- 유향(directed)그래프와 무향(undirected)그래프가 있다.
깊이 우선 탐색 (DFS; Depth-First Search)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
- 쉽게 말하자면 트리에서 아래로 쭉 방문했다가 다시 방문하지 않았던 맨 위의 노드로 가서 위 아래로 반복
너비 우선 탐색 (BFS; Breadth-First Search)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색을 행함
- 트리에서 동일 레벨의 노드들을 왼쪽에서 오른쪽으로 순차적으로 탐색

• 한 붓 그리기 문제
• 한 붓 그리기가 안되는 조건은 주어지지 않는다고 문제에서 보장하고 있음
• 시작 정점은 언제나 “ICN”으로 한정
• 모든 정점 방문이 아니고, 모든 간선을 거쳐야 함
  • 언젠가는 한번은 가야하는데, 그 순서를 결정해야 한다.
• 한 정점에서 택할 수 있는 간선이 두 개 이상이므로 이를 표현하기 위해서는 리스트를 사용해야 하고, 이를 알파벳 순으로 정렬해야 조건을 맞출 수 있다.
• 스택을 이용하여 재귀적인 “한 붓 그리기” 문제를 해결한다. (-> DFS 알고리즘의 응용)

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1
["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.
예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

문제 풀이 절차

1. 해시(dict)를 이용하여 각 공항에서 출발하는 항공권의 집합을 리스트로 표현한다.
2. 이렇게 각 공항마다 있는 항공권의 집합들을 정렬한다. 그런데 여기서 이후에 pop할 때 끝에서부터 하므로 역순으로 정렬해야한다.
3. 방문할 노드를 담을 스택을 만들고 거기에 방문한 공항을 해당 스택을 재귀적으로 스택의 길이가 0이 될때 가지 순환한다.
   예를 들어, ICN : [ ATL, SFO ] 로 인천공항은 두 개의 공항의 항공권을 가지고 있다. 문제에서 출발점은 항상 ICN이라고 했으므로 스택에는 ICN을 초기에 넣는다. 스택을 순환하면서 이를 반환하고 반환한 공항명으로 사전에서 티켓(공항)을 찾는다. ICN은 ATL, SFO가 있으므로 끝에 있는 티켓(공항)인 SFO가 스택에 들어간다. 또 다시 SFO는 스택에서 반환되어 이를 사전에서 찾고 반복… 이렇게 재귀적으로 스택에 삽입과 삭제한다.
4. 방문한 노드를 담을 스택에는 3번 스택에서 반환한 공황이 사전에 없거나, 사전에서 찾은 값이 없다면 ( ICN : [] 의 상태라면) 스택에 넣는다.
5. 마지막으로 4번 스택을 역순으로 정렬한 리스트를 반환한다.

코드 구현

def solution(tickets):
    routes = {}
    
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for r in routes:
        routes[r].sort(reverse=True)
    
    stack = ["ICN"]
    path = []
    
    while len(stack) > 0:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[top].pop())
            
    return path[::-1]

---

📝 주요메모사항

특강 - GPT에 관하여

언어 모델(Language model)이란?

• 문장의 일부를 보고 비어있는 단어를 확률적으로 맞추는 모델
• 모델의 훈련은 아무래도 공식적인 정보가 있는 Wikipedia에서 가장 많이 활용함

Supervised learning

• Supervised learning은 learning set이 필요함. 이 set을 만들기 위한 노력(데이터 모델에 맞춘 training data를 가져오고 transform하는 것)이 많이 들어간다.
• garbage in - garbage out의 구조...

Unsupervised learning

• 언어 모델의 경우 Unsupervised learning이다
• context window : context window의 크기가 4개면, 토큰 3개를 보고 1개의 토큰을 예측 훈련
• context window의 크기가 결국 모델의 메모리를 결정한다.
• 훈련을 용이하게 하기위해 문자열을 벡터로 변경(word embedding)

GPT

• 언어모델은 언어의 syntax를 이해하고 동작하는 것이 아님
• GPT 이외의 다른 경량 모델로도 일반적인 수준 이상의 언어 예측이 가능
• GPT4에서는 이미지 인식(입력)이 가능. 아마 다음 버전에서는 출력으로도 이미지가 가능해지지 않을까? 또한 비디오도 입력이 가능해지지 않을까?
• 현 GPT는 continuous learning이 되지 않는다. 현재 2021년도 후반의 Wikipedia정보를 말하고 있음

Fine tuning

• 이미 만들어진 모델을 tuning하여 비용을 덜 들이고 원하는 모델을 얻음
• 새로운 layer를 얹히고 다른 용도의 데이터로 훈련시킴
  GPT는 이를 API로 지원한다.
• chatGPT는 GPT를 챗봇의 형태로 fine tuning한 것이다.

chatGPT

• prompt engeneering - 질문을 잘 하는 것이 중요해짐
• 잘 활용하는 방법은 질문을 하나에 그치는 것이 아니라 그것을 보완하고 수정을 요구하면서 원하는 답을 얻어내는 것
• chatGPT 플러그인 - 정보를 주는 것이 그치지 않고 그와 연결된 서비스를 제공

---

😵 공부하면서 어려웠던 내용

당연히 모든 코테....😭🤯