[Algorithm] 구현(Implementation)

구현 알고리즘

실생활의 문제를 코드로 나타내 해결하는 방식

완전 탐색과 시뮬레이션 유형으로 나뉜다.

완전 탐색 (Brute-force search)

모든 경우의 수를 다 계산하는 방식

즉 로직을 간단하게 하기 위해 시간, 공간 복잡도를 늘리는 방식이다.

따라서 주어진 입력의 범위가 적을 때만 사용해야 한다.

시뮬레이션 (Simulation)

문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 방식

 

---

자주 등장하는 유형

실생활의 문제를 코드로 나타내기 위해서는 수식화 단계를 거쳐야 한다.

좌표로 나타내기

이동 가능한 경로를 계산하는 등의 방식에서 사용된다.

# 상하좌우
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
literal = ['Up', 'Down', 'Left', 'Right']

이 경우 위와 같이 데이터를 미리 할당한 뒤 사용하는 방식으로 풀이하는 것이 좋다.

데이터와 로직을 분리하여 코드가 깔끔해지고, 실수를 바로 알아보기 쉽기 때문이다.

모든 경우의 수 다 고려하기 (with 반복문)

data = [
    ['0', '0', '0', '0'],
    ['0', '1', '0', '0'],
    ['0', '0', '0', '0']
]

for i in range(data):
        for j in range(data[0]):
                if data[i][j] == '1':
                    print(i, j)
                    break

중첩 반복문을 이용하면 모든 경우의 수를 다 고려하는 완전탐색 알고리즘을 쉽게 이용할 수 있다.

그러나 시간복잡도가 O(N^m) 형태로 나타나기 때문에 수의 범위가 클 때에는 지양해야 한다.

문제에서 제시한 알고리즘을 그대로 구현하기

시뮬레이션은 대부분 이것에 해당된다.

문제에서 어떤 문제를 해결하는 방법에 대해 설명해주면, 이를 그대로 구현하면 된다.