이코테 Chapter 4 구현

김남형·2021년 7월 8일
0
  • 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
  • 흔히 구현 유형의 문제라 하면, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
  • 구현 유형의 예시로는 다음과 같다.
    • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
    • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
    • 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
    • 적절한 라이브러리를 찾아서 사용해야 하는 문제 (ex. 순열, 조합 찾기)
  • 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.
  • 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

예제 1 : 상하좌우

시뮬레이션 유형의 문제. 나의 풀이는 너무 지저분하다.

# 내 풀이
n = int(input())
command = list(input().split())
count = len(command)
x = 1
y = 1
i = 0

while count > 0 :
  if command[i] == 'R' :
    i += 1
    count -= 1
    if y == n :
      continue
    y += 1
  elif command[i] == 'L' :
    i += 1
    count -= 1
    if y == 1 :
      continue
    y -= 1
  elif command[i] == 'U' :
    i += 1
    count -= 1
    if x == 1 :
      continue
    x -= 1
  elif command[i] == 'D' :
    i += 1
    count -= 1
    if x == n :
      continue
    x += 1
  else :
    print('잘못된 입력')
    break

print(x, y)

방향 벡터를 활용하면 더욱 간단히 작성할 수 있다.

# 교재 풀이
# N 입력받기
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)

예제 2 : 시각

모든 경우를 다 세서 푸는 문제. 완전 탐색(Brute Forcing) 문제 유형이라고 불린다. 가능한 경우의 수를 모두 검사해보는 탐색 방법을 의미한다.

# 내 풀이
n = int(input())
x = [3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53]
count = 0

for i in range(n+1) :
    for j in range(60) :
        for k in range(60) :
            for three in x :
                if i == three :
                    count += 1
                    break
                if j == three :
                    count += 1
                    break
                if k == three :
                    count += 1
                    break
                print(i,j,k,count,three)

print(count)
# 교재 풀이
# H를 입력받기
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)

교재에서는 시, 분, 초를 문자형으로 바꾸어서 풀었다. 파이썬에서는 형변환이 다른 언어들보다 비교적 자유롭기 때문에 이와 같이 해결 하는 습관이 소스 코드를 간단히 하는 지름길인 것 같다.

실전 문제 1 : 왕실의 나이트

시뮬레이션, 완전 탐색, 2차원 좌표 이용하는 구현 문제

# 내 풀이
spot = list(input())

# 좌표로 변환
x = int(spot[1])
input_y = ['a','b','c','d','e','f','g','h']
for i in range(len(input_y)):
  if spot[0] == input_y[i] :
    y = i+1

# 총 경우의 수
dx = [-1, -2, -1, -2, 1, 2, 1, 2] # 위1 위2 위1 위2 아1 아2 아1 아2
dy = [-2, -1, 2, 1, -2, -1, 2, 1] # 왼2 외1 오2 오1 왼2 왼1 오2 오1

# 이동 가능 여부 확인
count = 0
for i in range(8) :
  if not (x + dx[i] < 1 or x + dx[i] > 8 or y + dy[i] < 1 or y + dy[i] > 8) :
    count += 1

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

내 풀이와 생각하는 방법은 똑같았다. 그러나, 입력 방식에서 아스키 코드를 이용했다는 점과 방향 설정을 튜플을 활용하여 하나의 리스트로 설정했다는 점이 차이가 있었다.

실전 문제 2 : 문자열 재정렬

숫자는 따로 합계를 계산해주고, 알파벳은 별도의 리스트에 저장하면 되는 문제.

# 내 풀이
data = input()
data_str = []
sum = 0

for x in data :
  if 65 <= ord(x) <= 90 :
    data_str.append(x)
  else :
    sum += int(x)
data_str.sort()

for x in data_str :
  print(x, end = '')
if sum != 0 :
  print(sum)
# 교재 풀이
data = input()
result = []
value = 0

# 문자를 하나씩 확인하며
for x in data:
    # 알파벳인 경우 결과 리스트에 삽입
    if x.isalpha():
        result.append(x)
    # 숫자는 따로 더하기
    else:
        value += int(x)

# 알파벳을 오름차순으로 정렬
result.sort()

# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
    result.append(str(value))

# 최종 결과 출력(리스트를 문자열로 변환하여 출력)
print(''.join(result))

isalpha() : 알파벳 판별 함수

'구분자'.join(리스트) : 리스트 내의 문자열을 합쳐주는 함수

교재 풀이에서는 위의 함수들을 사용했다는 것과 숫자의 합계를 문자열로 변환하여 하나의 리스트에 append 해주었다는 점이 차이가 있다.

실전 문제 3 : 게임 개발

시뮬레이션 문제. 이와 비슷한 문제를 코드업 100제 마지막 문제에서 풀어봤다고 생각했는데, 이 문제는 거기에다 방향 전환까지 추가되어서 너무 어려웠다. 하루 넘게 코딩해보다가 도저히 못하겠다 싶어서 풀이를 봤다.

# 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)

0개의 댓글