봄봄.devlog

📖 정의 - 방향성을 거스르지 않고 유향 그래프의 정점을 나열하는 방법 - 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 위해 사용하는 알고리즘 - 여러 개의 답이 존재할 수 있다. 📌 조건 - DAG(Directed Acyclic Graph)에만 적용 가능 - 사이클이 발생하는 경우 시작점이 불분명하므로 위상 정렬 불가 📌 구현 방법 1) Stack / DFS 이용 2) Queue 이용 진입 차수가 0인 정점을 queue에 삽입 queue에서 원소를 꺼내 연결된 모든 간선 제거 간선 제거 후 다시 1부터 반복 Point! 모든 정점을 방문했다면 queue에서 꺼낸 순서가 위상 정렬의 결과 모든 정점을 방문하기 전에 queue가 비면 사이클이 존재 -> 위상 정렬 불가 수행시간 O(V+E)..

[ DP 문제 풀이법 ] 1. 문제를 보고 규칙을 찾아서 점화식을 만든다. 2. 점화식을 이용하여 Top Down(재귀함수) 또는 Bottom Up(반복문) 방식으로 문제를 푼다. 왜 DP문제를 많이 풀어보라고 그러는지 알겠다...ㅠㅠ https://odysseyj.tistory.com/22 https://jyami.tistory.com/15

힙정렬(Heap Sort) 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식 퀵정렬과 병합정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다. 하지만 힙 자료구조가 많이 활용되고 있는 것은 사실! * 힙정렬 활용 1. 가장 크거나 가장 작은 값을 구할 때 최소힙 또는 최대힙의 루트값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능하다. 2. 최대 K만큼 떨어진 요소들을 정렬할 때 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다. 시간복잡도 ■ heapify 함수 수행 시간 heapify 함수는 힙 구조를 만들기 위해 이진 트리에서 자식 노드와 순서를 바꾸는 재귀호출을 한다. 힙 이진 트리의 높이는 logN이다. 따라서 heapify 함수의 재귀호출 횟수는 log..

1.개념 모든 경우의 수를 전부 탐색해 보지 않고, 어떤 기준(전략)으로 순서대로 하나씩 선택해 나가는 방식. 최적의 해를 구하는 방식을 그리디 알고리즘이라고 한다. 예를 들어, 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 가장 짧은 경로를 찾고 싶다고 가정하자. 가능한 모든 조합을 살표보는 방법은 5 x 4 x 3 x 2 x 1 = 120 가지 조합을 살펴봐야 한다. 10개의 도시라면 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800 가지 조합을 살펴봐야 한다. 너무 많다. 그리디 알고리즘은 어떤 적절한 기준(전략)으로 도시를 순서대로 하나씩 선택해 나가는 방식이다. 예를 들어, 임의의 도시를 하나 찍은 다음, 그 도시에서부터 시작하여, 현재 도시에서 출발..