Algorithm/Theory
프림 알고리즘 (Prim Algorithm)
👉 크루스칼 알고리즘과 같은 원리로 동작하는 또 다른 스패닝 트리 알고리즘이다. 💡 크루스칼 알고리즘이란? 참고 : https://withseungryu.tistory.com/70?category=753127 크루스칼 알고리즘 (Kruskal Algorithm) 👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 � withseungryu.tistory.com 프림 알고리즘과 크루스칼 알고리즘의 큰 차이는 진행 방식입니다. 크루스칼 알고리즘은 여기저기서 산발적으로 만들어진 트리의 조각들을 합쳐 스피닝 트리를 만드는 방법이고, 프림 알고리즘은 하나의 시작점으..
크루스칼 알고리즘 (Kruskal Algorithm)
👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식으로 동작합니다. 하지만, 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것이 아닌, 사이클이 생기는 간선을 고려해 제외 해줍니다. 👉 동작하는 과정 위 그래프를 보면 가중치가 1인 간선, 2인 간선, 3.. 순서대로 선택해 가고 있습니다. 이때 4번째에서 5번째를 보면 가중치가 3인 간선들이 남아 있는데도 불구하고, 4인 (c,d) 간선이 추가됩니다. 그 이유는 3인 간선들이 추가되면 트리..
Union-Find, Disjoint Set (유니온-파인드, 상호 배타적 집합)
☞ Union-Find 란? 상호 배타적인 부분 집합(Disjoint Set)들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조 Union-Find에는 자료 구조에 명칭에 맞게 연산이 초기화(init), 합치기(union) 그리고 찾기(find)로 이루어져 있습니다. 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화 합치기 연산 : 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합치는 연산 찾기 연산 : 어떤 원소가 주어질 때 이 원소가 속한 집합을 반환하는 연산 ☞ 상호 배타적 집합을 표현하는 방법은 2가지가 있는데, 첫번째는 배열입니다. 하지만 배열로 표현을 하면 합치기 연산에 드는 시간이 많이 걸리기 때문에 Union-Find 자료 구조 특성 상 효율적이지 못합니다. 그..
세그먼트 트리 (구간 트리, Segment Tree)
☞ 세그먼트 트리란 이름 그대로 저장된 자료를 적절히 구간별로 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 해주는 트리입니다. 예를 들어 A={1,2,3,4,5}에서 [2,4] 구간의 최소치를 알고 싶다면 해당 배열을 순회하며 찾는 방법도 있지만, 해당 배열을 전처리해 세그먼트 트리를 생성해 더욱 더 빠르게 구현 할 수 있습니다. A배열을 세그먼트 트리로 바꾼 후 -> 아래처럼 구간별로 나눠 세그먼트 트리를 만들 수 있다. ☞ 이렇게 이론적으로만 설명했지만, 코드 구현에 많은 어려움이 있을 수 있습니다. 그래서 세그먼트 트리 문제의 한 유형인 구간 최소 쿼리(range minimum query,RMQ)를 구현해보겠습니다. ※ 여기서 중요한 점은 세그먼트 트리에 초기 크기를 설정해줘야하는데 가장..
벨만-포드 알고리즘 (Bellman-Ford Algorithm)
☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로를 구해도 될까? -> 정당성에 성립되지 않습니다. 따라서 음수 간선이 존재하고 음수 사이클이 존재한다는 것을 확인하고 싶을 때 Bellman-Ford Algorithm을 사용해야합니다. ☞ 벨만-포드 알고리즘이란 무엇일까? 벨만포드 알고리즘 원리는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식입니다. 여기서 상한은 upper 배열에 저장하며 이 upper의 값은 알고리즘이 진행됨에 따라 점점 줄어들고 알고리즘이 종료되면 실제 최단 거리를 담게 되는 원리입니다. ☞ 벨만-포드 알고리즘 동작..
[c++] 입력은 여러 개의 테스트 케이스로 이루어져 있다.
문제의 조건에 이런 까다로운 것이 있을 때, c++에서는 어떻게 해결하면 될까? ● 보통 c++을 사용하는 개발자들이라면 scanf 대신 cin을 많이 사용 할 것이다. cin에는 EOF라는 모듈이 있는데, eof 기능을 사용하면 쉽게 해결된다. int a, b; while (true) { cin >> a; if (cin.eof() == true) { break; } //여기에 결과 값 입력! } 여기서 주목해야할 점은 cin.eof인데 ctrl+x를 입력할 때 프로그램에 끝냄 명령을 주는데, 이때 cin에 입력받은 값이 없을 때 신호를 주면, cin.eof는 true값을 반환을 하여 while문을 빠져나오게 된다. 따라서, 쉽게 저 조건을 해결 할 수 있게된다. 궁금하신 것이 있으시다면 언제든지 댓글로..