컴공0개언어

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42586

queue에 각 작업마다 배포가 몇 일 후에 진행될 수 있는지를 저장한다.

이 때, 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발되면 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다. 따라서

여기서 저장하려는 배포 일자가 queue에 저장된 최대 배포 일자보다 크면 그동안 queue에 저장된 작업들을 배포할 수 있으므로 answer에 queue의 길이를 저장하고, queue를 비운다.

이러한 과정을 반복하고, 과정이 끝나면 queue에 남아 있는 작업들이 있을 수 있으므로 queue에 남은 작업이 있으면 queue의 길이를 answer에 추가한다.

import math
from collections import deque

def solution(progresses, speeds):
    answer = []
    
    queue = deque()
    max_work_day = -1
    for progress, speed in zip(progresses, speeds):
        work_day = math.ceil((100 - progress) / speed) # 배포까지 걸리는 시간
        
        if max_work_day < work_day:
            if len(queue) > 0:
                answer.append(len(queue))
            
            queue.clear()
                
            max_work_day = work_day
            
        queue.append(work_day)
    
    if len(queue) > 0:
        answer.append(len(queue))
        
    return answer

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42584

prices의 길이를 n이라고 하면, 최대 O(nlogn)의 풀이가 가능해 보였다.

스택을 이용해서 문제의 요구사항대로 구현하고자 했다. 

스택의 top에 있는 주식의 price가 추가하려고하는 주식의 price보다 같거나 작으면 그냥 스택에 push하고, 크면 스택 top 주식의 price가 추가하려고하는 주식의 price보다 같거나 작아질 때까지 pop을 한다.

따라서 스택을 이용한 풀이의 최종 시간 복잡도가 O(n)가 된다.

def solution(prices):
    # prices의 길이 : 1 <= n <= 100000
    # 최대 O(nlogn) 정도 가능
    
    n_prices = len(prices)
    answer = [0 for _ in range(n_prices)]
    
    stack = [(prices[0], 0)] # (주식 가격, stack에 push된 시점)
    for i, price in enumerate(prices):
        top_price = stack[-1][0]
        
        if top_price > price:
            # top_price <= price가 될 때까지 pop한 후에 push
            while top_price > price:
                stack_top = stack.pop()
                answer[stack_top[1]] = i - stack_top[1]
                
                if len(stack) == 0:
                    break
                
                top_price = stack[-1][0]
            
        stack.append((price, i))
    
    
    while len(stack) > 0:
        stack_top = stack.pop()
        answer[stack_top[1]] = n_prices - 1 - stack_top[1]
    
    # 최종 복잡도 : O(n)
    return answer

금요일부로 2주동안 진행된 P Stage 1이 종료됐다.

P Stage는 총 4개의 Stage로 이루어져 있는데, P Stage에 진행하는 프로젝트 주제들은 부스트캠프 홈페이지에 나와있는 것과 거의 동일하다. 그리고 P Stage는 Kaggle이나 데이콘같이 Competition 형식으로 진행됐다. 

P Stage 1 주제는 이미지 분류(Image Classification)로 진행됐다.

총 18개 클래스로 이미지를 분류하는 문제였는데, 클래스별 불균형이 상당히 심해서 불균형 문제를 해결하는 것이 중요한 포인트였던 것 같았다. 

파이토치로 competition을 처음 참가해봐서 어렵기도 했는데 먼저 데이터셋을 구성하고 모델을 구성하는 등등 전체적인 흐름을 만들고 본격적으로 여러 실험들을 해보았다.

여러가지를 실험해보면서 Albumentation을 통한 augmentation, timm을 이용한 pretrained 모델 사용, Stratified K-Fold Cross Validation, Focal Loss, Label Smoothing 등등의 다양한 기법들을 시도해볼 수 있었고, 시도는 못 해본 방법이지만 CutMix 등등 다양한 기법들이 있다는 것을 알 수 있었다. 또한 주피터 노트북만 계속 사용했는데, 다음 스테이지부터는 IDE를 이용한 모듈화를 해봐야겠다는 생각이 들었다. 

