[파이썬] 구현

구현

 

 

머릿속에 있는 알고리즘을 정확하고 빠르게
프로그램으로 작성하기

 

"피지컬로 승부하기" - 이것이 취업을 위한 코딩 테스트다 with 파이썬

 

코딩 테스트 유형 중 "구현"이란 말 그대로 구현하는 것이다. 정확히는 앞서 언급한 것처럼 "머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 것"이다. 코딩 테스트 문제를 풀기 위해서는 구현을 해야 하므로 구현 문제 유형은 모든 범위의 코딩 테스트 유형을 포함하는 포괄적인 개념이다.

 

어떤 문제를 해결하고자 할 때, 해당 문제를 "어떻게 풀어야 하는지?" 방법에 대한 고민을 하게 된다. 이 과정의 결과로 해결 방법이 떠올랐을 때, 그 문제를 "풀었다, 정답을 맞혔다."라고 할 수 있는가? 그렇지 않다. 머릿속의 과정을 프로그래밍 언어로 옮겨 구현을 하고 정답을 맞혔을 때, 문제를 풀었다, 정답을 맞혔다고 할 수 있다. 따라서 문제를 풀기 위해서는 언어의 정확한 문법을 알고 있어야 하고 해당 문제의 요구사항을 정확히 이행해야 한다.

 

"구현" 유형의 문제는 문제를 읽고 풀이를 대강 떠올리기는 쉽지만, 코드로 작성하는데 어려움이 있는 경우가 더러 있다. 개발을 할 때, '피지컬이 좋은 사람'이라는 말은 프로그래밍 언어를 사용하는데 능숙하고 어려움이 없고, 코드로 작성하는 속도가 빠른 사람을 말한다. 문제를 풀기 위한 아이디어는 떠올렸지만 시간 내에 구현하지 못하면 의미가 없다.

 

대체로 구현하기 어려운 문제들은 다음과 같다.

• 알고리즘은 단순하지만 코드의 길이가 상당한 경우
• 정답 출력 과정에서 특정 소숫점 자리를 다루는 경우
• 주어진 문자열을 파싱해야 하는 경우

대체로 사소한 문제 요구사항이 많을수록 구현이 까다로워진다. 실제로 코딩 테스트 문제를 연습하면서 많이 느꼈던 부분들이다. 문제를 읽고 풀이의 대한 방향성을 찾고 풀이를 진행하다 보면 어떤 순서대로 풀어야 할지, 코드가 길어져서 어느 부분에서 문제가 생겼는지, 정규표현식에 대한 이해가 부족해 정답을 출력하는데 어려움이 있던지 등등. 문제 풀이의 경험이 많은 사람들은 대체로 쉽게 느껴지는 유형일 수 있지만, 아직 부족한 초심자의 경우는 문법부터 익숙하지 않아 문제가 어렵게 느껴지게 된다. 문제를 풀며 순열과 조합을 만났을 때, itertools 라이브러리를 몰랐을 때 어떻게 구현해야 하는지, 막막한 생각만 떠올렸었다.

 

[파이썬] 파이썬 순열과 조합, permutations/combinations

 

다양한 문제를 풀어보고, 언어에 능숙함이 있는 고수의 경우와 달리 필자는 초심자이기 때문에 구현 문제를 만나면 당황스러울 때가 많다. 문제를 읽고 풀이의 방향성은 느낄 수 있지만 어떤 부분부터 작성해야 할지 몰라 답답하게 느껴지는 경우가 종종 있기 때문이다. 

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 책에서는 '완전 탐색'과 '시뮬레이션' 유형을 모두 "구현" 유형으로 묶어 설명한다.

 

• 완전 탐색 : 모든 경우의 수를 모두 계산하는 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 직접 수행하는 방법

구현 시 고려해야 할 메모리 제약 사항

C/C++, Java에서 정수형 종류에 따라 범위를 고민해야 하지만, 파이썬에서는 다음과 같이 자료형을 직접 지정할 필요가 없고

int a = 7

큰 수의 연산 또한 기본적으로 지원해주기 때문에 고려하지 않아도 된다.

 

리스트 크기

 

파이썬에서 여러 변수를 사용할 경우 리스트를 사용하게 되는데, 이때 제한사항을 고려해야 한다. 대체로 코딩 테스트에서는 128~512MB로 메모레를 제한하는데 종종 수백만 개 이상의 데이터를 처리해야 하는 경우가 있다. 이 경우에는 메모리 제한을 염두해 문제를 풀어야 한다.

 

