구현 알고리즘은 크게 ‘시뮬레이션’과 ‘완전 탐색’이라는 두 가지 유형으로 나뉜다.
시뮬레이션은 _문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행해야하는 문제 유형_을 의미한다.
완전 탐색은 _모든 경우의 수를 주저없이 다 계산하는 해결방법을 의미_한다.
- 시뮬레이션 中 ‘상하좌우’ 문제 N x N 좌표계 시작은 (1,1)이며 맨 왼쪽 구석. 즉 0값을 갖는 좌표는 없음 L, R, U, D 는 방향을 지시하는 커멘드이며 각각 왼쪽, 오른쪽, 위쪽, 아래쪽으로 한칸씩 이동을 의미 좌표계를 벗어나는 커맨드는 무시됨
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
n = int(input())
# command는 알아서 리스트형태로 만들어짐. 별도의 지정이 없을 경우, 여러개의 인풋이 들어오면 디폴트가 리스트이기 때문.
# 물론 list에 직접 담아도 됨.
# list(input().split())
commands = input().split()
# 커맨드 타입에 대응하는 x,y의 변화량을 리스트로 명시
com_types = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# x,y 초기값 설정
x, y = 1, 1
# 반복문으로 입력된 커맨드들을 하나씩 대조해서 최종 좌표 출력
for command in commands:
for i in range(len(com_types)):
if command == com_types[i]:
nx = x + dx[i]
ny = y + dy[i]
# 여기선 continue를 사용해야함
# 왜냐면 좌표계를 넘어가는 커맨드는 무시되야하기 때문에 해당 조건문 뒤에 x, y값을 지정해주는 코드가 작동해선 안되기 때문.
# 실제로 pass 사용하면, 결과값이 (2,4)가 나옴
if nx < 0 or ny < 0 or nx > n or ny > n:
continue
x, y = nx, ny
print(x, y)
- 완전 탐색 中 ‘시각’ 문제 정수 n이 입력되면 00시~ n시 59분 59초까지의 모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 작성
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
count = 0
for h in range(n+1):
for m in range(60):
for s in range(60):
if '3' in str(h) + str(m) + str(s):
count +=1
print(count)
위의 함수는 1초씩 늘어나면서 3이 포함되어 있는지를 일일이 체크하도록 구성되었다.
앞서 설명했듯이 완전 탐색은 모든 경우의 수를 체크해보는 탐색 방법이기 때문에, 일반적으로 비효율적인 시간 복잡도를 가진다.
그래서 보통 백만개 이하일 때 완전 탐색을 사용하면 적절하고, 실제 문제들도 전체 데이터 수를 그렇게 크게 주진 않는다.