최종 등수는 조금 아쉬웠지만 이렇게 파이토치로 Competition을 참여해봐서 좋은 경험이었던 같고 데이터셋의 상태에 맞는 전략을 세우는 것도 중요한 것 같다는 생각이 들었다.

다음 스테이지도 열심히 해보자! 

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42578

소스코드의 간결함을 위해 defaultdict를 사용했다.

처음에는 combinations을 이용해서 가능한 모든 의상 종류 조합에 대해서 하나하나 구했는데, 시간복잡도가 O(2^m)이 되어 시간초과가 발생했다.

찾아보니 밑에 소스코드와 같은 풀이가 가능했는데, 약간 고등학교 때 확통 문제를 푸는 듯 했다...

def solution(clothes):
    # 의상 수 : 1 <= n <= 30
    # 의상 종류 수 : 1 <= m <= n
    answer = 1
    type2count = defaultdict(int) # key: 종류, value: 종류 count
    
    # n + m = O(n)
    for _, cloth_type in clothes:
        type2count[cloth_type] += 1
    
    keys = list(type2count.keys())
    
    for key in keys:
        # 종류에 있는 의상 개수가 n개라면 해당 종류의 의상을 선택하는 경우의 수는
        # (0개 선택), (1개 선택), ..., (n개 선택) ==> 총 n+1 경우
        answer *= type2count[key] + 1
        
    answer -= 1 # 모든 종류의 의상을 선택하지 않는 경우의 수를 뺌.
    
    return answer

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42577

먼저 전화번호들에 대해서 count가 1이므로 dictionary를 초기화한다.

그리고 전화번호들에 대해서 앞에서부터 하나씩 접두어를 저장하는 prefix에 저장하고, prefix가 dictionary에 있으면 접두어가 존재하므로 False를 return한다.

시간복잡도는 phone_book의 길이를 n, 전화번호의 길이를 m이라고 하면 O(nm)이다.

def solution(phone_book):
    answer = True
    prefix_dict = {} # key: phone_number, value: phone_number count
    
    
    for phone_number in phone_book:
        prefix_dict[phone_number] = 1
    
    for phone_number in phone_book:
        prefix = ""
        for digit in phone_number:
            prefix += digit
        
            if prefix in prefix_dict and prefix != phone_number:
                return False
                
    return True

어제부로 U스테이지의 모든 교육이 종료되었다.

다음주부터는 본격적으로 프로젝트를 진행하는 P스테이지에 들어가게 된다. 현재 P스테이지 프로젝트 주제를 고르고 있는데, 무엇을 골라야할지 계속 고민중이다.

U스테이지를 진행하면서 많은 분야에 대해 얇게 학습한 것 같은데, 학습하면서 내가 많이 부족하다는 것을 느꼈다. 특히 딥러닝 구현이 일반적인 개발과는 결이 좀 다른 것 같아 나한테 맞는 것인가 고민을 하기도 했다. 그래도 아직 많이 해보지 않아서 이런 생각이 든 것 같기도해서 앞으로 구현도 열심히 해봐야겠다.

그리고 낮에 졸린 적이 한두 번이 아니었는데, 규칙적인 수면이 굉장히 중요하다는 것을 많이 느꼈다. 

그리고 강의와 관련된 일부 내용이 포함되어 있더라도 외부로 작성해서는 안 된다는 내용이 있어서 그동안 블로그에 올렸던 학습정리는 모두 지우는게 맞다고 생각해서 모두 지웠다.

솔직히 잡을 것 같지는 않은데 지우는게 마음은 편한 것 같다. 그래도 회고 형식의 글은 올려도 된다고 해서 어떻게 작성해서 블로그에 올릴지 고민중이다.

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42576

사실 해시 관련 문제가 어떤 것인지 잘 몰랐는데, 이 문제를 풀면서 대략적인 방법을 알게 된 것 같다.

