[코드트리] 코딩테스트 준비 및 갭체크 후기

알고리즘은 항상 꾸준히 풀어야 하지만, 다른 것들이 몰려오면 놓치기 쉬운 부분인것 같다.

그러던 와중, "코드트리 청약 통장" 이라는 이벤트? 에 대해 알게 되어 참여해보게 되었다.

대학교때부터 제휴를 통해 곧잘 이용해왔던 서비스였기에, 편하게 접속해서 문제들을 한번씩 풀어보고자 한다.

 

우선 오늘은 실력을 체크하기 위한 "갭 체크"의 응시 후기와, 

내가 알고리즘 풀이할때 자주 사용되는 코드 스니펫? 라이브러리?들을 간략하게나마 정리해보고자 한다.

 

참고로 필자는 학부시절 C++로 알고리즘을 풀이하다가, 데이터 분야로 직무를 희망하며 Python으로 전환한 case이다.

혹시라도 파이썬으로 코딩테스트를 막 시작하려는 사람이 있다면,

"파이썬 알고리즘 인터뷰" 이 책을 매우 추천한다.

 

아래에 나오는 PPT 자료들은 필자가 본 블로그 포스팅을 모두 작성한 후,

이해를 돕기 위해 NotebookLM을 통해 생성하였음을 말씀드립니다.

 

 

격자 / 보드 문제 -  x,y ?  r,c? 

우선 필자는 수학을 좋아하기에 x,y를 좋아했었지만...

알고리즘을 풀이하며 사용하는 x y 는 그 방향이 헷갈리기에 꽤 고생했던 경험이 있었다.

이에 Row Column 으로 풀이시 변수를 고정하고자 노력했고, 아래와 같이 r,c로 활용하고 있다.

추가로, 격자나 정해진 조건(방문 불가 지점)등을 체킹하기 위한 in_range함수를 두어 사용한다. 

다만 python에서 함수 호출에 대한 오버헤드가 좀 있기에.. 제한 조건이 타이트한 경우에는 조건식으로 직접 사용하기도 한다.

 

또한 과거에는 drs, dcs와 같이 상하좌우 이동 방향에 대해 배열을 2개로 사용했었는데,

요즘은 directions와 같이 튜플로 묶어서 하나의 리스트로 관리하는게 더편한것 같다. 

이를 활용해 nr, nc (next row, next column)을 할당해서 활용한다.

 

예시 코드는 아래와 같다.

def in_range(r, c):
    return 0 <= r < n and 0 <= c < m

# 사용 시
if in_range(nr, nc):
    # 로직 수행

drs, dcs = [-1, 1, 0, 0], [0, 0, -1, 1]

for dr, dc in zip(drs, dcs):
    nr, nc = r + dr, c + dc
    
# 방향을 하나의 리스트로 관리 (상, 하, 좌, 우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    # ... 로직 수행

 + 단순히 r,c 좌표값만 다루는 경우가 아니라 해당 칸의 어떤 값이라던가, 우선순위와 같이 다른 값을 함께 관리해야하는 경우가 많다.

    그럴때는 tuple을 사용해서 활용하도록 하자. 

 

최소 / 최대값

문제를 풀다 보면, 최소/최대값을 구하는 과정에서 초기 첫 비교를 위해 C++의 INF와 같은 값을 설정해야 하는 경우가 왕왕 있다.

그러한 경우에 대해서 python에서 어떻게 처리하는지 알아보도록 하자. 

import sys
INF_MIN = -sys.maxsize

INF = float('inf')

# 충분히 큰 정수
INF = int(1e9)

 

일반적인 상황에서 필자는 sys.maxsize를 사용한다. 

그 이유는 int값이기에 정수형 연산에도 유리하고,

sys.maxsize는 Py_ssize_t의 최대값(2**63-1)이며, 이는 실제 문제에서 나올 어떤 값보다도 충분히 크기 때문에 유용하다고 판단했다.

 

float('inf')와 같은 경우에는 math.inf로도 사용할 수 있으며,

python은 int에 대해 오버플로우가 없으며,  float('inf')에 특정 값을 더해도  inf가 나오도록 산술이 정의되어 있다는 특징이 있다.

다만, float('inf') - float('inf')의 결과는 nan이 된다.

 

1e9과 같은 값을 활용하는 경우는 문제의 제약에 맞춰 발생 가능한 최대값보다 큰 값을 설정하는 경우인데,

잘못된 로직을 짜게 되면 INF의 역할을 못할 수 있기에 잘 활용해야 한다.

 

시뮬레이션

만약 격자에서 네모 박스의 숫자 합을 구해야 한다면, 파이썬에서는 아래와 같이 함수를 작성할 수 있다.

def rect_sum(r1,c1,r2,c2):
    return sum(
        grid[i][j]
        for i in range(r1,r2+1)
        for j in range(c1,c2+1)
    )

 

