[알고리즘] 구현(Implementation) 알고리즘(시뮬레이션과 완전 탐색)

*구현(Implementation) 알고리즘(시뮬레이션과 완전 탐색)

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

-> 아무리 알고리즘을 잘 세워도 실제로 구현할 수 있는 것이 더 중요하다!

 

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

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

- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

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

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

 

*일반적으로 알고리즘 문제에서의 2차원 공간은 행렬을 의미로 사용된다. (=2차원 리스트)

for i in range(n):
    for j in range(m):

* 시뮬레이션 및 완전 탐색 문제에서는 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)

---

[대표 문제 1] 상하좌우

 : 주어지는 요구사항에 따라 행렬 혹은 2차원 공간을 구성해주기
- 시뮬레이션 유형으로 분류 가능

주어지는 공간을 벗어나는 경우는 무시된다.

N = int(input())
x , y = 1 , 1
plans = input().split()

move = ['L', 'R', 'U', 'D']
dx = [0,0,-1,1]
dy = [-1,1,0,0]


for i in plans:
    for j in range(len(move)):
        if i == move[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)

* 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)이다.

 

[대표 문제 2] 시각

 : 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제 (완전 탐색 유형이라고 볼 수 있음)
하루(24H) -> 86,400s => 컴퓨터로 셈이 가능한 규모

N = int(input())

count = 0

for i in range(N+1): #시
    for j in range(60): #분
        for k in range(60): #초
            if '3' in str(i) + str(j) + str(k): #문자열로 처리하는 방식
                count += 1
print(count)

 

[대표 문제 3] 왕실의 나이트

 : 2차원 공간 -> 행 위치는 1~8 / 열 위치는 a~h
시뮬레이션 + 완전 탐색 + 이차원 공간 활용 문제
=> 요구사항대로 충실히 구현하면 되는 문제 (with. 방향벡터)

intput_data = input()
row = int(input_data[1])
col = int(ord(input_data[0])) - int(ord('a')) + 1

#나이트가 움직일 수 있는 방법
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,-1),(2,1),(1,2),(-1,2),(-2,1)] 

result = 0
for i in steps:
    next_row = row + i[0]
    next_col = col + i[1]

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

print(result)

 

[대표 문제 4] 문자열 재정렬

 : 요구사항대로 충실히 구현하면 되는 문제
-> 문자열이 입력되었을 때 문자를 하나씩 확인!
=> 이때, 숫자인 경우 따로 합계를 계산 + 문자인 경우 별도의 리스트에 저장
결과적으로 리스트에 저장된 알파벳을 먼저 출력하고 숫자의 합계를 뒤에 붙여 출력하면 된다.

S = input()

A = []
count = 0

for i in S:
    if i.isalpha(): #알파벳인지 확인하는 함수
        A.append(i)
    else :
        count += int(i)

A.sort()

if count != 0:
    A.append(str(count))

print(''.join(A)) #A 리스트를 공백 없이 일렬로 출력

---

강의 내용 출처 - https://youtu.be/2zjoKjt97vQ

(이코테 2021 강의 몰아보기) 2. 그리디 & 구현