[파이썬] 구현
미음제
·2022. 3. 20. 17:54
구현
머릿속에 있는 알고리즘을 정확하고 빠르게
프로그램으로 작성하기
"피지컬로 승부하기" - 이것이 취업을 위한 코딩 테스트다 with 파이썬
코딩 테스트 유형 중 "구현"이란 말 그대로 구현하는 것이다. 정확히는 앞서 언급한 것처럼 "머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 것"이다. 코딩 테스트 문제를 풀기 위해서는 구현을 해야 하므로 구현 문제 유형은 모든 범위의 코딩 테스트 유형을 포함하는 포괄적인 개념이다.
어떤 문제를 해결하고자 할 때, 해당 문제를 "어떻게 풀어야 하는지?" 방법에 대한 고민을 하게 된다. 이 과정의 결과로 해결 방법이 떠올랐을 때, 그 문제를 "풀었다, 정답을 맞혔다."라고 할 수 있는가? 그렇지 않다. 머릿속의 과정을 프로그래밍 언어로 옮겨 구현을 하고 정답을 맞혔을 때, 문제를 풀었다, 정답을 맞혔다고 할 수 있다. 따라서 문제를 풀기 위해서는 언어의 정확한 문법을 알고 있어야 하고 해당 문제의 요구사항을 정확히 이행해야 한다.
"구현" 유형의 문제는 문제를 읽고 풀이를 대강 떠올리기는 쉽지만, 코드로 작성하는데 어려움이 있는 경우가 더러 있다. 개발을 할 때, '피지컬이 좋은 사람'이라는 말은 프로그래밍 언어를 사용하는데 능숙하고 어려움이 없고, 코드로 작성하는 속도가 빠른 사람을 말한다. 문제를 풀기 위한 아이디어는 떠올렸지만 시간 내에 구현하지 못하면 의미가 없다.
대체로 구현하기 어려운 문제들은 다음과 같다.
- 알고리즘은 단순하지만 코드의 길이가 상당한 경우
- 정답 출력 과정에서 특정 소숫점 자리를 다루는 경우
- 주어진 문자열을 파싱해야 하는 경우
대체로 사소한 문제 요구사항이 많을수록 구현이 까다로워진다. 실제로 코딩 테스트 문제를 연습하면서 많이 느꼈던 부분들이다. 문제를 읽고 풀이의 대한 방향성을 찾고 풀이를 진행하다 보면 어떤 순서대로 풀어야 할지, 코드가 길어져서 어느 부분에서 문제가 생겼는지, 정규표현식에 대한 이해가 부족해 정답을 출력하는데 어려움이 있던지 등등. 문제 풀이의 경험이 많은 사람들은 대체로 쉽게 느껴지는 유형일 수 있지만, 아직 부족한 초심자의 경우는 문법부터 익숙하지 않아 문제가 어렵게 느껴지게 된다. 문제를 풀며 순열과 조합을 만났을 때, itertools 라이브러리를 몰랐을 때 어떻게 구현해야 하는지, 막막한 생각만 떠올렸었다.
다양한 문제를 풀어보고, 언어에 능숙함이 있는 고수의 경우와 달리 필자는 초심자이기 때문에 구현 문제를 만나면 당황스러울 때가 많다. 문제를 읽고 풀이의 방향성은 느낄 수 있지만 어떤 부분부터 작성해야 할지 몰라 답답하게 느껴지는 경우가 종종 있기 때문이다.
이것이 취업을 위한 코딩 테스트다 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
구현 문제에 접근하는 방법
구현 문제 중 길이가 긴 것은 대체로 사소한 입력 조건 등을 명시해 둔 경우이다. 문제 길이가 길어 어렵게 느껴질 수 있지만 해당 문제를 푸는데 고차원적인 아이디어를 요구하지는 않는다. 오히려 언어 사용에 능숙함이 있고 문법에 익숙하다면 오히려 문제는 쉽게 풀린다.
문제 길이가 길어 어려워 보였지만 차근차근 이해를 하고, 문제에 적힌 그대로 구현해 주기만 하면 문제가 더러 있었다. 기본적인 아이디어만 생각할 수 있으면 되고, 말을 그대로 구현해 주기만 하면 된다. 문제 풀이에 실패했던 경우는 대부분 문제 속에 요구된 것을 놓쳤을 때였다. 꼼꼼히 읽고 요구사항을 모두 만족하는 코드를 작성할 수 있도록 유의만 해주면 된다.
그리디 알고리즘 예제
상하좌우
문제 설명
입력 조건
출력 조건
입력 예시
출력 예시
문제 풀이
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)
시각
문제설명
입력 조건
출력 조건
입력 예시
출력 예시
문제 풀이
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 파이썬 를 통해 공부한 내용을 정리한 것입니다.
'Developer > Python' 카테고리의 다른 글
[파이썬] DFS/BFS(깊이 우선 탐색, 너비 우선 탐색) (0) | 2022.04.21 |
---|---|
[파이썬] 그리디(Greedy) 알고리즘 (0) | 2022.03.11 |
[파이썬] 파이썬 리스트 컴프리헨션 / 프로그래머스 메뉴 리뉴얼 (2) | 2022.01.13 |
[파이썬] 파이썬 heapq(힙큐) / 프로그래머스 더 맵게 (0) | 2022.01.11 |
[파이썬] 몫과 나머지 (0) | 2022.01.03 |