[python] 구현(완전 탐색, 시뮬레이션)

# 구현

• 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수핸하는 문제
• 알고리즘은 간단하지만 코드가 길거나, 특정 소수점 출력/문자열 다루기 등의 문제가 까다로운 구현 문제이다.

리스트

• 파이썬에서 리스트를 여러 개 선언하고, 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한에 걸릴 위험이 있다.
• 또한 빠른 입출력 속도까지 고려하여 시간 제한을 염두에 두고 풀어야 한다.
• int 자료형 데이터 개수에 따른 메모리 사용

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

 

 

# 예제

1. 상하좌우

- NxN 크기의 정사각형 공간에서 (1,1)에 위치한 사람이 (상,하,좌,우) 중 하나를 택해 이동한다.

- 정사각형 크기를 벗어나면 무시된다.

- 최종적으로 도착하게 될 위치를 출력한다.

# N 입력받기
n = int(input()
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획 하나씩 확인
for plan in plans:
# 이동 후 좌표 구하기
	for i in range(len(move_types)):
    	if plan == move_types[i] :
        	nx = x + dx[i]
            ny = y + dy[i]
        # 공간을 벗어나는 경우 무시
        if nx < 1 or ny < 1 or nx > n or ny>n:
        	continue
        # 이동 수행
        x, y = nx, ny
        
print(x, y)

 

2. 시각

- 정수 N이 입력되면 00시00분00초부터 N시59분59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기

- 하루는 86,400초로, 모든 경우의 수가 이를 넘지 않으므로 하나씩 세서 풀 수 있다.

# H 입력받기
h = int(input())

count = 0
for i in range(h+1):
	for j in range(60):
    	for k in range(60):
        	# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
            	count +=1
                
print(count)

 

3. 왕실의 나이트

- 8x8 좌표 평면에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력한다.

- 나이트틑 수평으로 두 칸 이동 + 수직 한 칸 이동 혹은 수직으로 두 칸 이동 + 수평 한 칸 이동 만 가능하다.

- 나이트의 이동 경로를 steps 변수에 넣고 상하좌우 문제와 같이 검사한다.

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1 # ord('a') a에 해당하는 유니코드 정수 반환

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1),
		(1, 2), (-1, 2), (-2, 1)]
        
# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in staps:
	# 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >=1 and next_row <= 8 and next_column >= 1 and next_column <=8:
    	result +=1

print(result)

 

3. 게임 개발

- NxM 직사각형 안에서 각 칸은 육지(0) 또는 바다(1)칸이 된다.

- 캐릭터는 동서남북으로 움직일 수 있으며, 바다로 되어 있는 칸에는 갈 수 없다.

- 캐릭터의 현재 위치에서 현재 방향을 기준으로 왼쪽부터 갈 곳을 정한다.

- 캐릭터의 바로 왼쪽 방향에 가보지 않은 칸이 존재한다면 왼쪽으로 회전 후 한 칸 전진. 존재하지 않으면 회전만 수행 후 다시 갈 곳을 정한다.(위 단계로)

- 네 방향 모두 가본 칸이거나 바다로 되어있는 경우 방향을 유지한 채로 한 칸 뒤로 간다. 이때 뒤쪽 방향이 바다인 경우 움직임을 멈춘다.

- 대표적인 시뮬레이션 문제이다.

# N, M을 공백으로 구분하여 입력받기

# 방문한 위치를 저장하기 위한 맵을 생성하여 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():
	gobal 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) # 정답 출력

 

---

# 백준

https://www.acmicpc.net/problem/4673

import sys
input = sys.stdin.readline

num = set(range(1, 10001))
num2 = set()

for i in range(1, 10001):
    for j in str(i):
        i+=int(j)
    num2.add(i)
    
ans = sorted(num - num2)
for i in ans:
    print(i)

- 집합 함수 set() 을 이용하면 쉽다.

- 생성자 집합과 숫자 집합을 만든 후 빼주면 셀프 넘버 집합(num2)

 

https://www.acmicpc.net/problem/7568

7568번: 덩치

import sys
input = sys.stdin.readline

n=int(input())

num = []
rank = []

for _ in range(n):
    num.append(list(map(int, input().split())))

for _ in range(n):
    k=0
    for i in range(1, n):
        if num[0][0]<num[i][0]:
            if num[0][1]<num[i][1]:
                k+=1
                
    rank.append(k)
    num.append(num.pop(0))
    
for i in rank:
    print(i+1, end =' ')

- rank에는 나보다 덩치가 큰 사람 수. 따라서 print는 사람 수 + 1(==등수)로 출력

- list의 pop(), append()을 이용하여 비교 완료한 사람은 뒤로 가게 함.