알고리즘 - 구현(Implementation)

https://youtu.be/2zjoKjt97vQ?t=1698 

<구현: 시뮬레이션과 완전 탐색>

구현(Implementation)이란?

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

이때, 구현에 초점을 맞춘 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기는 어려운 문제를 지칭한다.

 

구현 문제의 예시

• 알고리즘은 간단하지만 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제(문자열처리는 파이썬이 다른 언어에 비해서 굉장히 쉬움)
• 적절한 라이브러리를 찾아서 사용해야 하는 문제 (모든 순열, 모든 조합을 찾는 경우)

시뮬레이션과 완전 탐색이 구현의 대표적인 예시이다. 

파이썬에서는 2차원 리스트 = 2차원 공간인 행렬로 쓰인다.

0행0열이 아닌 첫 번째 원소라고 부른다.

x = 행

y = 열

(1,1)이 시작위치라면 (0,0)을 사용하지 않는 방법을 쓰거나 혹은 (1,1)을 (0,0)처럼 쓰는 방식이 있다.

---

<문제: 상하좌우>

 

#상하좌우
x,y = 1, 1 #시작 위치가 (1,1)
n = int(input())
plans = input().split()

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

for i in plans:
    for j in range(len(move)):
        if i == move[j]:
            nx = x +dx[j]
            ny = y +dy[j]
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    x, y = nx, ny
print(x,y)

---

<문제: 시각>

 

전형적인 완전탐색 문제로 구현문제이다.

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): #시, 분, 초를 전부 더해버리고 그 안에 3이 들어있나 체크하는 
                count += 1
print(count)

---

<문제: 왕실의 나이트>

구현문제 유형으로 구현하면 된다.

나이트의 8가지 경로를 매번 확인하며 각위치로 이동이 가능한지 확인해야 한다.

input_data = input()
row = int(input_data[1]) #c2를 입력 받았을 경우 input_data[1]이 2로 행이기 때문
column = int(ord(input_data[0]))-int(ord('a')) + 1 #0부터 시작하기 때문에 1을 더해줌
                            
#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1),(-1,-1),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

#가지의 방향에 대해 각 위치로 이동이 가능한지 확인
result = 0

for step in steps:
    #이동하고자 하는 위치 확인
    next_row = row + step[0] #1
    next_column = column + step[1] #2

    #해당 위치로 이동이 가능하다면 카운트를 증가
    if next_row >= 1 and next_row <=8 and next_column >= 1 and next_column <= 8:
        result += 1
print(result)

#1 행을 돌 때 step이 steps를 돌면 step[0] = 행 / step[1] = 열이기 때문에 steps에 정의된 나이트가 이동할 수 있는 8가지의 방향을 다 차례로 돌면서 지금 현재 위치한 행열(c2라면 (2,3))에서 이동할 수 있는지를 판단하기위함이다. 

---

<문자열 재정렬>

a = input()
lst = []
int_num = 0

for i in a:
    if i.isalpha(): #알파벳인 경우를 알려주는 함수
        lst.append(i)
    else:
        int_num += int(i) #문자로 숫자를 입력받았기 때문에 형변환해주어 int_num함수에 넣어준다.

lst.sort() #알파벳만 모아둔 리스트의 알파벳을 오름차순으로 정렬해준다.


#숫자가 하나라도 존재할 경우엔 가장 뒤에 삽입해주는 과정
if int_num != 0:
    lst.append(str(int_num))

print("".join(lst))

- 문자열과 숫자를 따로 분리해서 정렬한 뒤 다시 출력해주면 되는 문제이다.