[DE 데브코스] 04.14 TIL - ChatGPT 특강, 코딩테스트 연습(Hash, Greedy, Sort)

한기용 강사님의 ChatGPT 특강

• LLM과 GPT

Large Language Model은 문장의 일부를 보고 비어있는 단어를 확률적으로 맞추는 모델이다.

이 모델을 Train할때는 비지도 방식을 사용하는데 웹상에 존재하는 문서들이 모델의 훈련 데이터가 된다.

그리고 Temperature 개념이 들어가는데, 이는 자유도 개념으로써

이를 100으로 줄수록 출력 값이 랜덤으로 정해지고 0에 가까울수록 정해진 답으로 출력한다.

 

GPT는 OpenAI에서 만든 초거대 언어 모델이다.

GPT는 Word Completion, Code Completion 두 가지 모델을 제공한다.

cf) 네이버의 초거대 언어 모델은 Word Completion만 지원한다.

 

GPT-3 버전은 175B개의 파라미터를 사용하고 Context Window의 크기는 2,048+1이고

GPT-4 버전은 1T개의 파라미터를 사용하고 Context Window의 크기는 8,192+1이다.

그리고 GPT-4는 이미지 인식이 가능하다.

그러나 GPT의 단점은 Continuous Learning이 되지 않는다는 점인데, 이는 여전히 유효하다.

 

GPT API도 존재하는데 이 API들은 유료다.

그리고 API는 Fine Tuning도 제공하는데, 이미 만들어진 모델 위에 새로운 레이어를 얹히고 다른 용도의 데이터로

훈련하는 것을 의미한다. ( 기본 언어 모델 위에 나만의 모델을 생성하는 것이다. )

 

• ChatGPT

GPT를 챗봇의 형태로 Fine-Tuning한 것이다.

GPT의 지식을 챗봇의 형태로 활용할 수 있는데, 덕분에 프롬프트 엔지니어링이 빛을 보기 시작했다.

챗지피티의 발전이 너무 빨라서 이걸 쫓아 가는 것은 아직 무리라는 말씀을 해주셨다.

챗지피티가 대세가 될 기미가 보일 때, 빠르게 따라잡을 수 있도록 기본기를 먼저 충실하게 쌓자!

( C++를 배워놓으면 JAVA는 쉽게 배우는 것 마냥.. )

 

Hash

• 해시에서는 list를 선형 탐색 하는 것처럼 따로 Search의 과정을 거치지 않아도 key로 원소를 찾을 수 있다.
• hash table에 저장된 값을 찾아가는데 hash function이 사용된다. ( key -> hash function -> hash table )
• 해쉬 충돌이 발생할 수 있는데, 이는 다른 key인데 같은 bucket을 맵핑하는 경우를 의미한다.
• Python에서는 Dictionary를 이용하여 Hash를 흉내낼 수 있다.
• 사전의 원소들을 해시를 이용해 O(1)에 접근 가능하다.
• dict.get(i, 0) 같은 메소드를 이용하여 딕셔너리 key에 해당하는 값을 get하거나, 0을 할당할 수 있다.
• 딕셔너리를 자유자재로 활용하기 위하여 .get(key, 0)이나 .items()와 같은 메소드는 확실하게 익혀둘 필요가 있다.
• 해시를 연습하기 위해서는 프로그래머스의 코딩테스트 고득점 Kit의 Hash 부분을 풀어보거나, 관련한 백준 문제를 풀어보자.

 

Greedy

• 그리디 알고리즘은 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하는 알고리즘이다.
• 그리디 풀이법은 딱히 '정형화'된 형식이 없으므로, 설계할 알고리즘의 복잡도를 항상 염두하며 풀어나가자.
• 역시나 그리디를 연습하기 위해서 관련 백준 문제나 프로그래머스 문제를 풀어보면 되겠다.
• 오늘은 대표적으로 프로그래머스 기준 Lv.1 그리디 문제인 <체육복> 문제를 풀이했다.
• 쉬운 그리디 문제라도 2가지 경우로 나눠서 풀이를 할 수 있다는 것을 파악했다.
• 첫 번째 방법은 그냥 iterlative한 풀이법이다.

def solution(n, lost, reserve):
    li = [1] * (n+2)
    for i in lost:
        li[i] -= 1
    for j in reserve:
        li[j] += 1
    for k in range(1, n+1):
        if li[k-1] == 0 and li[k] == 2:
            li[k-1:k+1] = [1,1]
        elif li[k] == 2 and li[k+1] == 0:
            li[k:k+2] = [1,1]
    return len([ t for t in li[1:n+1] if t>= 1])

• 위 알고리즘의 시간 복잡도는 O(n)이다. 따라서, 만약 n이 1억 이상으로 주어질 경우 시간 초과가 발생할 가능성이 높다.
• n이 높을 경우, set을 이용한 문제풀이로 시간 초과를 방지할 수 있다.
• 마지막에 len을 이용하는 대신에 sum을 이용할 수도 있겠다.

 

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for i in sorted(r):
        if i-1 in l:
            l.remove(i-1)
        elif i+1 in l:
            l.remove(i+1)
    return n-len(l)

 

• 이처럼 set을 이용한다면, sorted(r)에 들어가는 O( n log n )의 연산이 사실상 시간복잡도 일 것이다.
• 단, 이는 lost, reserve의 길이(n)가 극도로 작을 경우 효율적일 것이다. 분명 set에 들어가는 연산도 있을 텐데 lost와 reserve의 값이 커버리면 iterlative한 방법보다 비효율적일 수 있다.

 

Sort

• 내가 원하는 기준으로 list를 정렬해서 문제를 해결하는 문제다.
• <가장 큰 수> 문제를 예시로 풀이했다. 이 문제는 '최적'을 탐욕적으로 선택하는 그리디 접근법도 섞여있다.
• <가장 큰 수> 문제의 경우, 가장 큰 수를 만드는 순서로 '어떻게' 정렬할 것인가?
• <가장 큰 수>는 x+y > y+x를 생각할 수 있느냐가 핵심이었던 문제.
• (Python) 파이썬에서는 문자열을 쭉 늘려서 (ex. 34343434... vs 343343343...) 어느 수가 더 클까? 를 비교한다.
• <가장 큰 수> : 원소에 0 이 들어갈 수 있다는 제약 조건에 유의한다.

 

Greedy(2)

• <큰 수 만들기> 라는 문제도 풀이한 강의를 학습했다.
• 해당 풀이는 "앞에서 부터 훑어서 지금 담으려는 것보다 작은 것들은 빼버린다."는 로직을 생각할수 있느냐.
• ex) 1924 ->  9 -> 94
• 이걸 왜 자꾸 나는 뒤에서 부터 훑어서 작은 것들 빼버린다로 생각이 드는지 처음에 볼때...

 

오늘 공부하며 어려웠던 내용

• 분명 <가장 큰 수> 문제가 백준에서는 플5 문제로 나와서 어려웠던 기억이 나는데 lv.2로 나와서 당황했다.
• <가장 큰 수> 같은 문제는 처음에 문제 해결 로직을 생각하는데 오래걸린다.
• 그리고 오래 생각한다고 100% 답을 도출할 수 있는 것도 아니었다.
• 이런건 결국 많이 풀어봐야..^^