[이것이코딩테스트다] ch4 구현

✅ 구현 (Implement) 

머릿속의 알고리즘을 소스코드로 바꾸는 과정

 

사소한 조건 설정이 많은 문제일수록 코드 구현이 까다로워진다. 

 

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

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

 

✔️ 구현시 고려할 메모리 제약사항

파이썬 리스트 크기

- 코딩테스트에서는 128~512MB로 메모리를 제한하는데, 알고리즘 문제중 수백만개 이상의 데이터를 처리해야하는 문제가 출제되고는 한다

 

일반적인 코딩테스트 수준에선 메모리 사용량제한보다는, 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하면 된다.

 

일반적으로는

2020년을 기준으로 파이썬 3.7로 코드를 작성할 때,

자신의 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면

실행 시간 제한에 안정적이다.

 

 

제한시간이 1초이고, 데이터개수가 100만개인 경우- 

 

2000만번의 연산까지가 안정적이므로

 

 

 

 

 

✅ 예제 4-1 : 상하좌우

 

 

💻 CODE

import sys
input = sys.stdin.readline

direction = {"L":[0,-1],"R":[0,1],"U":[-1,0],"D":[1,0]}

n = int(input())
moveInfo = list(map(str, input().split()))

r, c = 0, 0
for dir in moveInfo:

    dr = r + direction[dir][0]
    dc = c + direction[dir][1]

    if (0 <= dr < n ) and (0 <= dc < n) :
        r, c = dr, dc #이동완료

print(r+1,c+1)

 

✅  예제4-2 : 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각중에서 3 이 하나라도포

함되는 모든 경우의 수를 구히는- 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3 이 하

나라도 포함되어 있으므로 세어야 하는 시각이다.

 

> 3중 반복문으로 체크해도 된다.

N은 최대 23이므로, 

만약 00시00분00초부터 23시 59분 59초를 전부 고려하면  24*60*60이므로  전체경우가 86400밖에 되지 않는다. 

💻 CODE

import sys
input = sys.stdin.readline

h = int(input())

count = 0
for i in range(h+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i)+str(j)+str(k):
                count+=1

print(count)

 

 

✅  2 : 왕실의 나이트

8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을때 
나이트가 이동 할 수 있는 경우의 수를 출력하는 프로그램 작성

 

💻 CODE

import sys
input = sys.stdin.readline 

steps = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]]

now = input()

r = int(now[1])
c = int(ord(now[0]))- int(ord('a'))+1

result = 0
for step in steps :
    nextRow = r+step[0]
    nextColumn = c+step[1]

    if(1<=nextRow<=8 and 1<=nextColumn<=8):
        result +=1

print(result)

 

 

✅  3 : 게임개발

 

다시 풀어봐야 할듯하다! 세세한걸 읽는 능력이 살짝 떨어지는 것 같은데 좀더 자세히 읽어보면서 다시 풀어보자!

 

💻 CODE

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
r,c, dir = map(int,input().split())

board = [list(map(int,input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]


#북동남서
d = [[-1,0],[0,1],[1,0],[0,-1]]

#처음칸 방문처리
visited[r][c] = True
count = 1

def turnLeft():
    global dir
    dir -=1
    if (dir == -1):
        dir = 3

turn_count = 0
while True:
    turnLeft()
    nr = r+d[dir][0]
    nc = c+d[dir][1]

    if(board[nr][nc] == 0 and not visited[nr][nc]):
        visited[nr][nc] = True
        count +=1
        turn_count=0
        r,c = nr, nc
        continue
    else:
        turn_count+=1
    
    if turn_count == 4:
        nr = r - d[dir][0]
        nc = c - d[dir][1]

        if(board[nr][nc] == 1):
            break
        else:
            r,c = nr, nc
        turn_time =0

print(count)