컴공0개언어

문제링크 : www.acmicpc.net/problem/2164

deque를 사용하면 문제가 아주 간단해진다.

문제 설명에 나와있는대로 위에 있는 카드를 뺄 때는 deque.popleft()를 하면 되고, 위에 있는 카드를 아래로 옮길 때는 deque.popleft()값을 append해주면 된다.

import sys
from collections import deque

N = int(sys.stdin.readline())
deque = deque([i+1 for i in range(N)])

while len(deque) > 1:
    deque.popleft()
    deque.append(deque.popleft())

print(deque[0])

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

재귀를 이용한 dfs로 해결하였는데, 최소 수행 횟수를 찾는 것이므로 bfs로 푸는 것이 더 좋을 것 같다는 생각을 했다. 

is_convertible은 인자로 들어온 2개의 문자열에 대해서 같은 위치에 있지만 다른 알파벳 개수를 계산하는데, 문제 조건에서는 다른 알파벳이 1개일 경우에만 단어 변환을 해줄 수 있으므로 다른 알파벳 개수가 1개이면 True, 1개가 아니면 False를 반환한다.

dfs에서는 리스트를 잘라서 인자로 넣어주므로 단어들의 리스트인 words의 길이가 0이면 재귀를 탈출하도록 하였다.

그리고 for문 내에서 리스트의 index를 삭제할건데, for문을 도는 리스트를 삭제하면 에러가 발생하므로 copy()를 통해 리스트의 복사본을 생성한다.

이후 문제 조건에 맞게 if문을 설정하고 방문한 element를 삭제한 후 다시 dfs의 인자로 넘겨주었다.

def is_convertible(word1, word2):
    # len(word1) == len(word2)
    num_diff_words = sum([True if ch1 != ch2 else False for ch1, ch2 in zip(word1, word2)])
    if num_diff_words == 1:
        return True
    else:
        return False
    

min_count = 99999
def dfs(begin, target, words, count):
    global min_count
    if len(words) == 0:
        return
    
    words_copy = words.copy()
    
    for i, word in enumerate(words):
        if is_convertible(begin, word):
            if word == target:
                if count < min_count:
                    min_count = count
                return
            
            del words_copy[i]
            dfs(word, target, words_copy, count+1)
            words_copy = words.copy()


def solution(begin, target, words):
    global min_count
    
    if target not in words:
        return 0
    
    dfs(begin, target, words, 1)
    
    return min_count

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

재귀를 통한 dfs를 이용했다. 리스트를 잘라가며 재귀에 넘겨주므로 재귀 탈출 조건으로 numbers가 빈 리스트인 경우로 설정하였다. 인자에 있는 numbers는 계산을 하기 위해 남은 숫자 리스트, sum은 현재 재귀에서의 합을 뜻한다.

그리고 입력한 숫자에 대해서 +와 -모두 고려해야 되므로 현재 sum에 -한 값과 +한 값을 sum_1, sum_2로 설정하여 이용한다.

count = 0
def dfs(numbers, target, sum):
    global count
    
    if len(numbers) == 0:
        return
    
    sum_1 = sum - numbers[0]
    sum_2 = sum + numbers[0]
    
    if len(numbers) == 1:
        if sum_1 == target:
            count += 1
        if sum_2 == target:
            count += 1
    else:
        dfs(numbers[1:], target, sum_1)
        dfs(numbers[1:], target, sum_2)    


def solution(numbers, target):
    # 2 <= len(numbers) <= 20
    global count
    dfs(numbers, target, 0)
    
    return count

파이썬의 딕셔너리를 다루다 보면 정렬을 해야하는 경우가 발생한다. 딕셔너리는 key와 value를 가지고 있으므로 key값을 기준으로 정렬, value값을 기준으로 정렬을 할 수 있다.

우선 기본적으로 리스트와 달리 sort()를 사용할 수 없고 sorted()만 사용할 수 있다.

① key값을 기준으로 정렬

dict1 = {'g': 1, 'b': 5, 'z': 8, 'e': 2, 'k': 10}


sorted_dict1 = sorted(dict1.items(), key=lambda x: x[0])

print(sorted_dict1) # [('b', 5), ('e', 2), ('g', 1), ('k', 10), ('z', 8)]
print(type(sorted_dict1)) # <class 'list'> ==> dict타입 아님 주의!!


sorted_dict1 = dict(sorted(dict1.items(), key=lambda x: x[0])) 

