[Python] 코딩 테스트 대비 주요 알고리즘&함수 정리

 

코테를 준비하면서 자주 사용하는 알고리즘 & 함수를 정리합니다.

 

Queue

선입 선출의 구조로 queue 라이브러리를 사용합니다.

import queue
data = queue.Queue()
print(type(data))

 

queue에 데이터 넣기 

data.put(2)
data.put(3)
data.put(4)

 

데이터 출력 

print(data.get())
print(data.get())
print(data.get())

 

Stack 

후입 선출 구조로 별도 라이브러리 없이 파이썬의 리스트를 사용합니다.

stack = []

 

데이터 넣기 

stack.append(2)
stack.append(3)
stack.append(4)

 

데이터 출력 

print(stack.pop())
print(stack.pop())
print(stack.pop())

 

2차원 배열 

2차원 배열으로 알고리즘 문제를 풀 때, 배열 뒤집기와 특정 인덱스 기준 정렬을 자주 사용합니다.

 

1. 배열 뒤집기

array = [[i for i in range(4)] for j in range(5)]

out > [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]

위와 같이 4*5의 배열이 주어졌을 경우, 아래 코드를 통해서 5*4 배열로 전환해서 사용할 수 있습니다.

new_array = list(map(list,zip(*array)))
print(new_array)

out > [[0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3]]

 

2. 특정 인덱스 기준 정렬

array = [[1,2,1],[2,4,1],[5,4,2],[1,1,4]]

out > [[1, 2, 1], [2, 4, 1], [5, 4, 2], [1, 1, 4]]

2차원 배열이 주어졌을 경우, 람다식을 활용해서 0번째 인덱스가 아닌 첫번째 인덱스를 기준으로 정렬할 수 있습니다.

array.sort(key = lambda data : data[1]) #1번 인덱스 기준 정렬
print(array)

out > [[1, 1, 4], [1, 2, 1], [2, 4, 1], [5, 4, 2]]

-> (1번 인덱스가 오름차순으로 정렬 됨)

 

이를 활용해서 다중 인덱스 기준으로 정렬도 가능합니다.

# 평소 -> 0번 인덱스 기준 , 아래 예시 -> 0,1번 인덱스 기준
print(sorted(array,key = lambda x:  (x[0],x[1])))

 

문자열

 

문자열에서 특정 문자를 삭제하는 방법을 사용합니다.

파이썬 내장 라이브러리인 re를 사용할 수 있으며, .sub() 함수를 사용합니다.

import re
string = "AA**BB#@$CC 가나다-123"

0~9 (숫자) 제거하기

print(re.sub(r"[0-9]","",string))

out > AA**BB#@$CC 가나다-

 

알파벳 남기고 모두 제거하기 

print(re.sub(r"[^a-zA-Z]]","",string))

 

DRF, BFS

루트 노드와 그래프 리스트를 지정하고, DRF,BFS 탐색 방법을 사용합니다.

root_node = 1
graph_list = {
    1: set([3,4]),
    2: set([3,4,5]),
    3 :set([1,5]),
    4 :set([1]),
    5 :set([2,6]),
    6: set([3,5]),
}

 

DFS - 깊이 우선 탐색 

DFS의 경우 스택을 사용해서 깊이 우선 탐색을 진행합니다.

방문 노드를 제외한 연걸 된 노드들을 가져와서 stack 넣고 탐색하는 과정을 반복합니다.

# DFS 깊이 우선 탐색
def DFS(graph, root): # stack
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack+= graph[n] - set(visited)
    return visited
print("DFS : ",DFS(graph_list,root_node))

BFS - 너비 우선 탐색

BFS의 경우 양방향 큐인 deque를 사용해서 너비 우선 탐색을 진행합니다.

방문 노드를 제외한 연결 된 노드들을 가져와서 queue에 넣고 탐색하는 과정을 반복합니다.

# BFS 너비 우선 탐색
from collections import  deque
def BFS(graph, root): # deque
    visited = []
    queue = deque([root])
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
print("BFS : ",BFS(graph_list,root_node))

 

순열과 조합

자주 나오지는 않지만, 사용방법을 외워두면 빠른 속도의 알고리즘을 구현할 수 있습니다.

# 중복 순열 # (1,1) 가능
from itertools import product
data = ["1","2","3"]

print(list(product(data,repeat = 2)))

# 순열 (ab != ba)
from itertools import permutations
print(list(permutations(data,2)))

# 조합 ( ab == ba)
from itertools import combinations
print(list(combinations(data,2)))

# 중복 조합 # (1,1) 가능
from itertools import combinations_with_replacement
print(list(combinations_with_replacement(data,2)))