C++만 사용하던 사람이라면 엥?? 싶을수도 있겠지만,

파이썬에서는 사실 무척이나 자주 사용하는 Comprehension 방식이다.

 

dp유형의 문제에서 이중배열을 초기화할때도 자주 사용되는 패턴이기 때문에 잘 숙지해두도록 하자.

또한 보드를 초기화 해야 하는 상황에서는 아래와 같이 가능하다.

board = [[0]*n for _ in range(n)]

board = [
    [0 for _ in range(m)]
    for _ in range(n)
]

def clear_board():
    for i in range(n):
        for j in range(m):
            board[i][j] = 0

#기존 객체를 유지해야할 때
def clear_board():
#board[:] -> 기존 리스트의 주소값은 그대로 두고, 그 안의 내용물만 통째로 바꿈.
    board[:] = [[0]*m for i in range(n)]

3번째 방법이 가장 단순한? 평범한? 방법이라고 생각이 들지만, 첫번째 방법이 나는 "python스러운" 코드라고 생각한다. 

 

4번째 방식과 같은 경우는 함수 안에서 외부 리스트를 초기화할 때 사용된다.

BFS/DFS를 같은 그래프로 반복해서 돌리는 경우 이와 같은 방식을 통해 재사용 가능하다. 

다만, 코딩 테스트에서는 매번 새로 재할당을 해주는 방식이 가독성도 좋고, 충분히 빠른 경우가 많다.ㅎ 

그래도 필요한 경우가 있을 수 있으니 알아만 두도록 하자.!

 

 

보드의 특정 구역 내에서 원하는 값이 있는지 찾는 경우에는 어떻게 할 수 있을까? 

이중 for문을 통해 하나씩 비교할 수도 있겠지만, python의 any 함수를 통해 한줄로 작성할 수도 있다. 

(시간 복잡도나 내부 동작은 똑같다.)

 

any(iterable)는 낸부를 돌며 첫 True를 만나는 순간 즉시 종료후 값을 반환한다.

반대로 첫 False에서 종료 후 반환하는 all(iterable)도 있다.

아래는 any함수와 함께 위에서 언급한 comprehension 방식을 사용한것이다.

# 내부 값 검사
# def check_board():
#     for i in range(n):
#         for j in range(m):
#             if board[i][j] >= 2:
#                 return True
#     return False

def check_board():
	return any(val >= 2 for row in board for val in row)

 

 

추가로, 보드 내에서 두 사각형이 겹치는 구간이 있는지 검증해야하는 경우에는 아래와 같이 작성할 수 있다.

겹치는 조건보다, 겹치지 않는 조건이 더 단순하기에 이를 이용한것이다. 

예를 들어 r2 < r3인 경우는 하나의 직사각형이 다른 직사각형보다 완전히 위쪽에 존재함을 의미한다. 

def is_overlapped(r1, c1, r2, c2, r3, c3, r4, c4):
    # 한 직사각형이 다른 직사각형의 왼쪽, 오른쪽, 위쪽, 아래쪽에 있는 경우를 제외
    if r2 < r3 or r4 < r1 or c2 < c3 or c4 < c1:
        return False
    return True

 

배열(리스트) 회전하기

파이썬에서 리스트를 한칸 회전하고 싶다면 어떻게 할 수 있을까?

데이터 분석을 해서 인덱싱/슬라이싱 개념이 잡혀있는 사람들은 쉽게 유추해볼 수 있을 것이다.

리스트간 덧셈도 가능하기에, arr[1:] + arr[:1]과 같이 구현할 수 있을 것이다.

만약 변수 k만큼 회전을 한다면, k값이 len(arr)보다 클 수도 있으니 %를 활용하도록 하자.

 

다만 자주 사용하는 deque 에서 rotate()함수를 지원한다는 것을 알아두면 유용할것 같아 가져왔다.

rotate(k)과 같이 사용할 수 있으며, rotate 에서는 k값이 리스트 길이를 넘어가더라도 알아서 모듈러 처리를 해준다는 장점이 있다.

시간 복잡도는 O(N)의 시간이 걸리는 첫번째 방식에 비해 O(k)에 비례한다는 장점이 있다.

arr = [1, 2, 3]

# 왼쪽으로 한 칸 밀기: [2, 3, 1]
# index 1부터 끝까지 + index 0만 담은 리스트
arr = arr[1:] + arr[:1]

from collections import deque

arr = [1, 2, 3]
d = deque(arr)

# rotate(n): n이 음수면 왼쪽으로, 양수면 오른쪽으로 회전
d.rotate(-1)  # 왼쪽으로 1칸 -> deque([2, 3, 1])
# d.rotate(1) # 오른쪽으로 1칸 -> deque([3, 1, 2])

