✅ PS/Algorithm

[Algorithm] DFS / BFS

대표적인 탐색 알고리즘인 DFS / BFS를 이해, 구현하기 위해 우선 스택과 큐 자료구조에 대해 간단히 알아보겠습니다.스택 - Stack스택은 박스를 쌓고 내리는 원리와 같습니다.먼저 들어온 것이 나중에 나가고 (FILO), 나중에 들어온 것이 먼저 나가는 (LIFO) 구조입니다.만약 1-3-5-7 순서로 들어왔다면, 7-5-3-1의 순서로 나가게 됩니다.파이썬에서는 별도의 라이브러리 사용없이 기본 리스트에서 append()와 pop() 메서드로 리스트를 스택처럼 사용할 수 있습니다.append() 메서드는 데이터를 리스트 가장 뒤쪽에 삽입하고, pop() 메서드는 데이터를 리스트의 가장 뒤쪽에서 꺼내기 때문입니다.큐 - Queue큐는 줄을 서는 원리와 같습니다.먼저 들어온 것이 먼저 나가고 (FIFO..

[Algorithm] Union Find (Disjoint Set Forest)

💡여러 개의 노드가 존재할 때 그 중 두 개의 노드를 선택해서 서로 같은 그래프에 존재하는지 판별하는 알고리즘정의Union Find는 크게 두 가지 명령으로 이루어집니다.Union(a, b) - 노드 a와 b를 간선으로 연결합니다.Connected(a, b) - 노드 a와 b를 연결하는 경로가 존재하는지 확인합니다. 활용되는 상황두 점 간 연결되었는지 확인하면서 간선을 계속 추가해보는 동적인 상◼︎ 그래프 전체가 미리 주어지고 형태가 변하지 않는 고정된 정적인 상황에서는 적절하지 않습니다.◼︎ 두 점 연결하는 최단 경로 찾는 것과는 다른 문제입니다.연결 상태를 조금씩 받아오는 동시에 연결 상태를 확인하는 상황 ex) 컴퓨터망에서 두 장비가 연결되었는지?비행기 노선도에서 임의의 두 지역이 연결되었는지? 구..

[Algorithm] 그리디 알고리즘 (Greedy Algorithm)

1. 그리디 알고리즘 (Greedy Algorithm) ? 현재 상황에서 지금 당장 좋은 것만 고르자 그리디 알고리즘은 이름 그대로 다양한 알고리즘 교재나 문서에서 "탐욕법"으로 소개되고 있는 알고리즘입니다. 탐욕적으로 매 순간 가장 좋은 것을 선택하고, 선택이 미래에 미칠 영향은 고려하지 않습니다. 그렇기 때문에 그리디 알고리즘은 최종적인 결과 도출에 대한 최적해를 보장하지 않습니다. 하지만 그리디 알고리즘은 간단하고 빠르기 때문에 해결할 문제가 그리디 알고리즘을 사용할 조건을 갖출 때 사용합니다. 즉, 그리디 알고리즘을 사용했을 때 최적의 해를 구할 수 있는 문제일 때 입니다. 2. 그리디 알고리즘의 정당성 판단 그리디 알고리즘이 최적의 해를 구할 수 있는 조건은 아래의 두 가지입니다. 탐욕 선택 속..