파이썬 알고리즘 공부 - (1) 그리디, 구현, DFS, BFS

 

 

📍그리디 알고리즘 : 탐욕법 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

ex) 거스름돈 문제, 1이 될 때까지 

 

* 숫자 09380 를 받아서 왼쪽부터 숫자를 곱하거나 더해서 가장 큰 값이 되게 하는 문제

result = int(data[0])

for i in range(1, len(data)):
	num = int(data[i])
    if num <= 1 or result <= 1:
    	result += num
    else:
    	result *= num
        
print(result)

 

📍구현 문제 : 풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제 

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

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

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

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

 

*2차원 공간 -> 행렬로 표현, 방향 벡터 활용

 

예시) 상하좌우 문제 

n = int(input())
x, y = 1,1
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

 

시각 문제 - 완전탐색 문제 

-> 가능한 모든 경우의 수를 탐색

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):
            	count += 1

 

아스키코드 활용해서 알파벳 -> 숫자 

data = input()
result = []
value = 0

for x in data:
	if x.isalpha():
    	result.append(x)
    else:
    	value += int(x)

result.sort()

if value != 0:
	result.append(str(value))
    
print (''.join(result)) #리스트를 문자열로 변환

 

---

그래프 탐색 알고리즘

탐색 : 원하는 데이터를 찾는 과정

 

DFS/BFS

---

* 스택 자료구조 (선입후출) 입구와 출구가 동일함

파이썬에서는 리스트에서 append() , pop() 함수를 이용하는 게 스택 

 

* 큐 자료구조 (선입선출) 입구와 출구가 다름

import collections import deque #라이브러리 

queue = deque()

queue.append(), queue.popleft() #함수 이용

 

* 재귀함수 : 자기자신을 다시 호출하는 함수  -> 함수가 스택과 비슷한 원리로 실행됨

def recursive_function():
    print("재귀함수")
    recursive_function()
recursive_function()

 

-> 파이썬에서는 최대 깊이가 정해져 있어 중간에 오류가 생길 수 있음 

-> 종료 조건을 명시해야 함

예시) 팩토리얼 구현에서 n! 를 n*(n-1)*(n-2).. 반복문보다 n* (n-1)! 로 구현하는 것이 더 코드 길이 상 더 효과적이다. 

 

재귀함수를 효과적으로 작성하기 위한 방법 : 유클리드 호제법 : 최대공약수 계산

*유클리드 호제법 : a, b에 대하여 a를 b로 나눈 나머지를 r이라고 한다. a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

 

모든 재귀함수는 반복문을 이용해서 동일한 기능을 구현할 수 있다. 

---

📍DFS : 깊이 우선 탐색

-> 깊은 부분을 우선적으로 탐색

스택 자료구조(혹은 재귀함수)를 이용

graph = [
[],
[2,3,8]
...
]

#모두 방문하지 않았다고 정의
visited = [False] * 9 

#dfs 메서드 정의 
def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
dfs(graph, 1, visited)

 

📍BFS : 너비 우선 탐색

-> 가까운 노드부터 우선적으로 탐색

큐 자료구조 이용

from collections import deque

graph = [
[],
[2,3,8],
...
]

visited = [False] * 9

# bfs 메서드 정의
def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
    	v = queue.popleft()
        print(v, end='')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
                
bfs(graph, 1, visited)