[알고리즘]구현

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

 

구현 하기 까다로운 문제

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야 하는) 문제 등

 

알고리즘 중 "구현"은 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있다..

또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다.

 

예를 들어, 파이썬으로 코테를 보는데 N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한줄로 세우는 경우(순열)을 구해야 하는 문제를 만나면 어떻게 할것인가?? 무작정 기능을 전부 작성할 수도 있다.
하지만 파이썬의 itertools와 같은 표준 라이브러리로 쉽게 짜는 방법도 있다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결방법이다.
👉🏻 이를 두고 "피지컬이 좋다." 라고 하는데,, 이렇게 되기 위해선 파이썬의 문법 코어가 중요한것 같다.(이 부분에 대해서 앞으로도 지속적인 노력을 할 예정이다🤭)

 

구현의 예 중에는 완전탐색과 시뮬레이션 문제들이 있는데, 이는 삼전 코테에서 자주 등장한다고 한다..~~(삼전은 약간 구현 문제, DFS/BFS를 주로 내는것 같다)

완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법이고,
시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미한다.
둘 다 구현이 핵심이 되는 경우가 많다...

 

보통의 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.
문제의 길이를 보고 지레 겁을 먹게되는데..(나란 겁쟁이....😭), 고차원적인 사고력을 요구하는 문제는 잘 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀수 있다고 하니 너무 겁먹지 않아도 될것 같다.

구현 유형의 문제는 C/C++이나 자바로 문제를 풀때 더욱 어렵게 다가온다. 왜냐하면 문자열을 처리하거나 큰 정수를 처리하는 문제가 파이썬보다 훨씬 까다롭고 복잡하기 때문이다.(파이썬 최공❤️)
실제로 나와 같은 경우는 학교 수업에서는 거의 모든 자료구조와 알고리즘 코드를 C++을 사용하는데, 확실히 푸는 속도나 고려해야될것이 더욱 많다고 느껴졌다. 그래서 파이썬에 대한 소중함을 느끼게 되는 순간이 많다.

출처: 이코테

자동 채점 방식을 이용하는 코딩 테스트 환경에서는 점점 Pypy3를 지원하는곳도 늘어나고 있다고 한다.
Pypy3는 python3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. 
👉🏻 python이 코테에서 불리한 조건(실행속도가 느린것)이 점점 없어지는 추세라는 뜻!!

예제 문제를 풀어봅시다..

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

#상하좌우

n = int(input())

go = list(map(str,input().split()))
x=1
y=1

for goes in go:
    if goes=='D':
        if x+1 > n:
            continue
        else :
            x = x+1
    elif goes=='U':
        if x-1 <= 0:
            continue
        else :
            x = x-1
    elif goes=='R':
        if y+1 > n:
            continue
        else :
            y = y+1
    elif goes=='L':
        if y-1 <= 0:
            continue
        else :
            y = y-1

print(f"{x} {y}")

 

#상하좌우 다른 답

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)

 

이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례한게 된다. 예를 들어 이동 횟수가 N번인 경우 시간 복잡도는 O(N)이다.

위의 문제는 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 대표적인 문제이다.

⭐️ 코테에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 알고리즘이나 구현 문제라고 한다. 난이도가 낮은 만큼 합격을 좌우하기 때문에 매우 중요한 유형이라고 볼 수 있다. 

---

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

#시각

n = int(input())

cnt = 0
for k in range(n+1):
    if k==3:
        cnt+=60*60
        continue
    for i in range(60):
        if 0<=i-30<10: #30대면 모두 포함
            cnt += 60
            continue
        else:
            if (i-3)%10 == 0:
                cnt += 60
                continue
        for j in range(60):
            if 0<=j-30<10: #30대면 모두 포함
                cnt += 1
            else:
                if (j-3)%10 == 0:
                    cnt += 1

print(cnt)

#시각 다른 풀이(문자열 풀이)
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)

 

위 문제와 같은 유형은 "완전탐색" 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.

완전 탐색 문제 또한 구현이 중요한 대표적인 문제유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있기 때문에 데이터 개수가 큰 경우에는 정상적으로 동작하지 않을 수도 있다.

그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야할 전체 데이터 개수가 100만개 이하일때 완전 탐색을 사용하면 적절하다..

 