해시 관련 문제를 풀 때는 어떻게 하면 탐색을 O(1)에 할 수 있는지를 생각하는게 중요하다 생각했다.

파이썬에서는 다행히 딕셔너리라는 좋은 자료형을 제공해줘서 딕셔너리를 잘 이용하면 될 것 같다.

이 문제는 완주자의 수가 (참여자의 수 - 1)이므로 사실상 같다고 할 수 있다. 따라서 참여자의 수를 n이라고 하면 1 <= n <= 100000이므로 시간복잡도를 최대 O(nlogn)까지 가능할 것이라 파악했다.

이 문제에서는 참여자 중 완주자에 포함되지 않는 사람을 찾는 것이고, 이를 위해 완주자가 참여자에 있는지 탐색을 하였다.

이 때, 탐색을 O(1)에 하기 위해 딕셔너리를 이용했고, 중복된 이름의 참여자가 있을 수 있으므로 딕셔너리의 Key로는 참여자의 이름, Value로는 Key값을 이름으로 가진 사람의 수를 저장하였다.

그리고 각 완주자들에 대해서 해당 완주자가 있으면 딕셔너리의 Value값을 1씩 감소시키고, Value가 0이 되면 Key를 이름으로 가진 사람은 완주를 했다는 것이므로 딕셔너리에서 삭제한다.

이러한 과정을 거치면 최종적으로 딕셔너리의 Key로는 완주하지 못한 한 사람의 이름과, Value값으로는 1을 갖게 된다.

따라서 하나 남은 Key를 최종 답으로 제출하면 된다.

해당 풀이는 O(n) 시간복잡도를 갖는다.

def solution(participant, completion):
    answer = ''
    participant_dict = {}
    
    for p in participant:
        if p not in participant_dict:
            participant_dict[p] = 1
        else:
            participant_dict[p] += 1
    
    for c in completion:
        participant_dict[c] -= 1
        if participant_dict[c] == 0:
            del participant_dict[c]
    
    answer = list(participant_dict.keys())[0]
    
    return answer

해당 알고리즘의 채점 결과이다.

그리고 defaultdict를 사용하면 key값에 대해서 if Key not in dict 구문을 사용하지 않아도 되므로 코드를 약간 간결하게 할 수 있다. 다만 시간은 기본 dictionary를 사용했을 때 보다 조금 느리다.

from collections import defaultdict

def solution(participant, completion):
    answer = ''
    participant_dict = defaultdict(int)
    
    for p in participant:
        participant_dict[p] += 1
    
    for c in completion:
        participant_dict[c] -= 1
        if participant_dict[c] == 0:
            del participant_dict[c]
    
    answer = list(participant_dict.keys())[0]
    
    return answer

오늘은 학습 정리를 대신해서 4주차 후기를 짧게 작성해보고자 한다.

어느덧 과정이 시작한지는 5주가 되었는데, 설 연휴가 있었던 지난주를 통째로 쉬어서 이번 주가 4주차가 되었다.

4주차 강의는 NLP에 대해서 진행되었는데

자연어처리의 굵직한 모델들에 대해서 한정된 강의 시간이지만 정말 많은 내용을 배울 수 있었다.

설명해주시는 내용이 정말 많아서 강의를 듣고, 정리하기까지 제일 많은 시간이 걸렸던 것 같다.

물론 강의에서 모든 내용을 다뤄주지는 않기 때문에 더 자세하게 알고 싶다면 개인적인 학습이 필요한 것 같다.

하지만 이번주는 너무 피곤했다....

해커톤과 교육을 같이 병행해서 잠도 별로 못 자서 강의에 집중도 잘 안 되고 너무 졸렸다

앞으로는 교육만 듣기로 결정.........

내일부터는 강의와 학습정리도 안 밀리고 과제로 미리미리 해서 저녁에 좀 자유 시간을 보내보고 싶다.