[이것이 취업을 위한 코딩테스트다 with 파이썬] Ch.4 구현

1. 아이디어를 코드로 바꾸는 구현

피지컬로 승부하기 

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

  - (알고리즘에서의) 구현 : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

  - 문법이 능숙하고 코드 작성 속도가 빠른 사람이 유리

 

 2) 까다로운 구현의 문제

   - 사소한 설정이 많을 수록 코드 구현 까다로움

• 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야하는 문제
• 문자열이 입력으로 주어질 때 → 한 문자 단위로 끊어서 넣는 문제

  - 라이브러리 사용 경험 있어야 함

  - 프로그래밍 문법 정확하게 숙지하기

 

 3) 구현의 '종류'

   - 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법

   - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 방법

 

 

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

 1) C/C++에서 변수의 표현 범위

   - 정수형 종류 : int형 사용(4바이트) → long long형 사용(8바이트) → BigInteger 클래스 구현 및 이용(가변적)

  → 파이썬에서는 매우 큰 수의 연산도 기본으로 지원, 정수형 자료 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 됨

  → 파이썬 실수형 변수는 유효숫자에 따라서 연산결과가 원하는 값이 안나올 수 있음

 

 2) 파이썬에서 리스트 크기

  - int 자료형 데이터의 개수에 따른 메모리 사용량

• (리스트 길이)1,000 → (메모리 사용량) 4KB
• (리스트 길이) 1,000,000 → (메모리 사용량) 4MB
• (리스트 길이) 10,000,000 → (메모리 사용량) 40MB

  - 데이터 처리량이 많을 때에는 메모리 제한 고려하기

    → 크기가 1,000만 이상인 리스트, 용량 제한으로 문제 풀 수 없게 되는 경우도 있음

    → 일반적인 코테는 메모리 사용량 제한 > 사용 메모리

 

 

채점 환경

 - 파이썬은 C/C++에 비해 2배의 수행시간 주어지기도 함

 - 일반적인 기업 코테 환경 : 1초에 2,000만 번의 연산 수행한다고 가정하면 크게 무리 없음

 - 시간 제한 , 데이터 개수 확인 → 어느 정도 시간 복잡도 알고리즘으로 작성해야 풀 수 있을지 예측

 

 

구현 문제에 접근하는 방법

 - (일반적인) 구현 문제 : 사소한 입력 조건을 문제에서 명시, 문제의 길이가 꽤 긴 편

    → 문법이 익숙하면 쉽게 풀 수 있음

    → 구현 난이도 : 쉬운편, 프로그램 실행 시간 : 긴 편

 - Pypy3 : 실행속도 빠름, 반복문이 많을 수록 일반 실행 코드보다 더 빠름
    → Python과 Pypy3 지원 시, Pypy3 사용하기

 

 

📌예제 4-1) 상하좌우

 

✔️문제

N * N인 정사각형 공간에서 여행 계획서에 따라 움직임

 

L : 왼쪽으로 한 칸 이동

R : 오른쪽으로 한 칸 이동

U: 위로 한 칸 이동

D : 아래로 한 칸 이동

 

이 때, 여행자가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시됨

 

✔️입력조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다.( 1<= N <= 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1<= 이동횟수 <= 100)

 

✔️출력조건

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

 

✔️입력예시

5

R R R U D D

 

✔️출력예시

3 4

 

✔️나의 문제 풀이

 - 각 위치별 갈 수 없는 구간 (0 이하, n+1 이상)을 넘을 시 1 or n으로 돌려놓음

n = int(input())
plan = list(input().split())

x = 1
y = 1

for i in plan:
  if i == 'L':
    y -= 1
    if y == 0:
      y = 1
      
  elif i == 'R':
    y += 1
    if y == n+1:
      y = n
      
  elif i == 'U':
    x -= 1
    if x == 0:
      x = 1
      
  elif i == 'D':
    x += 1
    if x == n+1:
      x = n

print(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]
  # 공간을 벗어나는 경우 무시 = x,y 업데이트 안 함
  if nx < 1 or ny < 1 or nx > n or ny > n:
    continue
  # 이동 수행
  x, y = nx, ny

print(x,y)

 

