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

1. 구현 개념 및 아이디어

 

개념: 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정

구현: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

시뮬레이션:  일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점(실제로 시뮬레이션 해보는 것)

완전탐색: 가능한 경우의 수를 모두 검사해보는 탐색방법

 

 

예시

- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

- 실수 연산을 다루고, 특정 소수점까지 출력

- 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제

- 적절한 라이브러리를 찾아서 사용해야하는 문제

 

2. 예제

 

2차원 공간 문제에서 많이 쓰이는 행렬

예제1) 행렬

for i in range(5):

    for j in range(5):

        print('(',i,',',j,')', end=' ')

    print()

 

시뮬레이션 및 완전탐색 문제에서 자주 쓰이는 2차원 공간에서의 방향벡터

예제2) 방향 벡터

dx = [0, -1, 0, -1]

dy = [1, 0 ,-1, 0]

x, y = 2, 2

for i in range(4):

   

    nx = x + dx[i]

    ny = y + dy[i]

    print(nx, ny)

 

예제3) 상하좌우 문제

아이디어: 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요하다.

n = int(input())

x, y = 1, 1

plans = input().split()

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)

 

예제4) 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 문제

아이디어: 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제 하루는 86400초이므로 경우는 86400 따라서 단순하게 1씩 증가 시켜 3이 하나라도 포함되어 있는지를 확인하면 된다. 이러한 유형을 완전 탐색 문제 유형이라고한다.

 

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)

 

예제5) 왕실의 나이트 문제 나이트가 특정 위치에 있을 때 이동할 수 있는 경우의 수

아이디어: 나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인한다. 리스트를 이용하여 8가지 방향에 대한 방향벡터를 정의한다.

input_data = input()

row = int(input_data[1])

column = int(ord(input_data[0]))- int(ord('a'))+1

result = 0

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

for step in steps:

    next_row = row + step[0]

    next_col = column + step[1]

    if next_row >=1 and next_row <=8 and next_col >=1 and next_col <=8:

        result+=1

print(result)

 

예제6) 문자열 재정렬

아이디어: 문자열이 입력되었을 때 문자를 하나씩 확인하고 숫자인 경우 따로 합계를 계산하고 알파벳의 경우 별도의 리스트에 저장한다. 리스트에 저장된 알파벳을 정렬하여 출력하고, 합계를 뒤에 붙여 출력하자

data = input()

result =[]

value = 0

for x in data:

    if x.isalpha():

        result.append(x)

    else:

        value += int(x)

result.sort()

if value != 0:

    result.append(str(value))

print(''.join(result))