구현

구현이란?

- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 (풀이 방법 구상 -> 정확히 구현)
- 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이긴 

완전 탐색 _ 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 _ 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
(+ 코드가 길어지는 문제, 실수 연산과 특정 소수점 출력 문제, 문자열 슬라이싱, 라이브러리 사용 문제)

 

1. 메모리 제약 사항 생각하기 ( 변수의 표현 범위, 리스트 크기 )

2. 좌표 문제의 경우, 이동할 방향을 기록

 

tip. 문제의 길이가 길지만, 문법에 익숙하다면 오히려 쉬울 수 있음.

---

ex) 상하좌우 ( 시뮬레이션 )

닫기

입력

 N (1 ≤  N ≤ 100) ; N * N 크기의 정사각형, 가장 왼쪽 위가 (1,1)

 A가 이동할 계획서 (1 ≤ 이동 횟수 ≤ 100) 공백으로 구분  ; L (왼쪽으로 한칸), R ( 오른쪽으로 한칸 ), U ( 위로 한칸), D (아래로 한 칸 이동)  

출력

(1,1)에서 시작해 이동을 마친 후 A가 최종적으로 도착할 좌표 (X, Y) 를 공백으로 구분하여 출력, 범위를 벗어나는 움직임은 무시

import sys

n = int(input())
plans = input().split()

x, y = 1, 1
move_types = ['L', 'R', 'U', 'D']
move_x = [0, 0, -1, 1]
move_y = [-1, 1, 0, 0]

for plan in plans:
    for j in range(len(move_types)):
        
        if plan == move_types[j]:
            now_x = x + move_x[j]
            now_y = y + move_y[j]
            
    if now_x < 1 or now_y <1 or now_x > n or now_y > n:
        continue
        
    x = now_x
    y = now_y
        
print(x, y)

 

1. 연산 횟수와 이동 횟수가 비례, N번 이동 -> O(N)

2. 각 방향당 x, y가 하나씩 있으므로 인덱스 활용

---

ex) 시각 (완전 탐색 )

닫기

입력

 N (0 ≤  N ≤ 23) 

출력

N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수

import sys

hour = int(input())

count = 0

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

 

1. 하루는 86,400초로 한정, 모든 시각의 경우를 하나씩 세도 됨.

-  경우의 수가 100,000도 되지 않으면 시간 제한 2초 안에 문제 해결 가능

---

이것이 코딩 테스트다 - 나동빈
https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

정리하긔