[코딩테스트] 구현

JY·2022년 5월 14일

목록 보기

1/2

구현

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기
구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함
언어의 문법을 잘 이해하는 것이 중요

구현 유형

완전 탐색: 모든 경우의 수를 주저 없이 다 계산
일반적으로 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 많을 때는 정상적으로 동작하지 않을 수 있음. (100만 개 이하일 때 사용하면 적절)
시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

cf) 구현이 어려운 문제
-> 알고리즘은 간단하지만 코드가 지나칠 만큼 길어지는 문제
-> 특정 소수점 자리까지 출력해야하는 문제
-> 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 파싱해야하는 문제 등

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

C/C++ 또는 자바에서는 정수 자료형에 따라 자료형 범위가 제한적
Python은 프로그래머가 직접 자료형을 지정할 필요가 없음
-> 매우 큰 수 연산 또한 기본적으로 지원
하지만 Python에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라 연산 결과가 달라질 수 있음을 유의
Python에서 리스트 사용 => 코딩 테스트의 메모리 제한 고려해야함.
- 대체로 코딩 테스트에서는 128~512 MB 메모리 제한
- 알고리즘 문제 중 큰 데이터를 처리해야하는 문제일 때 메모리 제한 염두
- 리스트를 여러 개 선언하고 그 중 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없음

채점환경

: 시간 제한이 1초이고, 데이터 개수가 100만 개인 문제가 있다면 시간복잡도 O(NlogN) 이내의 알고리즘 이용하여 문제를 풀어야 함
=> 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 후, 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측

** 코딩 테스트에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 알고리즘 또는 구현 문항. 논리적 사고력을 확인할 수 있는 가장 기본 난이도의 문제로 적합 => 합격 좌우 가능

Ex1) 상하좌우

여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 상,하,좌,우 방향으로 이동할 수 있으며 N X N의 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

sol) 시뮬레이션 유형, O(N)의 시간 복잡도 (이동 횟수에 연산 횟수 비례)

입력조건
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 $\leq$ N $\leq$ 100)
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 $\leq$ 이동횟수 $\leq$ 100)

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

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)

Ex2) 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

sol) 완전 탐색 유형, 모든 시각의 경우를 하나씩 모두 세서 풀기 (하루의 모든 초의 경우는 86,400개로 완전 탐색 알고리즘으로 수용 가능)
-> 매 시각을 문자열로 바꾼 후 문자열에 '3'이 포함이 되었는지 검사

입력조건
- 첫째 줄에 정수 N이 입력된다. (0 $\leq$ N $\leq$ 23)

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


h = int(input())  #시간 입력 받기

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)

Ex3) 왕실의 나이트

왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
Rule 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
이처럼 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. (행:1~8, 열:a~h)

sol) 나이트가 이동할 수 있는 이동 경로를 리스트에 넣고, 현재 위치에서 이동 경로를 더한 다음 8 X 8 좌표 평면에 있는지 반복문으로 확인

입력조건
- 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력조건
- 첫째 줄에 나이트가 이동할 수 있는 경우를 출력하시오.

input_loc = input() #현재 위치 입력받기
row = int(input_loc[1])
col = int(ord(input_loc[0])) - int(ord('a')) + 1

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

result = 0
for step in steps: #8가지 방향에 대해 이동가능한지 확인
    next_row = row + step[0]
    next_col = col + step[1]
    #이동 가능하다면 result 증가
    if next_row >=1 and next_row <= 8 and next_col >= 1 and next_col <=8:
        result += 1

print(result)

Ex4) 게임 개발

게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼이다.

Rule 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
            2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면,
             왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지
                 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
            3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는,
                 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때
                 뒤쪽 방향이 바다인 칸이라 뒤로 갈수 없는 경우에는 움직임을 멈춘다.

위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트 하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