print(sorted_dict1) # {'b': 5, 'e': 2, 'g': 1, 'k': 10, 'z': 8}
print(type(sorted_dict1)) # <class 'dict'>

위의 코드와 같이 sorted()결과는 리스트로, 딕셔너리로 사용하고 싶으면 dict()를 이용해야 한다.

그리고 정렬된 key값만 얻고싶은 경우에는 key인자를 설정하지 않아도 된다.

dict1 = {'g': 1, 'b': 5, 'z': 8, 'e': 2, 'k': 10}


sorted_dict1 = sorted(dict1) 

print(sorted_dict1) # ['b', 'e', 'g', 'k', 'z']
print(type(sorted_dict1)) # <class 'list'>


sorted_dict1 = sorted(dict1.keys()) 

print(sorted_dict1) # ['b', 'e', 'g', 'k', 'z']
print(type(sorted_dict1)) # <class 'list'>

sorted()에 dict1로 하는 경우와 dict1.keys()로 한 경우가 동일한 결과를 갖는다. 결과 type은 리스트다.

② value값을 기준으로 정렬

dict1 = {'g': 1, 'b': 5, 'z': 8, 'e': 2, 'k': 10}


sorted_dict1 = sorted(dict1.items(), key=lambda x: x[1]) 

print(sorted_dict1) # [('g', 1), ('e', 2), ('b', 5), ('z', 8), ('k', 10)]
print(type(sorted_dict1)) # <class 'list'> ==> dict타입 아님 주의!!


sorted_dict1 = dict(sorted(dict1.items(), key=lambda x: x[1]))

print(sorted_dict1) # {'g': 1, 'e': 2, 'b': 5, 'z': 8, 'k': 10}
print(type(sorted_dict1)) # <class 'dict'>

마찬가지로 sorted()결과는 리스트로, 딕셔너리로 사용하고 싶으면 dict()를 이용해야 한다.

그리고 정렬된 value값만 얻고싶은 경우에는 간단하게 values()를 이용하면 된다.

dict1 = {'g': 1, 'b': 5, 'z': 8, 'e': 2, 'k': 10}


sorted_dict1 = sorted(dict1.values()) 

print(sorted_dict1) # [1, 2, 5, 8, 10]
print(type(sorted_dict1)) # <class 'list'>

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

정규 표현식을 이용하면 간단하게 해결할 수 있는 문제다.

다만 처음에 3단계에서 정규표현식을 '.+'로 사용하였는데 계속 모든 답이 "aaa"로 나왔다.

정규표현식을 더 살펴보니 그냥 '.'을 사용하면 문자 전체를 의미하는 것이므로 단순이 '.'을 사용하면 안되고 '\.'을 사용해야 한다.

아직 정규표현식에 대해 익숙하지 않아 헷갈렸던 부분이다.

import re

def solution(new_id):
    answer = new_id
    
    # 1단계
    answer = answer.lower()
    
    # 2단계
    answer = re.sub('[^a-z0-9-_.]', '', answer)
    
    # 3단계
    # 그냥 . ==> 모든 문자, \. ==> 점
    answer = re.sub('\.+', '.', answer)
    
    # 4단계
    answer = answer.strip('.')
    
    # 5단계
    if not answer:
        answer = 'a'
    
    # 6단계
    if len(answer) >= 16:
        answer = answer[:15]
    answer = answer.rstrip('.')
    
    # 7단계
    if len(answer) <= 2:
        last_char = answer[-1]
        while len(answer) < 3:
            answer += last_char
    
    return answer

문제링크 : www.acmicpc.net/problem/2667

지도와 동일한 크기를 가지는 visited리스트를 만든다. visited는 방문했으면 True, 방문하지 않았으면 False값을 가진다. 따라서 map이 '1'값을 가지고, visited가 False값을 가질 때 탐색을 시작하도록 한다. 탐색한 부분의 visited는 True로 변경하고, 상하좌우 중 map이 '1'값을 가지고 visited가 False인 지점이 있으면 재귀를 이용하여 탐색을 진행한다.

import sys
sys.setrecursionlimit(10**9)

house_num = 0
house_nums = []
def dfs(house_map, visited, start_row, start_col):
    if visited[start_row][start_col]:
        return

    global house_num

    dx = [0, 0, -1, 1] # 상 하 좌 우
    dy = [-1, 1, 0, 0]

    house_num += 1
    visited[start_row][start_col] = True

    for i in range(len(dx)):
        if 0 <= start_row + dy[i] < len(house_map) and 0 <= start_col + dx[i] < len(house_map[start_row+dy[i]]):
            if house_map[start_row+dy[i]][start_col+dx[i]] == '1' and not visited[start_row+dy[i]][start_col+dx[i]]:
                dfs(house_map, visited, start_row+dy[i], start_col+dx[i])


