[Algorithm] "구현"이란 무엇일까?

알고리즘

[Algorithm] "구현"이란 무엇일까?

Jay_J 2024. 6. 27. 08:38

알고리즘 문제를 풀다 보면 이 "구현"에 관련된 내용을 자주 접했을 것이다. 나도 올 여름 LG 코딩테스트에서 구현,DFS, 최단경로 등등의 문제가 나왔지만 알고리즘에 무지했던터라 어떤 문제가 "구현" 문제인지 알아내지 못했다. 하지만 리서치를 해보니, 대부분의 기업에서 가장 많이 출제하는 유형은 대부분 DFS / 구현 / 최단경로 / 완전탐색 이였다. 그래서 오늘은 도대체 이 "구현"이 뭔지 알고 넘어가 보도록 하겠다.

구현(Implementation)이란 무엇일까?

먼저, 프로그래밍적 관점에서 '구현' 이란 단순히 머릿속에 있는 알고리즘을 코드로 작성하는 것이다. 어떤 문제이건 간에 머릿속의 아이디어를 소스코드로 바꾸는 과정은 필수이므로 구현 문제의 유형은 포괄적인 개념이다.흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

그렇다면, 어떤 문제를 '구현하기 어렵다' 라고 할 수 있을까? 알고리즘은 간단한데 코드가 지나치게 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 또한 프로그래밍 문법을 제대로 모르거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀때 불리하다.

구현 시 고려해야 할 메모리 제약 사항
- C / C++에서 정수의 표현범위
  전통적으로 프로그래밍 언어에서 정수형(int)를 표현할 때는 int 자료형을 주로 사용하며, 이 자료형의 크기는 4바이트 이다. 자바의 int의 표현 범위는 -2,147,483,648 ~ 2,147,483,648이며, 이 범위 바깥의 숫자는 int로 표현 할 수 없고, long 자료형을 써야한다.
- 파이썬의 자료형과 리스트 크기
  반면, 파이썬에서는 프로그래머가 직접 자료형을 지정 할 필요가 없으며, 매우 큰 수의 연산도 기본적으로 지원한다.
  이제, 리스트 크기의 제약에 대해 알아보자. 파이썬에서 리스트를 사용 할 때 고려해야 할 사항이 있다. 바로 코딩 테스트의 메모리 제한이다. 대체로 코딩 테스트에서는 128~512MB의 메모리 제한을 두는데, 이럴 때는 메모리 제한을 염두에 두고 코드를 작성 해야한다. 파이썬에서는 정수를 사용할때 자바의 int와 같이 자료형을 명시 해줄 필요가 없지만, 내부적으로는 다음 표에서 보이는 것 만큼 메모리를 차지한다.

구현 문제에 접근하는 방법
보통 구현 유형의 문제는 사소한 입력 조건들을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁 먹기 보단, 문법에 익숙하다면 구현 문제도 손쉽게 풀어 낼 수 있다. 파이썬은 자바/C 와 달리 문자열 처리가 훨씬 간결하다. 기본적인 문법만 잘 알고 있어도 상대적으로 구현 문제를 쉽게 해결 할 수 있다. 이제 구현 문제의 대표적인 두 문제를 보고 이런게 구현 문제구나 하고 넘어가 보자.
- 예제 1) 상하좌우

이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례한다(O(n)). 코딩 테스트에서 가장 난이도가 낮은 1 ~ 2번 문제는 대부분 그리디 알고리즘이나 구현 문제이다. 이 두 유형이 논리적 사고력을 확인 할 수 있는 가장 기본 난이도의 문제로 적합하기 때문이다.

# N을 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

n을 입력받아 공간의 크기를 지정한다.
초기 위치 x, y는 (1, 1)로 설정된다.
이동 계획 plans는 공백을 기준으로 나눠서 리스트로 저장된다.

이동 방향 설정:
dx와 dy 리스트는 각 방향으로 이동할 때 x와 y 좌표의 변화를 나타낸다.
move_types 리스트는 이동 방향을 나타내는 문자열을 저장한다.

이동 계획 실행:
for plan in plans 루프를 통해 각 이동 계획을 하나씩 확인한다.
for i in range(len(move_types)) 루프를 통해 이동 방향과 매칭되는 경우 새로운 좌표 nx, ny를 계산한다.
계산된 좌표가 공간을 벗어나는 경우 (nx < 1 or ny < 1 or nx > n or ny > n) 해당 이동을 무시하고, 그렇지 않은 경우 이동을 수행한다.

결과 출력:
최종 좌표 (x, y)를 출력한다.

예제 2)

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

예제 2) 왕실의 나이트 - 가장 잘 알려진 기본적인 구현 문제이다.

- 이 문제의 접근 방식은 내가 지금까지 생각 해내지 못했던 방법이다. 우선 문제를 잘 살펴보면, 나이트는 두가지 경로로 움직일 수 있다고 한다. 그렇다면, 주어진 좌표에서 나이트가 이동 할 수 있는 경우의 수를 구하려면, 나이트의 이동 경로를 steps라는 변수에 넣어준다. steps 변수는 다음과 같이 초기화 될 수 있다.

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

현재 값을 기준으로 아래쪽과 오른쪽은 양수의 값을, 위쪽과 왼쪽은 음수의 값을 대입했다. 이렇게 미리 steps를 정해 놓으면(즉 이 steps리스트 안에 담긴 각각의 튜플들은 주어진 위치에서 뻗어 나갈 수 있는 모든 경우의 수 이며, 반복문을 통해 이 steps의 step들이 유효한지 검사하면 간단할 일이다.)