---

 

실전 문제를 풀어봅시다..

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

#왕실의 나이트(ㄹㅇ 수준떨어지는 문제풀이)
w = input()

col = w[0]
row = w[1]

if w[0] == 'a' or w[0] == 'h':
    if w[1]=='1' or w[1]=='8':
        cnt=2
    elif w[1]=='2' or w[1] =='7':
        cnt=3
    else:
        cnt=4
elif w[0] == 'b'  or w[0] == 'g':
    if w[1]=='1' or w[1]=='8':
        cnt=3
    elif w[1]=='2' or w[1] =='7':
        cnt=4
    else:
        cnt=6
else:
    if w[1]=='1' or w[1]=='8':
        cnt=4
    elif w[1]=='2' or w[1] =='7':
        cnt=6
    else:
        cnt=8

print(cnt)

이건 내가 문제만 보고 정말 "구현"만을 하기 위해서 작성한 수준이 떨어지는 풀이 코드이다. 이후에 좀 더 배운 이론을 활용하여 코드를 작성한것은 아래와 같다.

# 왕실의 나이트(이론 설명 좀 듣고 다시 풀어봄)

w = input()

col = w[0]
row = w[1]
#int(ord(w[1])-int(ord('a')) + 1 로 미리 표현해줄 수도 있음

# 나이트가 갈 수 있는 전체 경우의 수
steps = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
cnt = 0
for step in steps:
    nr = int(row) + step[0]
    nc = ord(col)-96 + step[1]

    if 0 < nr < 9 and 0 < nc < 9:
        cnt += 1

print(cnt)

위 문제의 소스 코드에서는 steps의 변수가 dx와 dy 변수의 기능을 대신하여 수행한다는 점을 기억하자

 

---

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

# 게임 개발
n, m = map(int, input().split())  # 맵 크기
a, b, c = map(int, input().split())  # 현재 캐릭터의 위치(a,b)와 바라보고 있는 방향(c)

li = [[0 for col in range(m)] for row in range(n)]
cmp = [[0 for col in range(m)] for row in range(n)]

for i in range(n):  # 배열에 저장 성공
    li[i] = list(map(int, input().split()))  # 0이 육지, 1이 바다

for i in range(n):
    for j in range(m):
        cmp[i][j] = 1  # 1로 초기화


def game(row, col, c, result):
    if c == 0:  # 북
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        dc = [3, 2, 1, 0]
    elif c == 1:  # 동
        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]
        dc = [0, 3, 2, 1]
    elif c == 2:  # 남
        dx = [1, 0, -1, 0]
        dy = [0, -1, 0, 1]
        dc = [1, 0, 3, 2]
    elif c == 3:  # 서
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        dc = [2, 1, 0, 3]

    cnt = 0  # 4면 모두 못갈때
    for i in range(4):
        ny = row + dy[i]
        nx = col + dx[i]
        nc = dc[i]

        if li[ny][nx] == 0 and cmp[ny][nx] == 1:  # 해당하는 곳이 육지이고 한번도 지나간적이 없다면
            cmp[ny][nx] = 0  # 지나갔다는 표시
            result += 1
            game(ny, nx, nc, result)
        elif li[ny][nx] == 1 or cmp[ny][nx] == 0:
            cnt += 1
            game(row, col, nc, result)

    if cnt == 4:
        for i in range(4):
            if dc[i] == nc:
                last = i
                break
        if dy[last] != 0:
            ny = row - dy[i]  # 뒤로가기
            nx = col
            if li[ny][nx] == 1:
                return result
            game(ny, nx, nc, result)
        elif dx[last] != 0:
            ny = row
            nx = col - dx[i]  # 뒤로가기

            if li[ny][nx] == 1:
                return result
            game(ny, nx, nc, result)


game(a, b, c, 0)

ㄴ 처음엔 이런식으로 코드를 작성했었다. 재귀함수를 이용할 계획이었다. 하지만

"RecursionError: maximum recursion depth exceeded in comparison"

이런 에러가 나타났었고, 이 에러가 난 이유는 파이썬에서는 재귀의 한도가 시스템의 안정을 위해 정해져있는데, 그 한도를 넘었기 때문이다. 이후 해결방법을 인터넷으로 찾아보고다가 다음과 같은 방법을 찾아냈다. 

