"벨만 포드(bellman-ford) 알고리즘 " 알고리즘 이름이 맘에 안든다. =3= 알고리즘이나 수학적 법칙을 보면 발견한 사람들의 이름으로 이름을 만든다. 직관적이지 않아서 계속 까먹게 된다. 직관적으로 이름을 지어줬으면 좋겠다. 예를 들어, "음수사이클 다익스트라" 이런식으로 ~  1. 최단 경로 트리 (shortest-path tree), 최적해 구조(optimal substructure 알고리즘이다. 답은 여러개가 존재 할 수 있으면 가중치가 있는 그래프로 최단 경로를 찾는다.  2. 음수 사이클의 유무를 확인할 수 있다. 다익스트라랑 다른 점!!으로 음수 사이클의 발생으로 최단 경로가 무한으로 빠지는 음수차이클을 찾는다.  3. 모든 음수 간선이 문제다 ? 아니다. (-) 마이너스 값이 있는..

" Algorithm/ KMP 알고리즘 " 🔸 KMP( Knuth, Morris, Prett ) Algorithm? 대표적인 상수시간 내에 할 수 있는 문자열 검색 알고리즘이다. 명칭은 알고리즘 쓰임새와 상관없이 만든 사람이름이다. 문자열 매칭 알고리즘이라고 부르는게(?) 더 좋을거 같다.  🔸 해답https://www.acmicpc.net/problem/1786"baekjoon 1786번 - 찾기"와 함께 kmp 알고리즘을 배우고 풀어보자. P: 패턴(길이: m) T: 텍스트(길이: n) 만약 모든 매칭을 하나하나 확인한다면? (n - m + 1) x m  = 시간 복잡도 O(nm)목표: 시간 목잡도 O(n) 만들기.  🔥 step 1.  찾으려는 문자열 전처리 과정 거치기 접두사(이을 접 : 接..

' binary search & lower bound & upper bound ' 코딩 테스트를 하다보면 이분 탐색을 자주하게 된다. 대부분 내장함수로 사용하면 되지만,  문제 종류에 따라서 직접 구현해 조건을 더해야 풀 수 있는 경우가 있다. c++ 기준으로 이진 탐색 함수는 총 3가지가 있다. 이 세가지 모두 이진 탐색이 기반인 알고리즘이므로 데이터가 오름차순으로 정렬이 되어 있어야 한다. 1. [ #include ]  std::binary_searchval값이 있는지 없는지 확인하는 알고리즘 [ return bool ] std::lower_bound를 이용하여 구현한 알고리즘. 2. [ #include ] std::lower_bound val값의 시작 위치를 찾는 알고리즘 3. [ #include..

공부 전 Tmi.매일 일 집 일 집 하니 꾸미는 날도 없고 나를 너무 대충대충 살게 두는 거 같아서 현타가 옵니다. 옷도 가방도 화장품도 안 산 지 오래 된 거 같아요. 나를 위한 소비도 없이 그냥 먹고 자고 일합니다. 이렇게 살면 좋을까? 라는 생각이 종종 듭니다. 잘 살고 있는건 아닌거 같죠 ? ㅠㅠ 공부도 조금 쉬었어요. 나의 속도로 공부하려고 했는데 남들의 속도를 보고 불안함을 느끼면서 우울감에 쉬는 것…? 참 아이러니합니다. (한심..) 백준 드디어 200개 돌파했습니다. 아직 적은 수지만 이번 연도에 500개는 넘고 싶네요. 지금은 정말 푸는 데 오래 걸리고 이전에 풀었던 거와 비슷한 문제여도 헤매는데 그러지 않을 날이 올까요? 현재 골드 2 입니다. 백준이 플레니넘이 되는 날 헌 번 더 Tm..

Sparse Table (스파스 테이블) 특징 방향 그래프 입니다.모든 점이 목적지가 있습니다.그 점을 타고 새로운 점으로 갑니다.2의 제곱근으로 도착한 점을 저장합니다. (1번, 2번, 4번, 8번 이동에 대한 배열을 모두 저장합니다.) 예제를 풀면서 설명하겠습니다. https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는www.acmicpc.n..

스터디에서 A* 알고리즘을 한 번 작성해보고 간단하게 콘솔로 띄어보고.. 유니티로 적용해보기로 하였다. 유니티로 옮기는 작업 벌써부터 걱정이 된다. 일단 A*알고리즘이 뭔지 정리를 해보자 ..A* 알고리즘은 다익스트라 알고리즘을 확장하여 만들어진 알고리즘으로 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다. 주로 게임에서 몬스터가 플레이어를 목표지점으로 이동하거나  자동 사냥 게임에서 플레이어가 타겟(몬스터나 다른 PC)을 향해 이동시킬 때 사용하는 알고리즘이다. 알고리즘다익스트라 알고리즘 A* 알고리즘목표점시작점 -> 나머지 모든 정점들까지의 최단 거리시작점 -> 목표점까지의 최단 거리 차후 경로 도출을 위한 함수f(n)현재 노드에서 가까운 노드부터..

프림(Prim) 알고리즘1. 그래프에서 시작점을 정한다 - (어떤 노드이어도 상관없음)2. 선택한 정점과 인접하는 정점들 중 최소 비용인 간선에 연결된 정점을 선택한다.3. 모든 정점이 선택될 때까지 1,2과정을 반복한다.※ 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리를 구성하는데 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 정렬 후 가장 최소 비용으로 간선을 선택하기 때문에 사이클이 발생하는지 판단하면서 진행해야 한다.

크루스칼(Kruscal) 알고리즘 최소 비용 신장트리(Minimum Spanning Tree) 대표적인 알고리즘 중 하나로 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용한 알고리즘이다. [Algorithm] 최소 비용 신장 트리 (MST, Minimum SpanningTree) (tistory.com) [Algorithm] 최소 비용 신장 트리 (MST, Minimum SpanningTree)신장트리(SpanningTree) 그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 의미한다. 특징으로는 N개의 정점을 가지는 그래프의 최소 간선(edge)의 수는 (N-1)개cclient.tistory.com이전에 포스팅한 최소 비용 신장 트리의 다섯까지 특징..

신장트리(SpanningTree)그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 의미한다. 특징으로는 N개의 정점을 가지는 그래프의 최소 간선(edge)의 수는 (N-1)개이다. 최소 비용 신장 트리 (MST, Minimum SpanningTree)신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다. 최소 비용 신장 트리는 그리디 ..

Union-Find(유니온 파인드)그래프 알고리즘 중 하나로 서로소(disjoint sets) 집합 자료구조이다. 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.1. union(합집합)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.       - A와 B의 루트 노트 A', B'를 각각 찾는다.       - A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.17. Union-Find(..