# 다시 리스트로 만들고 싶다면
result = list(d)

 

 

 

추가로 list 출력에 관해서..

프로그래머스와 같은 곳에서는 답을 return 하는 형식이기에 신경 쓸일이 잘 없긴 하지만,

출력에 있어 기본 리스트 출력 결과와 *를 사용한 방법에 따른 차이를 인지하도록 하자.

 

격자에서 한 칼럼의 값을 리스트로 추출하기

기본적으로 보드를 구현할때 board[r][c]와 같이, row 가 먼저 위치하고 column이 다음을 의미한다.

즉, 1번째 row 값들만을 연속적으로 보는것은 board[0]와 같이 가능하다는 말이다.

그렇다면, 1번째 column값들만을 연속적으로 보려면 어떻게 해야 할까? 

r1부터 r2까지의 c2 칼럼에 위치한 값을 보고 싶은 경우에, 아래와 같이 코드를 작성할 수 있다.

   col2 = [a[i][c2] for i in range(r1,r2+1)]

사실 이 코드를 C++ 의 일반적인 방식으로 풀어 쓴다면 그냥 말 그대로 조건에 맞춰 구현하였을 뿐,

특별한 함수가 사용되거나 하진 않았다.

다만, 아직 이러한 코드 스니펫을 보았을 때 한눈에 머릿속에 그려지지 않거나 익숙치 않은 느낌이 든다면

이는 pythonic한 코드가 아직 어색하다는 뜻일수도 있기에, 친숙해지도록 노력해보자.

 

위에서 언급한 영역합 구하기와 특정 열 추출 코드를 복습해보자.

 

특정 범위 원소 제거

리스트에서 특정 범위의 값들만을 해당 리스트에서 제거하고 싶은 경우가 충분히 있을 수 있다.

이러한 경우 슬라이싱을 통해 list[a:b] = X와 같이  삭제/교체/삽입등을 할 수 있는데,

제거하고 싶은 경우에 대해서는 del 을 사용하는게 가독성이 좋다.

 

둘다 뒤쪽의 원소를 앞으로 당겨야 하기에 시간복잡도는 둘 다 O(N)이다.

만약, 큰 리스트의 앞쪽을 자주 제거하는 경우에는 collections.deque을 활용하는게 유리하다.

del blocks[a:b]
# blocks[a:b] = []

 

 

 

중력 적용

보드에서 중력이 적용되는 경우가 있다! ㅋㅋㅋ..

예를 들어 0인 칸들은 모두 삭제가 되고  더 위에 있던 값들이 아래로 떨어지는. 그런 경우이다.

이러한 경우 풀이법이 2가지가 있는데, 

한 열씩 각 행을 보며 0이 아닌 값들을 temp에 저장하고, 모두 0으로 초기화한 후 다시 채우는 방식이다.

이는 comprehension에서 조건문을 넣어 0이 아닌 값만을 뽑아 내고, 리스트간 덧셈으로 더 깔끔하게 구현할 수 있다.

temp를 활용하게 되면 최악에 O(N^2)이 되며, comprehension 방식은 O(N)으로 가능하다.

 

코드는 아래와 같다.

def apply_gravity():
    # n: 행의 개수, m: 열의 개수
    for j in range(m):  # 각 열(Column)에 대해 반복
        # 1. 현재 열에서 0이 아닌 숫자만 아래서부터 위로 읽으며 추출
        temp = []
        for i in range(n - 1, -1, -1):
            if grid[i][j] != 0:
                temp.append(grid[i][j])
        
        # 2. 열을 일단 모두 0으로 초기화 (또는 뒤에서부터 채우기)
        for i in range(n - 1, -1, -1):
            # temp에 숫자가 남아있다면 순서대로 채움
            if temp:
                grid[i][j] = temp.pop(0)
            else:
                grid[i][j] = 0  # 남은 윗부분은 비워둠
                
# 특정 열을 리스트로 뽑았다고 가정: col = [1, 0, 2, 0, 3]
# 0을 모두 제거
col = [val for val in col if val != 0]

# 부족한 만큼 앞에 0을 채워넣음 (중력 적용 완료)
# n은 원래 열의 높이
col = [0] * (n - len(col)) + col

 

 

 

이번 포스팅에서는 격자나 시뮬에 관한 내용이 주로 있었던거 같은데,

코드트리에서 진행한 갭체크 결과 내가 백트래킹 부분이 취약하다는 점을 알 수 있었다.

이처럼 불안정한 알고리즘 부분들이 어떤 포인트인지 알 수 있어 좋았다.

다음에 백트래킹 부분의 문제들을 좀 더 다루어 보도록 하겠다.

 

---

 

Codetree: Master Coding Interviews - Data Structures & Algorithms

 

파이썬 알고리즘 인터뷰 | 박상길 - 교보문고