✔️나의 문제풀이와 책의 문제풀이 비교

 - 나는 일대일 대응하여 문제를 해결, 책은 xy 짝을 짓고 계획과 연결시켜 계산

 - 나는 하나씩 공간 조건 게시, 책은 한꺼번에 검사하기

 - for문과 if문에서 조건 성립이 안될 때, continue 생각하기

---

📌예제 4-2) 시각

✔️문제

정수 N이 입력되면 00시 00분 00초 ~ N시 59분 59초까지의 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기

 

✔️입력조건

첫쨰 줄에 정수 N이 입력된다.

 

✔️출력조건

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

 

✔️나의 문제 풀이

 - 시간, 분, 초에 3이 들어가 있는 것 확인 

n = int(input())
list_3 = [3,13,23,30,31,32,33,34,35,36,37,38,39,43,53]

ans = 0
for hour in range(n+1):
    for minute in range(60):
        for second in range(60):
            if second in list_3 or minute in list_3 or hour in list_3:
                ans += 1
print(ans)

 

✔️책의 문제 풀이

 - 완전 탐색 : 가능한 경우의 수를 모두 검사해보는 탐색 방법

• 비효율적인 시간 복잡도, 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있음
• 확인해야 할 데이터 개수가 100만 개 이하일 때 완전 탐색 사용

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)

 

✔️나의 문제풀이와 책의 문제풀이 비교

 - 나의 문제풀이는 3이 들어가는 숫자 다 넣어서 비교

 - 숫자를 str로 바꿔 3을 검증하는 방법 기억하기

---

📌2. 왕실의 나이트

✔️문제

행복 왕국 왕실 정원 8*8 좌표 평면(행 위치 - 1~8, 열 위치 - a~h)

 

나이트는 이동할 때 L자 형태로만 이동 가능, 정원 밖으로는 나갈 수 없다. 특정한 위치에서 2가지 경우로 이동 할 수 있다.

 1) 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기( →→↑, 화살표 반대로도 가능)

 2) 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기(↑↑→, 화살표 반대로도 가능)

 

나이트가 이동할 수 있는 경우의 수 출력하기.

 

✔️입력 조건

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

 

✔️출력 조건

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

 

✔️입력 예시

a1

 

✔️출력 예시

2

 

✔️나의 문제풀이

 - 문자열 입력 받고, 문자열 앞뒤 쪼개서 숫자로 변환

 - 이동할 수 있는 두 가지 경로 따로 저장 [1)은 dx_1, dy_1으로 / 2)는 dx_2, dy_2로 저장]

 - for문 안에서 격자 벗어나지 않게 제한값 설정

# 입력 받기
point = input()

# 문자열 숫자로 변환
if point[0] == 'a':
  x = 1
elif point[0] == 'b':
  x = 2
elif point[0] == 'c':
  x = 3
elif point[0] == 'd':
  x = 4
elif point[0] == 'e':
  x = 5
elif point[0] == 'f':
  x = 6
elif point[0] == 'g':
  x = 7
elif point[0] == 'h':
  x = 8

# y저장
y = int(point[1])

# 정답 저장 공간
cnt = 0

# 이동할 수 있는 경로 저장
dx_1 = [2,2,-2,-2]
dy_1 = [-1,1,-1,1]

dy_2 = [-2,-2,2,2]
dx_2 = [1,-1,1,-1]

# dx_1, dy_1 이동경로 cnt
for i in range(4):
  ans_x = x + dx_1[i]
  ans_y = y + dy_1[i]
  if ans_x < 1 or ans_x > 8 or ans_y < 1 or ans_y > 8:
    cnt = cnt
  else:
    cnt += 1

# dx_2, dy_2 이동경로 cnt
for i in range(4):
  ans_y = y + dy_2[i]
  ans_x = x + dx_2[i]
  if ans_x < 1 or ans_x > 8 or ans_y < 1 or ans_y > 8:
    cnt = cnt
  else:
    cnt += 1

# 최종 답
print(cnt)

n = input()

x = int(ord(n[0]) - 96)
y = int(n[1])
new_x, new_y = 0,0
ans = 0

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