내가 생각해낸 pseudo code는 대략 다음과 같다.

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

#여기서 주어진 (x,y)좌표는 'coord'라고 칭하겠음
#기존 8x8의 프레임 사이즈는 'frame'이라고 칭하겠음

count = 0

for step in steps:
	if (coord + step) >= frame:
    	count += 1

return count

아래는 해설집에 나온 소스코드이다.

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

예제 3)

이 문제는 전형적인 시뮬레이션 문제이다. 별도의 알고리즘이 필요하다기 보다는 문제에서 요구하는 내용을 오류없이 성실하게 구현한다면 풀 수 있다는 특징이 있다. 하지만 문제가 길고 문제를 소스코드로 옮기는 과정이 쉽지 않다. 따라서 이러한 문제들은 반복된 연습을 통해 익숙해 지는 연습을 하는것이 가장 중요하다.

- 문제 풀이를 위해 다시 설명하자면, 일반적으로 방향을 설정하여 이동하는 문제라면 dx, dy라는 별도의 리스트를 만들어 방향을 정하는것이 효과적이다. 예를들어 다음의 답안 코드 예시는 현재 캐릭터가 북쪽을 바라보고 있을때는 북쪽으로 이동하기 위해 x와 y 좌표를 각각 dx[0], dy[0] 만큼 더한다. 다시 말해, 현재 위치에서 (-1, 0) 만큼 이동 시키는 것이다. 이처럼 위치들을 리스트에 미리 설정해놓고 반복문을 이용하면 모든 방향을 차례대로 확인 할 수 있다는 장점이 있다.

- 그리고 답안 코드를 보면 리스트 컴프리헨션을 사용해 2차원 리스트를 초기화 했다. 파이썬에서 2차원 리스트를 선언할때는 리스트 컴프레션이 효과적이라는것을 기억해 두자.

그렇다면, 리스트 컴프리헨션이란 무엇인가?

리스트 컴프리헨션은 파이썬에서 리스트를 간결하고 효율적으로 생성하기 위한 문법이다. 일반적으로 반복문과 조건문을 사용하여 리스트를 초기화하는 작업을 한 줄로 표현할 수 있게 해준다.

리스트 컴프리헨션을 사용하면 코드의 가독성을 높이고, 간결한 형태로 리스트를 생성할 수 있다. 예를 들어, 1부터 10까지의 숫자 중 짝수만 포함된 리스트를 생성하는 경우를 생각해보자.

기존의 방법으로는 다음과 같이 작성할 수 있다:

even_numbers = []
for i in range(1, 11):
    if i % 2 == 0:
        even_numbers.append(i)

위 코드는 짝수를 찾아 리스트에 추가하는 과정을 반복문과 조건문으로 구현한 것이다. 하지만 리스트 컴프리헨션을 사용하면 이 과정을 한 줄로 간단하게 표현할 수 있다:

even_numbers = [i for i in range(1, 11) if i % 2 == 0]

위 코드에서 `for i in range(1, 11)`은 1부터 10까지의 숫자를 반복하며, `if i % 2 == 0` 조건을 만족하는 경우에만 `i`를 리스트에 추가한다. 이처럼 리스트 컴프리헨션은 반복문과 조건문을 한 줄로 작성하여 리스트를 초기화하는 방법이다.

또 다른 예로, 이 문제와 같이 2차원 리스트를 초기화하는 경우를 살펴보자. 예를 들어, 3x3 크기의 2차원 리스트를 모두 0으로 초기화하는 경우를 생각해 보자.

기존의 방법으로는 다음과 같이 작성할 수 있다:

matrix = []
for _ in range(3):
    row = []
    for _ in range(3):
        row.append(0)
    matrix.append(row)

리스트 컴프리헨션을 사용하면 이 과정을 간단하게 표현할 수 있다:

matrix = [[0 for _ in range(3)] for _ in range(3)]

이처럼 리스트 컴프리헨션은 반복문과 조건문을 한 줄로 작성하여 리스트를 초기화하는 간결하고 효율적인 방법이다. 파이썬에서 리스트를 초기화할 때 리스트 컴프리헨션을 사용하면 코드의 가독성을 높이고, 작성하는 코드를 더 간결하게 만들 수 있다.

아래는 예제 3의 소스 코드이다.

n, m = map(int, input().split())

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

x, y, direction = map(int, input().split())
d[x][y] = 1

array = []
for i in range(n):
    array.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3

count = 1
turn_time = 0
while True:
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    else:
        turn_time += 1
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        if array[nx][ny] == 0:
            x = nx
            y = ny
        else:
            break
        turn_time = 0

print(count)

그래서 "구현"은 단순히 알고리즘을 코드로 변환하는 과정을 의미한다. 이 과정은 필수적이기 때문에 다양한 문제 유형에 적용될 수 있다. '구현' 문제는 문제를 해결하는 알고리즘이 비교적 간단하지만, 이를 정확하게 코드로 옮기는 과정에서 많은 주의가 필요하다. 특히 디버깅과 테스트가 중요한데, 이는 코드가 올바르게 작동하도록 하기 위해 필수적이다. '구현' 유형의 문제를 많이 풀어보면서 다양한 문제에 익숙해지는 것이 중요하다.

결론적으로, '구현' 문제는 알고리즘 문제를 풀기 위한 기본적인 단계이며, 이를 통해 프로그래밍 실력을 향상시킬 수 있다. 반복적인 연습과 다양한 문제를 풀어보는 것이 '구현' 문제에 능숙해지는 지름길이다. 꾸준한 연습을 통해 다양한 문제를 해결하는 능력을 키워나가자.

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