N = int(sys.stdin.readline())

house_map = [sys.stdin.readline().rstrip() for _ in range(N)]
visited = [[False] * N for _ in range(N)]

group_count = 0
for i in range(len(house_map)):
    for j in range(len(house_map[i])):
        if house_map[i][j] == '1' and not visited[i][j]:
            dfs(house_map, visited, i, j)
            group_count += 1

            if house_num != 0:
                house_nums.append(house_num)
                house_num = 0

print(group_count)

house_nums.sort()
for house_num in house_nums:
    print(house_num)

어제 저녁 부스트캠프 AI Tech 최종 결과 발표가 났다.

결과는 정말 운이 좋게 합격 했다!!

부스트캠프같은 코딩 부트캠프는 처음 지원해보는 것이고, 코딩테스트도 그동안 해본 적이 없기 때문에 합격할 것이라고는 예상하지 못했다.

이번 포스팅에서는 부족하지만 부스트캠프 AI Tech를 지원한 과정들에 대해서 간단하게 작성하고자 한다. 후기를 처음 작성하는거라 필력이 안 좋아도 이해 부탁드립니다ㅋㅋㅋ

① 서류 작성

먼저 지원을 위해서는 간단한 프로필 작성과 자기소개서 작성을 해야한다.

자소서 작성이 가장 중요한 것 같은데 나는 부스트캠프 지원을 늦게 했기 때문에 지원 마감날 아침까지 밤을 새며 자소서를 작성했다.

시간이 부족하다보니까 내용을 많이 다듬기는 힘들었고, 그냥 최대한 솔직하게 작성했다. AI엔지니어와 관련된 내용, 딥러닝 학습을 많이 하지는 않았지만 혼자서 하면서 느꼈던 점, 내가 자연어처리를 하고 싶다는 내용 등등의 내용을 작성했다.

② BAT

모든 부스트캠프 지원자들은 BAT(부스트캠프 AI 테스트)를 응시해야 한다.

BAT문제를 풀 때 부정행위 방지를 위해 핸드폰을 통해 문제풀이 하는 모습과 노트북(컴퓨터) 화면을 실시간 녹화 해야했다. 휴대폰 거치대를 사용하지 않아서 최적의 각도를 찾느라 약간 애를 먹었는데 지금 생각해보면 그냥 휴대폰 거치대를 하나 사는게 마음 편할 것 같다.

부스트캠프 지원할 때 "자가진단테스트"라고 BAT관련해서 지원 전에 자신의 수준이 어느 정도인지 판단할 수 있도록 게시해 놓은 문제들이 있었는데, 내 생각에 BAT난이도는 자가진단테스트 문제들보다는 약간 더 어려운 것 같았다.

총 22문제 정도 나온 것 같았고, 문제 유형은 잘 기억이 나지는 않지만 계산 문제가 좀 있었고 파이썬과 관련된 문제도 있었다.

③ 1차 코딩테스트

가장 걱정되었던 부분이 바로 코딩테스트였다. solved.ac등급은 실버5정도로 낮은 편으로 알고리즘 문제를 잘 못 풀기도 하고, 문제를 푸는데 시간도 꽤 많이 걸렸기 때문이다. 알고리즘 문제 잘 푸시는 분들을 보면 문제를 보고 그리디, DP와 같이 어떤 유형의 문제인지 파악할 수 있다고 하는데, 나는 문제를 보면 간단한 그리디 정도만 파악할 수 있고 나머지들은 어떤 유형의 문제인지 파악하지 못하고 그냥 단순히 문제를 풀었다.

코딩테스트 준비를 하기 전에 다른 분들이 올려주신 이전 부스트캠프 코딩테스트 후기들을 살펴보았다. 후기들을 보니 1차 코딩테스트는 그렇게 어려운 문제가 나오지는 않은 것 같아서 백준에 있는 "단계별로 풀어보기"에서 실버 난이도, 프로그래머스에 있는 Level2 난이도를 가지는 문제들을 중점적으로 풀었다.