for i in range(8):
    new_x = x + dx[i]
    new_y = y + dy[i]

    if new_x < 1 or new_x > 8 or new_y < 1 or new_y > 8:
        continue
    else:
        ans += 1
print(ans)

 

✔️책의 문제풀이

 - 입력받은 문자를 ord()를 이용하여 아스키코드 변환 후 사용

파이썬 아스키코드 변환 함수 ord( ), chr( ) (Python)

 - 값 8개 한꺼번에 저장 후 움직임

• 1) dx,dy 형태 / 2) steps 변수 형태 자주 사용 

# 현재 나이트의 위치 입력받기
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)

 

✔️나의 문제풀이와 책의 문제풀이 비교

 - 아스키코드 변환하여 풀이(아스키코드 변환법 익히기)

 - 한꺼번에 8가지 방향 저장하기

 - 내가 쓴 소스코드(dx,dy)도 많이 이용되므로 두 가지 다 익히기

---

📌3. 게임 개발

✔️문제

N * M 크기의 직사각형. 각각의 칸은 육지 또는 바다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A,B) → A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수.

 

캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.

 

캐릭터 설정 메뉴얼은 다음과 같다.

 1) 현재 위치 - 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.

 2) 캐릭터의 바로 왼쪽에 아직 가보지 않는 칸이 존재O → 왼쪽 방향으로 회전 후 왼쪽으로 한 칸 전진

     왼쪽에 가보지 않는 칸이 존재하지 X → 왼쪽 방향으로 회전만 수행 후 1단계로 돌아감

 3) 만약 네 방향 모두 이미 가본 칸 or  바다로 되어 있는 칸 → 바라보는 방향 유지한 채, 뒤로 한 칸 이동. 1단계로 돌아간다. (뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우는 움직임을 멈춘다.)

 

위 방법을 반복적으로 수행하면서 캐릭터의 움직임에 이상 있는지 테스트하려한다.

캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

 

✔️입력 조건

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

 

✔️출력 조건

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

 

✔️입력 예시

✔️출력 예시

3

 

✔️나의 문제풀이

 - 30분 내에 문제 해결하지 못하여 답지 확인

n,m = map(int,input().split())    # n 세로 크기, m 가로 크기
a,b,d = map(int,input().split())    # (a,b) 게임 캐릭터 좌표, d 바라보는 방향

pos = [3,2,1,0]
move = [(-1,0),(0,1),(1,0),(0,-1)]
maps = []
ans,turn = 1,0

for _ in range(n):
    maps.append(list(map(int,input().split())))


while True:
    now_pos = (pos.index(d) + 1) % 4 
    if maps[a + move[now_pos][0]][b + move[now_pos][1]] != 1:
        maps[a + move[now_pos][0]][b + move[now_pos][1]] = 1
        a = a + move[now_pos][0]
        b = b + move[now_pos][1]
        ans += 1
    else:
        now_pos = (now_pos + 1) % 4
        if now_pos == d and maps[a-move[now_pos][0]][b-move[now_pos][1]] == 1:
            break
        elif now_pos == d:
            a = a-move[now_pos][0]
            b = b-move[now_pos][1]
print(ans)

 

✔️책의 문제 풀이

 - 전형적인 시뮬레이션 문제. 별도의 알고리즘 필요하지 않음, 문제에서 요구하는 내용 성실히 구현하기

 - 방향 설정 이동 문제

•   dx,dy 별도의 리스트를 만들어 방향 정하기

 - 코딩 테스트는 입력값이 주어져서 예외처리 고려하지 않고 코드 작성하기

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

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 x,y 좌표,방향 입력받기
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)

 

✔️책의 문제풀이 분석

 - 조건

• 왼쪽 방향 회전하면서 탐색 
• 진행 방향(북,동,남,서) 좌표화 
• 왼쪽 방향 돌때마다 진행방향 숫자화 하기
• 회전 이후 정면에 가보지 않은 칸 or 가본 칸(가보거나 바다인 경우)
• 네 방향 다 가본 경우 → 뒤로 가기 or 뒤가 바다인 경우 종료

 - 부수 조건

•  카운트 세기
• 회전 횟수 세기

 - 다음 문제 풀때는 문제 조건 하나씩 뜯어보면서 코딩해보기