import sys
sys.setrecursionlimit(10**7)

 이와 같이 sys 모듈을 불러와서 재귀의 한도를 늘려주면 해결되는 문제이다.
하지만 위의 코드를 붙여주고 실행을 해보았지만 코드가 계속 실행되고, 정답은 나오질 않았다...

그래서 재귀함수 말고 while문을 이용해서 코드를 다시 작성해보았다.

#게임 개발 2트(while문으로)
n,m = map(int,input().split()) #맵 크기
a,b,c = map(int, input().split()) #현재 캐릭터의 위치(a,b)와 바라보고 있는 방향(c)

l = [[0 for col in range(m)] for row in range(n)]
cmp = [[0 for col in range(m)] for row in range(n)]

for i in range(n): #배열에 저장 성공
    l[i] = list(map(int, input().split())) #0이 육지, 1이 바다

for i in range(n):
    for j in range(m):
        cmp[i][j]=1 #1로 초기화

result = 1 #초기 위치 좌표
row = a
col = b
cmp[row][col]=0

while True:
    if c==0: #북
        dx = [-1,0,1,0]
        dy = [0,1,0,-1]
        dc = [3,2,1,0]
    elif c==1: #동
        dx = [0,-1,0,1]
        dy = [-1,0,1,0]
        dc = [0,3,2,1]
    elif c==2: #남
        dx = [1,0,-1,0]
        dy = [0,-1,0,1]
        dc = [1,0,3,2]
    elif c==3: #서
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        dc = [2,1,0,3]

    cnt=0 #4면 모두 못갈때
    for i in range(4):
        ny = row + dy[i]
        nx = col + dx[i]
        nc = dc[i]
        if l[ny][nx]==0 and cmp[ny][nx]==1: #해당하는 곳이 육지이고 한번도 지나간적이 없다면
            cmp[ny][nx] = 0 #지나갔다는 표시
            result +=1
            # game(ny, nx, nc, result)
            row = ny
            col = nx
            c = nc
            continue
        elif l[ny][nx]==1 or cmp[ny][nx]==0:
            cnt +=1
            # game(row, col, nc,result)
            c = nc
            continue

    if cnt ==4:
        for i in range(4):
            if dc[i]== nc:
                last = i
                break
        if dy[last]!=0:
            ny = row-dy[i] #뒤로가기
            nx = col
            if l[ny][nx]==1:
                break
            # game(ny, nx, nc, result)
            row = ny
            col = nx
            c = nc
            continue
        elif dx[last]!=0:
            ny = row
            nx = col-dx[i] #뒤로가기
            if l[ny][nx]==1:
                break
            # game(ny, nx, nc, result)
            row = ny
            col = nx
            c = nc
            continue

print(result)

# 방문한 좌표를 확인해보기 위해서 출력
# for i in range(n): 
#     for j in range(m):
#         print(cmp[i][j])
#     print("-")

이렇게 while문을 사용해서 코드를 작성하니 정답도 맞았고, 시간도 전혀 오래걸리지 않았다!!

책에서 정답으로 제시한 코드는 다음과 같다. 👇🏻👇🏻👇🏻
내가 작성한 while문 버전의 코드와 로직이 거의 비슷한데, 나는 바라보고 있는 방향 마다의 움질 일 수 있는 dx와 dy를 따로 설정해준 반면 책의 정답코드는 dx와 dy는 고정해놓고, 방향 바꾸는 함수를 turn_left()로 설정하고 방향이 바뀔 때마다 함수를 호출하도록 설정했다.

#게임 개발(정답)

n, m = map(int,input())

#방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화(컴프리헨션 문법을 사용한 2차원 리스트 초기화)
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():
    global direction #direction은 전역변수임 
    direction -=1
    if direction == -1: #만약 방향이 -1이 되면 3으로 취급해서 다시~
        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 #방향전환 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 #방향전환 0으로 초기화

#정답 출력
print(count)

 

⭐️⭐️⭐️ 이 문제는 방향을 설정해서 이동하는 문제로, 이와 같은 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.
이와 같이 코드를 작성하면, 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있다는 점에서 매우 유용하다.