1차 코딩테스트는 총 6문제였고, 테스트 시간은 기억이 나지 않는다. 그리고 BAT처럼 화면을 녹화하지는 않았고, 구글검색과 같은 외부 자료 검색도 허용하였다. 언어는 C, C++, Java, JavaScript, Python정도 허용한 것 같았다.

6문제 중 앞에 3문제는 풀어왔던 백준 실버, 프로그래머스 Level 2정도의 난이도의 문제 같았다. 그래서 먼저 앞에 있는 3문제를 먼저 풀고 다음에 뒤에 3문제는 풀려고 시도하였는데 어려워서 못 풀었다.....

따라서 총 6문제 중 3문제를 풀었다.

④ 2차 코딩테스트

1차 코딩테스트를 반타작 했는데 운좋게 합격하고 2차 코딩테스트를 볼 수 있었다.

후기를 보니 2차 코딩테스트는 1차 코딩테스트보다 어렵다는 의견이 많았다. 하지만 그렇다고 백준 골드 문제를 풀기는 좀 힘들어서 더 다양한 유형의 문제들을 풀면서 대비하기로 하였다.

2차 코딩테스트는 총 8문제였고, 테스트 시간은 120분였다. 또한 BAT처럼 시험 보는 모습과 노트북 화면을 실시간 녹화해야했고, 외부 자료 검색은 전부 허용하지 않았다.

시험을 시작하는데 익숙한 문제들이 몇 개 보였다. 아마 1차 코딩 테스트와 같은 문제들이 몇 개 있었던 것 같다. 그래도 문제 수가 많았기 때문이 더욱 어려웠고, 전체적인 문제 난이도도 1차 코딩 테스트보다 더욱 올라간 것 같았다.

나는 먼저 초반 4문제를 풀었고, 5번 문제와 6번 문제를 풀려고 했는데 잘 풀리지 않았다. 5번 문제와 6번 문제 중 한 문제는 3개의 테스트 케이스가 자꾸 틀렸다고 나와서 해결하려고 노력하다가 그냥 제출했고, 나머지 한 문제는 5개의 테스트케이스 정도만 맞은 상태로 그냥 제출했다.

따라서 총 8문제 중 4문제를 풀었고, 부분점수도 있다면 아마 5문제 정도 푼 것 같다.

이렇게 선발 전형 과정들이 마무리 되었다. 코딩테스트를 준비하면서 부족한 점을 많이 느꼈다. 알고리즘 문제들에 대해서 앞으로 어떤 식으로 학습을 해야할지도 고민을 해야될 것 같다.

그래도 좋은 기회를 받을 수 있어서 감사드리고 부스트캠프가 빡세다고 해서 기대 반 걱정 반 하는 마음으로 기다리고 교육에 열심히 참여해야겠다.

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

대기중인 트럭과 다리를 지나가고 있는 트럭들은 큐에 저장하였고, 다리를 지나간 트럭들은 리스트에 저장하였다. while문에서는 먼저 지나가고 있는 트럭 중 끝에 도달한 트럭이 있으면 다리를 지나간 트럭 리스트로 옮긴다. 다리의 끝에 도달했는지 판단하는 조건은 트럭이 1초에 1만큼 움직이므로 (현재 초) - (트럭이 다리에 들어올 때 초) >= bridge_length로 하였다.

그리고 대기중인 트럭이 들어왔을 때 weight를 넘게 되면 다리를 지나가는 트럭 큐에 추가하지 않고, 넘지 않으면 추가한다. 추가하는 내용은 (트럭의 weight, 트럭이 다리를 진입할 때의 초)이다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    num_truck = len(truck_weights)
    
    waiting_truck = deque(truck_weights) # 대기중인 트럭
    passing_truck = deque() # 다리를 지나는 트럭
    passed_truck = [] # 다리를 지난 트럭
    
    weight_sum = 0
    while len(passed_truck) < num_truck:
        answer += 1
        
        if len(passing_truck) > 0:
            first_passing_truck = passing_truck.popleft()
            
            if answer - first_passing_truck[1] >= bridge_length:
                weight_sum -= first_passing_truck[0]
                passed_truck.append(first_passing_truck[0])
            else:
                passing_truck.appendleft(first_passing_truck)
        
        if len(waiting_truck) > 0:
            cur_weight = waiting_truck.popleft()
            weight_sum += cur_weight
        
            if weight_sum <= weight:
                passing_truck.append((cur_weight, answer)) # (weight, 진입한 시점의 초)
            else:
                weight_sum -= cur_weight
                waiting_truck.appendleft(cur_weight)
        
    return answer