[ 이코테 강의 ] 그리디 & 구현 / DFS & BFS

 

👓 그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 바로 떠올릴 수 있는 능력을 요구한다
• 정당성 분석이 중요
  • 단순히 가장 좋아 보이는 것만 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

문제
단순히 매 상황에서 가장 큰 값만 고를 때 최적의 답을 고를 수 없을 때가 있다.

• 일반적인 알고리즘에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다
• 하지만 코테에서는 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다 == 탐욕법으로 풀릴수 있게 출제함

O(NlogN)의 시간복잡도를 가지는 방법

while True:
    target = (n // k) * k
    result += (n-target)
    n = target
    if n < k :
        break
    result +=1
    n//=k
result += (n-1)
print(result)

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

• 머릿속에 있는 알고리즘을 소스코드로 바뀌는 과정
• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
• 유형 예시
  • 알고리즘은 간단한데 코드가 길어지는 문제
  • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
  • 적절한 라이브러리를 찾아서 사용해야 하는 문제 (순열 / 조합 찾기 등)
• 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.
• for i in range(5): for j in range(5): print(i,j, end=" ") print()
• 가장 왼쪽 위가 행렬에서 첫번째 문제
• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 사용된다

그래프 탐색 알고리즘

• 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다
• 코테에서 자주 등장하는 유형

스택

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출) 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있음
• 파이썬에서 스택을 사용할때는 그냥 list를 사용해서 stack과 같이 사용하면 된다
• 시간은 O(1)이기 때문에 효율적이다.
• 맨 안쪽부터 출력하고 싶다면 list를 뒤입어야 한다 stack[::-1]

큐

• 먼저 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 입구와 출구가 모두 뚫려 있는 터널 같은 형태
• 대기열
• 리스트 자료형을 이용해서 큐를 구현할 수 있지만 시간복잡도가 높아서 좋지 않다.
  from collections import deque
queue = deque()

재귀 함수

• 자기 자신을 다시 호출하는 함수
• DFS를 실질적으로 구현하고자 할 때 자주 사용한다
• 함수가 stack에 담긴 것처럼 생각하면 된다

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다

최대공약수 계산 (유클리드 호제법)

• 두 개의 자연수에 대한 최대공약수를 구한다
• A>B일 때 A%B ==R, A,B 최대공약수는 B,R의 최대공약수와 같다

재귀 함수 사용의 유의 사항

• 복잡한 알고리즘을 간결하게 작성할 수 있지만 다른 사람이 이해하기 어려울 수 있음
• 모든 재귀 함수는 반복문을 이용해서 동일한 기능을 구현할 수 있다
• 재귀 함수가 반복문보다 유리한 경우 / 불리한 경우 다 있다
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다
  • 따라서 스택을 구현할 때 stack 라이브러리 대신에 재귀 함수를 하용하기도 한다

DFS(Depth-First Search)

• 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색
• 스택 자료구조(혹은 재귀 함수)를 이용한다
• 동작 과정
  • 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
  • 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
  • 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  • 더 이상 수행할 수 없을 때까지 반복

BFS(Breadth-First Search)

• 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색
• 큐 자료구조를 이용한다
  • 탐색 시작 노드를 큐에 삽입하고 방문 처리
  • 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모듀 큐에 삽입하고 방문 처리
• 특정 조건의 최단 거리 해결 목적으로 많이 사용한다
• from collections import deque

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

얼음틀
얼음틀 같은 네모네모모양도 서로 연결되었다고 파악하고 그래프 형태로 모델링 할 수 있음.

DFS

1. 특정한 지점의 주변 상,하,좌,우를 살표본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
2. 방문한 지점에서 다시 상하좌우를 살펴 방문을 진행하는 과정을 반복하면, 연결된 모든 지점 방문 가능