"(백준/c++) 1238 - 파티 / 최단경로그래프, 플로이드 워샬"https://www.acmicpc.net/problem/1238 🏆 solved.ac 난이도: 골드3 🔸 문제 핵심 단방향 도로갔다가 돌아오는 최단경로  🔹 주요 코드 부분파란줄: form ~ stopper 시작점부터 경유지까지 무한이면, 연결되어 있지 않는다는 뜻이기 때문에 무시해주자.노란줄: 시작점부터 도착점 > 시작점부터 경유지 + 경유지부터 도착점이 구조를 외우지 말고 완화(relax)를 이해하자. #include#include#includeusing namespace std;//vector> students[1'001]; int students[1'001][1'001];int result[1'001];int main(v..

"벨만 포드(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..

스터디에서 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(..

0. STL이란 뭔가요? Standard Template Library로 C++의 템플릿을 사용하여 표준으로 정리된 라이브러리입니다. 반복자/컨테이너/알고리즘/함수 객체등의 라이브러리로 구성됩니다. 1. 시퀀스 컨테이너, 연관 컨테이너, 어뎁터 컨테이너에 대해서 설명해주세요. (자료의 구조로 구분을 하면…)시퀀스 컨테이너는 자료를 입력한 순서대로 저장하기 때문에 저장 검색 알고리즘이라고 불립니다. 많지 않은 양의 자료/검색속도가 중요하지 않은 경우에 사용되며 vector, list, string, dequue등이 이에 해당합니다. 연관 컨테이너는 일정한 규칙에 따라 자료를 조직화하여 저장하는 것을 말합니다. 자료를 정렬하여 저장하기 때문에 검색에 유리하고 많은 양의 자료/빠른 검색이 중요할 때 사용합니다..