잡담연구소

1 ) 다익스트라란 ? : 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘 그래프의 방향 유무는 상관없다 간선 중 하나라도 가중치가 음수라면 사용할 수 없다. 이런 경우는 벨만포드를 사용한다. 플로이드 와샬은 모든 정점에서 모든정점까지의 최단 거리를 구하지만 , 다익스트라는 한 정점에서부터 모든 저점까지의 최단 거리를 구하는 알고리즘이다. 다익스트라가 DP문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져있기때문이다. 코드를 보면 한 점까지의 최단거리를 구할 때 이전까지의 최단거리로 사용하는걸 확인할 수 있다. ✨최단 거리를 구하는 알고리즘이 꽤 많다. 각 알고리즘마다의 어떤 점이 다른 지를 기억하고 있어야한다. 2 ) 다익스트라 알고리즘의 원리 리스트로 단순구..

3주차에 힙정렬을 구현하면서 힙에 대해서 간략하게 정리했었다. 3주차 힙정렬 👉 blahblahlab.tistory.com/33 1) 힙이란 ? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure) 부모노드와 자식노드 사이에 일정한 대소관계가 존재한다. 부모노드가 자식노드보다 더 크면 최대힙(max heap) 부모노드가 자식노드보다 더 작으면 최소힙(min heap) 형제끼리는 대소관계가 존재하지 않는다. 부모와 자식간의 인덱스는 왼쪽자식 = 2 * 부모노드 , 오른쪽 자식 = 2 * 부모노드 +1 을 성립한다. 그림으로 보는 게 훨씬 직관적이다. 부모노드가 자식노드보다 큰 최대힙의 ..

스터디 숙제는 아니지만 공부하다 보니 DP 대표적인 알고리즘인 LIS에 대해 공부하게 되었다. 1. Long Increasing Subsequence 란 ? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 오름차순으로 정렬되어야하므로 원소들 사이의 대소관계 즉, 이전 원소보다는 그 뒤에 오는 원소가 더 커야한다는 조건이 존재한다. 예를 들어 10 20 10 30 20 50 이라고 하자. 이때 만들 수 있는 증가하는 부분 수열은 {10, 20, 30 ,50} , {20 ,50} , {10,30,50} 등 여러가지이다. 이중 가장 긴 {10, 20, 30 ,50} 부..

1) 벨만포드 알고리즘 개념 갓키백과에 따르면 벨만포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 다익스트라 알고리즘과 같이 한 정점에서부터 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용한다. 모든 경우의 수를 다 탐색하며 확인한다. 정점이 1,2,3,4가 있다면 1에서 각 점 2,3,4로 가는데 걸리는 각각의 최소비용을 구하는데 사용할 수 있다. 시간복잡도도 다익스트라보다 크지만 벨만포드의 장점은 가중치가 음수일 때 사용가능하다는 것이다. 2) 벨만포드 알고리즘의 원리 기본 아이디어는 a라는 시작노드에서 z라는 정점까지의 최소비용을 구하려면 이미 y까지의 경로가 최단경로라 믿고 a에서 y까지의 최단경로 + y에서 z까지의 가중치를 더하는 것이다. 그렇다면 시작노드..

3주차 이번 주 주제는 이었다. 힙정렬에 대해서 공부하기전에 힙에 대해 알아야 한다. 0) 힙이란 ? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure) 부모노드와 자식노드 사이에 일정한 대소관계가 존재한다. 부모노드가 자식노드보다 더 크면 최대힙(max heap) 부모노드가 자식노드보다 더 작으면 최소힙(min heap) 형제끼리는 대소관계가 존재하지 않는다. 부모와 자식간의 인덱스는 왼쪽자식 = 2 * 부모노드 , 오른쪽 자식 = 2 * 부모노드 +1 을 성립한다. 그림으로 보는 게 훨씬 직관적이다. 부모노드가 자식노드보다 큰 최대힙의 경우이다. 형제끼리는 대소관계가 없다. 1 ..

1) 위상정렬의 개념 갓키백과에 따르면 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것이라고 한다. 방향이 있는 그래프에서 그 방향을 따라가며 즉 선후 관계를 지키며 모든 정점을 정렬하는 것이라고 생각한다. 선후관계 즉 순서가 있어야한다. 그래서 사이클이 존재하면 위상정렬을 사용할 수 없다. 이런 걸 DAG : 사이클이 존재하지 않는 방향 그래프 라고 한다. 고등학교 수학을 수1 > 수2 > 미적1 > 미적2 인걸 예로 들 수 있겠다. 2) 위상정렬 원리 스터디장님이 설명해주시는데 진입차수가 대체 뭔지 이해가 안갔다,,,, 내 머리,,,, 진입차수 : 특정 정점과 연결되어있는 선행되어야 하는 정점들 진입차수가 0인 정점을 큐에 넣는다. 여러 개인 경우 상관없다. 넣고싶은대..