크래프톤 정글 회고: 1주차

정글 회고 목차

Week 0
Week 1

1주차

본격적으로 정글이 시작됐다.

1주차부터 3주차까지는 알고리즘과 문제 풀이에 집중하는 주차들이다. 물론 이 와중에 Computer Science: A Programmer’s Perspective(이하 CS:APP)을 읽으며 컴퓨터 구조와 운영체제에 대해서도 학습하지만, 코치님들이 직접 알고리즘에 집중하라고 한 만큼 비중은 전자가 높다고 보면 된다.

파이썬으로 푸는 것이 과제였는데, 백준 문제들을 몇 개 풀어본 경험은 있었지만, 단순한 문제 몇 개였어서 그 방식에 대해 학습할 필요가 있었다.

우선 파이썬으로 문제를 푸는 데 주의해야 할 점! 이건 내가 추후에도 깜빡할 수도 있으니 여기에 기록해두겠다.

#input()대신 sys.stdin.readline()
import sys
input = sys.stdin.readline
#input을 대체함으로써 편하게 이하부터는 input()으로 사용 가능

#재귀함수가 있는 경우, 최대 재귀 깊이 설정 
import sys
sys.setrecursinlimit(10**6)
#DFS같은 경우에는 재귀 깊이를 설정해주어야 런타임 오류가 뜨는 경우를 방지할 수 있다

그리고 정글에 있을 때는 생각하지 못 했지만 있는 줄도 몰랐다 스터디를 하면서 스터디원 만석님이 파이써닉(Pythonic)한 문법에 대해 설명해주었다. 그 중 참고할 만한 것도 같이 정리하겠다.

아래는 지금까지도 내가 자주 써왔던 문법이다.

animals =  ['cat','dog','moose']
for i in range(len(animals)):
    print(i, animals[i])

C와 자바스크립트가 파이썬보다 상대적으로 익숙하기 때문에 저러한 문법을 써왔는데, 파이썬에서는 다음과 같이 enumerate함수를 사용한다고 한다.

animals =  ['cat','dog','moose']
for i, animal in enumerate(animals):
    print(i, animal)

인덱스가 필요 없는 경우에는 다음과 같이 써준다:

animals =  ['cat','dog','moose']
for animal in animals:
    print(animal)

여튼, 1주차의 문제 주제들은 배열, 반복문과 재귀함수, 정렬, 완전 탐색, 이분 탐색, 분할 정복, 스택, 큐, 해시 등이 있었다. 여기에 추가적으로 단순 수학 문제들도 있었다. 몇 가지 문제들은 접근 자체가 어려웠지만, 적어도 저번 주의 미니 프로젝트보다는 많이 편했기 때문에 상대적으로 괜찮았다.

코어타임

코어타임 때는 각자 키워드를 나눠서 학습하고 팀원들에게 공유하는 방식으로 했다. 추가로, 문제들을 각자 풀고 서로에게 설명도 하여 본인의 학습 진도를 파악하기로 했다. 1주차 키워드는 앞서 말한 알고리즘들이었기에, 서로 공유하고 수도코드를 보여주며 문제풀이가 더 용이하도록 했다.

문제

문제들을 복습 차원에서 몇 가지 다시 풀어보고자 한다.

달팽이는 올라가고 싶다

import sys
input = sys.stdin.readline
a,b,v = map(int,input().split())
k = (v-b)/(a-b)

print(int(k) if k == int(k) else int(k)+1)

종이 자르기

import sys
input = sys.stdin.readline

h, v = map(int, input().split())
cuts = int(input())
hors = [0, v]
vers = [0, h]

for i in range(cuts):
    direction, number = map(int, input().split())
    if direction:
        vers.append(number)
    else:
        hors.append(number)

hors.sort()
vers.sort()

hval = 0 
for i in range(1, len(hors)):
    hval = max(hval, hors[i] - hors[i-1])

vval = 0
for i in range(1, len(vers)):
    vval = max(vval, vers[i]-vers[i-1])

print(hval*vval)

생각보다 긴 문제였다. 자름이 없는 구간 중 가장 큰 구간을 가로 세로에서 각각 구하여 이를 곱해 면적을 찾으면 됐다.

Z

import sys
input = sys.stdin.readline

N, r, c = map(int, input().split())

def recursion(x, y, N):
    global count
    if N == 0:
        return

    half = 2 ** (N - 1)
    
    if x < half and y < half: 
        recursion(x, y, N - 1)
    elif x < half and y >= half:  
        count += half * half
        recursion(x, y - half, N - 1)
    elif x >= half and y < half:  
        count += 2 * half * half
        recursion(x - half, y, N - 1)
    else: 
        count += 3 * half * half
        recursion(x - half, y - half, N - 1)

count = 0
recursion(r, c, N)
print(count)

어려웠다… 분할정복 부분에 약점이 있는 것 같다. 해당 문제는 다시 한 번 풀어보아야겠다.

마치며

문제는 더 풀어야겠다. 까먹은 게 많다는 것을 느껴서 이 회고의 목적은 달성했다고 생각한다.

---