[알고리즘 이론] 구현 문제

[이것이 코딩 테스트다, 나동빈] 책을 공부하고 정리한 글입니다.

🌀구현 문제

: 이 책에서는 완전 탐색과 시뮬레이션 유형을 구현 문제로 묶어서 다루고 있음.

: 머리 속의 알고리즘을 프로그램으로 작성하기.

 

✅ 예제 : 상하좌우

여행가 A는 n * n 크기의 정사각형 공간에 있다. 여행가의 계획서에는 LRUD(왼, 오, 위, 아래)가 반복적으로 적혀있다.

정사각형을 벗어나는 움직임은 무시함. 최종 도착지의 좌표를 구하시오. (아래 방향 x축, 오른쪽 방향 y 축)

 

💡내 풀이

n = int(input())
plan = list(input().split())
x = 1
y = 1
for i in plan:
    if (i == 'R') and (y != n):
        y += 1
    elif (i == 'L') and (y != 1):
        y -= 1
    elif (i == 'U') and (x != 1):
        x -= 1
    elif (i == 'D') and (x != n):
        x += 1
print(x, y)

파이썬은 &&가 없다니.... 대충격! 대신 and, &, or, |, is, not ... 등등이 있다. and랑 &도 역할이 다르다. 엄청 신기해.... 내일 이거 알아봐야겠당.

 

책에 나온 코드는 좀 더 복잡하지만 확장성이 좋은 듯 하다.. 지금은 4가지 움직임 밖에 없어서 나는 if문으로 풀었지만, 대각선 움직임이 가능하고 좌표가 3차원으로 바뀐다면,,, if문을 26개 써야할지도 모른다.아래는 저자의 코드!!https://github.com/ndb796/python-for-coding-test/blob/master/4/1.py

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

✅ 예제 : 시각

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

 

💡내 풀이

n = int(input())
res = 0
three = 60 * 60 - (5 * 9 * 5 * 9)
for i in range(n + 1):
    if (i == 3) or (i == 13) or (i == 23):
        res += (60 * 60)
    else:
        res = res + three
print(res)

내 풀이의 경우..! 확통 문제 풀듯이 풀었다. 시간에 3이 들어간 경우에는 60 * 60(분, 초 모든 경우)를 더하고, 시간에 3이 들어가지 않은 경우에는, three라는 변수에 분 또는 초에 3이 들어가 있는 경우의 수를 구해서 더해준다.

 

책에서는 삼중 for문을 이용하여 시, 분, 초를 문자열로 변형해 풀었다. 간결해서 알아보기 좋은 코드인 것 같다!

💡 책 답안 예시

n = int(input())
res = 0

for i in range(n + 1):
    for j in range(60):
        for k in range (60):
            if '3' in str(i) + str(j) + str(k):
                res += 1
print(res)

 

✅ 예제 : 왕실의 나이트

(8 * 8)체스판 위에 나이트가 있다. 나이트는 다음과 같은  두 가지 경우로 이동 가능

    1 수평으로 두칸 이동한 뒤에 수직으로 한 칸 이동

    2 수직으로 두칸 이동한 뒤에 수평으로 한 칸 이동

체스판에서 행 위치는 1 ~8, 열 위치는 a ~ h로 표현된다.

나이트가 이동할 수 있는 경우의 수

💡내 풀이

pos = input()
res = 8

x = int(ord(pos[0]) - ord('a')) + 1
y = int(pos[1])

move = [[2, 1], [2, -1], [-2, 1], [-2, -2], [1, 2], [1, -2], [-1, 2], [-1, -2]]
for i in move:
    if (x + i[0] < 1) or (x + i[0] > 8) or (y + i[1] < 1) or (y + i[1] > 8):
        res -= 1
print(res)

파이썬은 char형과 int형의 자유로운 연산이 안된다....! 추우우웅격 ord와 chr에 대해 알아보장.

처음에는 자연스럽게 pos가 문자열이니까 pos[0] <  'a' 이런식으로 비교하려 했는데..? 완전 c언어 식으로만 생각중이었다...

파이썬 편리하지만 너무 헷갈려어어ㅓㅇ🥴🥴 그래서 처음부터 그냥 풀이 참고해서 풀었다..ㅎㅎ

 

✅ 예제 : 게임 개발

문제는 너무 길어서 생략...!

 

💡내 풀이

n, m = map(int, input().split())
x, y, d = map(int, input().split())

move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
x_move = x
y_move = y

visit =[[0] * m for i in range(n)]
visit[x][y] = 1

res = 0

def turnleft(d):
    if d == 0:
        d = 3
    else:
        d -= 1
    return d

game_map = list()

for i in range(n):
    game_map.append(list(map(int, input().split())))

while 1:
    d = turnleft(d)

    x_move = x + move[d][0]
    y_move = y + move[d][1]

    if visit[x-1][y]+visit[x+1][y]+visit[x][y+1]+visit[x][y-1]+ \
    game_map[x-1][y]+game_map[x+1][y]+game_map[x][y+1]+game_map[x][y-1] >= 4 :
        break
    if x_move < 0 or x_move > n - 1 or y_move < 0 or y_move > m - 1 :
        continue
    elif game_map[x_move][y_move] == 1:
        continue
    elif visit[x_move][y_move] == 1:
        continue
    else :
        x = x_move
        y = y_move
        visit[x][y] = 1

for i in visit:
    for j in i:
        if j == 1:
            res += 1
res += 1
print(res)

굉장히 오래걸렸당.. 이거하는데 이렇게 오래걸리다니..!ㅎㅎ..