데이터 개수(리스트 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

 

파이썬은 코드를 작성하는 것이 다른 언어에 비해 쉬운 편이지만, 데이터 처리량이 많을 때는 메모리 제한을 꼭 생각해야 한다. 리스트를 여럿 선언하고 그중 크기가 1,000만 이상이 되는 경우가 있다면 메모리 용량 제한에 걸리는 경우가 있다.

 

아직 코드를 작성하고 문제를 푸는데 실력이 좋지 못한 편이라 반복문을 자주 사용하는데 2중, 3중 반복문을 사용해 문제를 풀던 경우 메모리 제한으로 인해 실패했던 경우가 있다. 이전에 문제를 풀 때는 메모리 사용량에 대해 크게 고민해 보지 않았다. 사실 고민을 하지 않았다기보다는 신경 쓰지 않았다는 게 맞다. 제한에 걸리더라도 더 개선된 코드를 작성하기 어려웠고 문제를 풀기 급급했었다. 앞으로 문제를 풀 때, 처리해야 할 데이터의 양이 어느 정도 인지, 요구하는 메모리 제한 사항은 얼마나 되는지 인지하고 문제에 접근할 수 있도록 노력해야 한다.

 

채점 환경

 

시간 제한이 1초이고, 데이터 개수가 100만 개인 문제가 있다면 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용해 문제를 풀어야 한다.

 

N = 1,000,000일 때 Nlog2N은 약 20,000,000

 

구현 문제에 접근하는 방법

 

구현 문제 중 길이가 긴 것은 대체로 사소한 입력 조건 등을 명시해 둔 경우이다. 문제 길이가 길어 어렵게 느껴질 수 있지만 해당 문제를 푸는데 고차원적인 아이디어를 요구하지는 않는다. 오히려 언어 사용에 능숙함이 있고 문법에 익숙하다면 오히려 문제는 쉽게 풀린다.

 

문제 길이가 길어 어려워 보였지만 차근차근 이해를 하고, 문제에 적힌 그대로 구현해 주기만 하면 문제가 더러 있었다. 기본적인 아이디어만 생각할 수 있으면 되고, 말을 그대로 구현해 주기만 하면 된다. 문제 풀이에 실패했던 경우는 대부분 문제 속에 요구된 것을 놓쳤을 때였다. 꼼꼼히 읽고 요구사항을 모두 만족하는 코드를 작성할 수 있도록 유의만 해주면 된다.

 

---

 

그리디 알고리즘 예제

 

상하좌우

 

문제 설명

 

여행가 A는 N * N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 * 1 크기의 정사각형으로 나누어져 있다. 가장 왼 쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.

- L : 왼쪽으로 한 칸 이동

- R : 오른쪽으로 한 칸 이동

- U : 위로 한 칸 이동

- D : 아래로 한 칸 이동

이때 여행가 A가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1,1)의 위치에서 L 혹은 U를 만나면 무시된다.

N = 5이고, 움직임이 R, R, R, U, D, D인 경우를 살펴보자.

6개의 명렁에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1,1), (1,2), (1,3), (1,4), (2,4), (3,4)가 된다. 최종적으로 A가 도착하게 되는 곳의 좌표는 (3,4)이다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

 

입력 조건

 

- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)

- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)

출력 조건

 

- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.

 

 

입력 예시

 

- 5

- R R R U D D

 

출력 예시

 

- 3 4

 

문제 풀이

 

def solution(N, moves):
    x, y = 1, 1         # 시작 위치
    dx = [0, 0, -1, 1]  # 좌, 우, 상, 하
    dy = [-1, 1, 0, 0]  # 좌, 우, 상, 하
    move_type = ['L', 'R', 'U', 'D']

    for move in moves:
        for j in range(4):
            if move == move_type[j]:
                nx = x + dx[j]
                ny = y + dy[j]
        if nx < 1 or ny < 1 or nx > N or ny > N:    # x,y 좌표가 N*N을 벗어난 경우
            continue
        x = nx
        y = ny
    return x, y


N = int(input())
moves = input().split()
x, y = solution(N, moves)


print(x, y)

---

시각

 

문제설명

 

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 대 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

- 00시 00분 03초

- 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

- 00시 02분 55초

- 01시 27분 45초

입력 조건

 

첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

출력 조건

 

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

입력 예시

 

5

출력 예시

 

11475

 

문제 풀이

 

def solution(N):
    answer = 0
    for Hour in range(N+1):             # 0시 ~ N시
        for Minute in range(60):        # 0분 ~ 59분
            for Second in range(60):    # 0초 ~ 59초
                tmp = f"{str(Hour)}:{str(Minute)}:{str(Second)}" # HH:MM:SS 형태로 문자열 생성
                if "3" in tmp:  # tmp 문자열에 "3"이 포함된 경우 answer 증가
                    answer += 1
    return answer


N = int(input())
print(solution(N))

 

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

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

이것이 취업을 위한 코딩 테스트다 with 파이썬 를 통해 공부한 내용을 정리한 것입니다.