[이코테] chapter04 구현

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

 

구현 알고리즘

: 머릿속에 잇는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

✨구현 알고리즘은 피지컬 싸움이다!
(1) 완전 탐색
     : 모든 경우의 수를 다 계산하는 해결 방법
(2) 시뮬레이션
     : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제

- 고려해야하는 메모리 제약 사항 -

파이썬은 자료형의 표현 범위 제한은 고려 안해도 됨!

리스트는 보통 128MB ~ 512MB

데이터의 개수(리스트 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4KB
10,000,000	약 40MB

---

4-1.py 상하좌우 - ⭐1/3 (⭕)

파이썬에는 switch-case문이 없다..!!

교재 풀이에서는 type들을 따로 리스트에 저장해서 사용했다.

N = int(input())
data = list(map(str, input().split()))

reachPoint = [1,1]
for i in range(len(data)):
    if data[i] == 'R':
        if reachPoint[1] == N:
            continue
        reachPoint[1] += 1

    elif data[i] == 'L':
        if reachPoint[1] == 1:
            continue
        reachPoint[1] -= 1
    
    elif data[i] == 'U':
        if reachPoint[0] == 1:
            continue
        reachPoint[0] -= 1
    
    elif data[i] == 'D':
        if reachPoint[0] == N:
            continue
        reachPoint[0] +=1
print(reachPoint)

 

 

4-2.py 시각 - ⭐1/3 (⭕)

이 문제는 백준 <18312번 시각> 문제이다.

N, K = map(int, input().split())
cnt = 0
result = 0

for i in range(60):
    if i % 10 == K or i //10 == K:
        cnt += 1
cnt = cnt*60*2 - cnt*cnt

for i in range(N+1):
    if i % 10 == K or i//10 == K:
        result += 3600
    else: result+= cnt

print(result)

 

 

4-3.py 왕실의 나이트 - ⭐1/3 (⭕)

유니코드를 가져올 때는 ord() 함수를 사용한다.

data = input()
x = [2, 2, 1, 1, -1. -1, -2, -2]
y = [1, -1, 2, -2, 2, -2, 1, -1]
cnt = 0

for i in range(len(x)):
    rx = ord(data[0]) + x[i]
    ry = int(data[1]) + y[i]
    if rx <= ord('h') and rx >= ord('a') and ry <= 8 and ry >= 1:
        cnt += 1

print(cnt)

 

 

4-4.py 게임 개발 - ⭐2/3 (❌ 33m 31s)

처음으로 별 2개짜리 문제가 나왔다!

문제에서 주어지는 입력 예시는 테스트 성공했지만 찜찜한 이 기분,,😫😒

이 문제는 문제부터 충분히 이해를 한 후에 풀어야한다.

나의 중심 아이디어는 방문한 곳은 모두 '1'로 바꾸기였다. 그래서 아래와 같이 코드를 짰다.

N, M = map(int,input().split())
x, y, d = map(int, input().split())
myMap=[]
cnt = 1

for i in range(N):
    myMap.append(list(map(int, input().split())))

while myMap[x+1][y] == 0 or myMap[x][y-1] == 0 or myMap[x-1][y] == 0 or myMap[x][y+1] == 0:
    if d == 0:
        d = 3
        if myMap[x-1][y] == 0:
            myMap[x][y] = 1
            x -= 1
            cnt += 1

    elif d == 1:
        d = 0
        if myMap[x][y+1] == 0:
            myMap[x][y] = 1
            y += 1
            cnt += 1

    elif d == 2:
        d = 1
        if myMap[x+1][y] == 0:
            myMap[x][y] = 1
            x += 1
            cnt += 1

    elif d == 3:
        d = 2
        if myMap[x][y-1] == 0:
            myMap[x][y] = 1
            y -= 1
            cnt += 1

print(cnt)

교재에서 주어진 예시는 통과했지만 아래의 내가 만든 예시에서는 오답으로 나왔다.

(참고로 아래의 출력값으로는 7이 나와야함!)

이유는 문제에서 주어진 3번 조건을 고려안하고 푼 것,,,

6 6
1 1 1
1 1 1 1 1 1
1 0 0 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

 

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

 

ㅎㅎ.. 고려를 안했다..

교재 풀이를 리뷰해보겠다.

나는 왜 지금까지 함수를 사용해서 풀 생각을 못 했을까~ 

그리고 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)