sol) 시뮬레이션 문항, 별도의 알고리즘의 필요보다 문제에서 요구하는 내용을 오류 없이 성실히 구현만 할 수 있담녀 풀 수 있음.
방향을 설정하는 문제 유형 => dx, dy라는 별도의 리스트를 만드는 것이 효과적
2차원 리스트 선언 => 리스트 컴프리헨션 문법 사용

입력조건
- 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 $\leq$ N,M $\leq$ 50)
- 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A,B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값은 4가지가 존재한다. (0:북, 1:동, 2:남, 3:서)
- 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어있다. (0:육지, 1:바다)

출력조건
- 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

입력예시

4  4         # 4x4 맵 생성
1  1  0      # (1,1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1  1  1  1   # 첫 줄은 모두 바다
1  0  0  1   # 둘째 줄은 바다/육지/육지/바다
1  1  0  1   # 셋째 줄은 바다/바다/육지/바다
1  1  1  1   # 넷째 줄은 모두 바다

출력예시
3

n, m = map(int, input().split())  #N,M을 공백으로 구분하여 입력 받기

#방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]

#현재 캐릭터의 X, Y 좌표, 방향을 입력받기
x, y, direc = 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 direc #함수 바깥에서 선언된 전역변수이므로 global 사용
    direc -= 1
    if direc == -1:
        direc = 3

#시뮬레이션 시작
count = 1
turn_time = 0
while True:
     #왼쪽으로 회전
    turn_left()
    nx = x + dx[direc]
    ny = y + dy[direc]

    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[direc]
        ny = y - dy[direc]

        if array[nx][ny] == 0: #뒤로 갈 수 있다면 이동하기
            x = nx
            y = ny
        else: #뒤가 바다로 막혀있는 경우
            break
        turn_time = 0
print(count)

실전문제) 럭키 스트레이트

게임의 아웃복서 캐릭터는 필살기인 '럭키 스트레이트' 기술이 있다. 이 기술은 매우 강력한 대신 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다.
특정 조건 현재 캐릭터의 점수를 N이라 할 때 자릿수를 기준으로 점수 N을 반으로
나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한
값이 동일한 상황

현재 점수 N이 주어지면 럭키 스트레이트를 사용할 수 있는 상태인지 아닌지를 알려주는 프로그램을 작성하시오.

sol) 입력받은 정수형 데이터를 각 자릿수를 구분하여 합을 계산한다. 문자열에서 문자를 하나씩 확인한 후 정수형으로 변환한 후에 합 변수에 더한다.

입력조건
- 첫째 줄에 점수 N이 정수로 주어집니다. (10 $\leq$ N $\leq$ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어집니다. 예를 들어 자릿수가 5인 12,345와 같은 수는 입력으로 들어오지 않습니다.

출력조건
- 첫째 줄에 럭키 스트레이트를 사용할 수 있다면 "LUCKY"를, 사용할 수 없다면 "READY"를 출력합니다.

score = input() #점수 입력받기
length = len(score) #입력 받은 점수값의 자릿수
l_result = 0
r_result = 0

#왼쪽 부분 자릿수 합 구하기
for i in range(length//2):
    l_result += int(score[i])

#오른쪽 부분 자릿수 합 구하기
for i in range(length//2, length):
    r_result += int(score[i])

#왼쪽 부분과 오른쪽 부분의 자릿수 합이 동일한지 검사
if l_result == r_result:
    print("LUCKY")
else:
    print("READY")

나는 왼쪽 부분 자릿수 합과 오른쪽 부분 자릿수의 합을 각자 새로운 변수에 지정하여 비교함.
하지만 예시 답안에는 왼쪽 부분 자릿수 합은 result에 더하고 오른쪽 부분 자릿수 합은 result
에서 빼는 것을 이용하여 result가 0인지 아닌지를 이용함.
이렇게 되면 변수를 더 적게 사용할 수 있고, 코드도 한 줄 짧아지게 됨.

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

다음 포스트

[코딩테스트] 구현