[TIL] 자료구조/알고리즘 풀기 (5)

학습 주제

---

1. [특강] ChatGPT 활용하기

2. [Heap] 더 맵게

3. [DP] N으로 표현

4. [DFS / BFS] 여행경로
   
   

1. [특강] ChatGPT 활용하기

---

• LLM(Large Language Model)
  • 문장의 일부를 보고 비어있는 단어를 확률적으로 맞추는(Word Completion) 모델
    
    

• Temperature

  • 0과 100 사이의 값
  • 100에 가까울수록 조금 더 랜덤해짐
    
    

• 훈련

  • Unsupervised Learning

  • 웹상에서 존재하는 문서들이 모델의 훈련 데이터

  • 품질이 중요하기 때문에 위키피디아를 가장 많이 이용

  • 코드에도 적용 가능(Code Completion)하며, 이 경우 Github를 훈련 데이터로 사용

  • 언어 모델에 사용되는 Transformer 모델은 기본적으로 수학 모델
    
    

  • 단어를 그대로 사용할 수 없고 이를 숫자로 변환한 후(One-hot encoding) 다시 N차원 공간의 벡터로 변환

    • 이를 워드 임베딩(Word Embedding)이라고 부름
      • 데이터의 크기를 줄이고 단어 간의 유사도 측정 가능
        - king : queen = man : woman
        
        

• Fine Tuning

  • 이미 만들어진 모델(Pre-trained Model) 위에 새로운 레이어를 얹히고 다른 용도의 데이터로 훈련하는 것
    • GPT는 이를 API로 지원
      
      

• 업무에 사용해보기

  • 검색하거나 주변에 물어보던 모든 일에 ChatGPT를 사용해보기

  • 단발성으로 끝나지 않고 계속해서 이어서 질문해 내가 원하는 것을 얻어내기
    
    

• 질문(Prompt)의 중요성

  • 삼성전자 휴대폰 판매량을 알려줘 vs 삼성전자 휴대폰 판매량을 2018년부터 분기별로 알려줘
    
    

• 코딩에 사용해보기

  • 특정 기능의 함수를 구현해야하는 경우 ChatGPT에게 물어보기

  • 코드 리뷰, 주석 작성, 테스트 코드 추가 요구
    
    

• 학습에 사용해보기

  • 새로운 기술이나 개념을 학습할 때 ChatGPT에게 물어보거나 학습 방법에 대해 문의해보기
    
    

• 업무 자동화, 생산성 증대를 위해 GenAI(Generative AI) 툴을 많이 사용해보기

  • https://github.com/steven2358/awesome-generative-ai
    
    

• ChatGPT처럼 각광받는 기술을 바라보는 관점

  • 발전이 너무 빠르기 때문에 이를 쫓아다니는 것은 시간낭비

  • 확실한 방향이 보이기 전까지는 뉴스레터 등을 구독해서 요약본으로만 따라가고, 일상에서 관련 툴을 활용

2. [Heap] 더 맵게

---

• 풀이

  • scoville의 길이가 최대 1,000,000이므로 O(N) 혹은 O(N * log N)의 알고리즘을 구현해야 함

  • 최소 원소를 빠르게 추출하기 위해 힙(Heap) 사용
    
    

• 구현

  import heapq
  
  def solution(scoville, K):
  
      # 리스트를 힙으로 변환
      heapq.heapify(scoville)
  
      count = 0
      while True:
          first = heapq.heappop(scoville)
  
          # 가장 작은 원소가 K 이상이면 반복 종료
          if first >= K:
              break
  
          else:
              # 원소가 남아있다면 두 번째로 작은 원소를 추출해 연산 후 연산 횟수 증가
              if len(scoville) >= 1:
                  second = heapq.heappop(scoville)
                  heapq.heappush(scoville, first + (second * 2))
                  count += 1
  
              # 원소가 남아있지 않다면 모든 음식의 스코빌을 K 이상으로 만들 수 없으므로 -1 반환
              else:
                  return -1
  
      # 연산 횟수 반환
      return count

3. [DP] N으로 표현

---

4. [DFS/BFS] 여행경로

---

• 풀이

  • 모든 정점이 아닌, 모든 간선을 이용하는 것

  • 스택을 활용한 재귀적인 한 붓 그리기 문제
    
    

• 구현

  def solution(tickets):
  
  	# 딕셔너리 형태로 인접한 공항 저장
      route = {}
  
      for t in tickets:
          if t[0] in route:
              route[t[0]].append(t[1])
  
          else:
              route[t[0]] = [t[1]]
  
      # 리스트의 앞에서 pop하는 것보다 뒤에서하는 것이 더 빠르기 때문에 역순으로 정렬
      for key in route:
          route[key].sort(reverse = True)
  
      stack = ["ICN"]
      visited = []
  
      while len(stack) > 0:
          top = stack[-1]
  
          # 스택의 최상단에 있는 공항에서 다른 공항으로 가는 표가 없을 경우 경로에 추가(마지막에 방문)
          if top not in route or len(route[top]) == 0:
              visited.append(stack.pop())
  
          # 표가 있을 경우, 스택에 추가
          else:
              stack.append(route[top].pop())
  
      return visited[::-1]

메모

---

• heapq 라이브러리

  • heapq.heapify(list): 인자로 받은 리스트를 힙으로 변환

  • heapq.heappush(heap, item): 인자로 받은 힙에 두 번째 인자로 받은 item 추가

  • heapq.heappop(heap): 인자로 받은 힙에서 가장 작은 값 추출

    • 최대 힙일 경우 가장 큰 값 추출