이것이 코딩테스트다 3일차 - 구현

1. 구현이란?

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

Problem -> Thingking -> Solution

사실 문제 해결 분야에서 구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제‘를 의미한다.

피지컬이 좋다 : 프로그래밍 언어의 문법에 능숙하고 코드작성속도가 빠른 사람
따라서 구현은 피지컬을 요구하는 문제라고 할 수 있다.

구현하기 어려운 문제란?

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 (파싱을 해야하는) 문제 등

파이썬으로 N개의 원소가 들어있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우를 구해야하는 문제는 어떻게 풀까?

• 인덱스만 다르면 다른 원소로 쳐준다면 뭐 그냥 N*(N-1)…*(N-(R-1))
• 인덱스가 달라도 동일한 원소면 같은 원소로 친다면, 중복을 제거하는 세트로 만들기, 그 다음 (S=len(Set) 일 때) S*(S-1)*…*(S-(R-1))

Itertools 같은 표준 라이브러리로 쉽게 짜는 방법이 있다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결방법


이 책에서는 완전탐색, 시뮬레이션 유형도 구현으로 묶어서 다루고 있음

• 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제유형

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

(c나 c++관련 내용은 필기하지 않았음)

파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없다.
매우 큰 수의 연산 또한 기본으로 지원한다.
따라서 정수형 변수의 연산 때문에 머리 아프게 고민해야 할 일은 거의 없다.
다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다.

파이썬 리스트 크기

여러개의 변수를 사용할 때는 리스트를 이용한다. 고려해야 할 것은 메모리 제한이다.
대체로 코딩테스트의 메모리 제한 : 128~512MB
알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다.
파이썬 내부에서 int자료형 데이터의 개수에 따른 메모리 사용량
1,000개당 : 4KB
1,000만 개 : 40MB

구현상 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하자
(흠.. 어떤 상황에서 메모리를 신경 써야 될까..시간 신경 쓰기에도 딸려용..)
리스트를 여러 개 선언하고, 그 중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다. 하지만 이런 문제는 드물다.(입출력 때문에 출제자도 번거롭다) 빠른 입출력을 위한 테크닉들이 필요에 따라 사용되기는 한다.
일반적인 코딩테스트에서는 뭐 이 정도만 기억해도 된다.

(메모리 사용량은 렘 사용량을 말하는 거 겠지? 거의 단순히 데이터의 개수관련..?)

채점환경

출제자가 매우 빠르게 동작하는 프로그램을 원한다면 시간 제한은 더욱 짧다.
보통 코딩테스트 환경에는 채점시스템의 시간 제한 및 메모리 제한 정보가 다음처럼 적혀있다.

• 시간 제한 : 1초
• 메모리 제한 : 128MB

일반적으로 코딩테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만번의 연산을 수행한다고 하면 크게 무리가 없다.
예를들어 시간제한이 1초이고 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의 알고리즘을 사용하여 문제를 풀어야 한다. (100만*20)

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴편이다. 그러나 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다. 기본문법만 알아도 된다!

(실무에서 파이썬으로 프로그램을 개발할 때는 GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학문제를 풀 때는 C언어로 작성된 파이썬 코어 소프트웨어가 동작한다. )
Pypy3을 선택하면 파이썬 3과 동일한 코들를 제출하지만 실행 시간을 줄일 수 있다.
삼전은 사용중. 특히 반복문이 많을 수록 차이가 난다. 대략 1초에 2000만~1억번 정도의 연산을 처리할 수 있다.

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 카카오 공채 때 API개발 문제가 출제, 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. BUT파이썬은 쉽다

2. 구현 문제

상하 좌우

출발은 늘 (1,1)에서.
1. 가로세로가 N인 좌표가 주어진다
2. R,L,U,D가 적힌 계획표가 주어진다
마지막에 도착하는 좌표는?

n = int(input())
list = input().split() #리스트로 반환
# 아예 계획서를 받아서 숫자로 만들어버리는 방법은 안되나,,?
# 일단 다 if문으로 작성해버리는 방법

coordinate=[1,1]

for i in list : 
    x = coordinate[0]
    y = coordinate[1]
    if i == "R" : 
        x+=1
    elif i =="L" : 
        x-=1
    elif i =="U" : 
        y-=1
    else : 
        y+=1
    
    if not (1<=x<=5 and 1<=y<=5) : 
        continue
    coordinate[0] = x
    coordinate[1] = y
    
print (coordinate[0],coordinate[1])    

문제 해설

• 일단 나는 시간 복잡도를 생각하지 못했다. n이 이동 횟수라고 했을 때 다행히 n이 아무리 커도 100이기 때문에 시간복잡도는 넉넉하다. 4n이라서 O(n)이다.
• 이 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시큘레이션 유형으로 분류된다.

모범답안 : 다음에도 써먹을 코드 냠
(계획서를 받아서 숫자로 반들어버리는 방법이 요거일 듯!)

n = int(input())
plans = input().split()
x,y=1,1

#이동방향을 세가지 리스트로 나눠서 저장한다. 
dy = [0,0,-1,1]
dx = [-1,1,0,0]
move_types = ["L","R","U","D"]

#이동 계획을 하나씩 확인
for plan in plans : #리스트에서 하나씩 꺼내서
    for i in range(len(move_types)) : #move_types와 비교
        if plan == move_types[i] : #동일한 것에 대해 dx,dy 만큼 이동
            nx = x+dx[i]
            ny = y+dy[i]

#공간을 벗어나는 경우 무시는 코드 동일
    if not(1<=nx<=5 and 1<=ny<=5) : 
        continue
#이동수행
    x,y = nx, ny

print(x,y)