본문 바로가기

알고리즘

 (11)
유니온 파인드 #include #include #include using namespace std; // 각 정점의 부모 노드 번호를 저장하는 배열 int parent[100] = { 0, }; int Find(int n) { // 배열의 인덱스와 값이 같다면 루트 노드 발견 if (parent[n] == n) return n; // 부모 노드의 번호를 전달하면서, 루트 노드를 찾을때까지 재귀호출 else return parent[n] == Find(parent[n]); } void Union(int x, int y) { x = Find(x); y = Find(y); // 루트 노드가 같다면 이미 연결 if (x == y) {// 더 작은 값이 부모 노드 if (x < y) { parent[y] = x; } else ..
A * 알고리즘 길 찾기 알고리즘의 대표적인 예로 A * 알고리즘이 존재한다! 최단 경로로 시작점부터 목표지점까지 경로를 탐색하는 알고리즘으로서 매우 재미있고 유용한 알고리즘이다. A* 알고리즘은 지난 블로그에 작성한 DFS, BFS 알고리즘의 활용버전이라고 생각하며 앞으로 공부해볼 다익스타라 알고리즘과 흡사한 유형이라고 생각할 수 있겠다. A* 알고리즘 ● A * 알고리즘 : 출발 꼭짓점에서부터 목표 꼭짓점까지 최단 경로를 탐색하는 휴라스틱기반의 그래프 탐색 알고리즘. 계산 방식 ● F(n) = g(n) + h(n) - g(n) = 시작 노드부터 현재 노드까지의 비용 - h(n) = 현재 노드에서 목표 노드까지의 예상 비용 보통 h(n)을 휴리스틱 함수라고 일컫는다. 해당 휴리스틱 함수를 어떻게 지정하냐에 따라, 알고..
다익스트라 알고리즘 다익스트라 알고리즘이란? 방향성을 갖거나 갖지않는 그래프에서 하나의 시작지점으로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘이다. 시작점을 아무곳으로 지정하여도 상관없다. 플로이드 알고리즘과의 차이점은 플로이드 알고리즘의 경우에는 간선의 가중치 값에 음수가 존재한다면, 문제가 발생할 수 있으며 다익스트라 알고리즘을 사용할때, 간선의 가중치 값에 음수가 존재한다면 사용할 수 없다는 차이점이 존재한다. 또한, 길찾기 알고리즘의 대표적인 예시의 A* 알고리즘은 길찾기에 필요한 최단거리를 정확하게 계산하는것이 아닌 근사값을 추정한다는 점에서 차이점이 존재한다. 아래와 같은 그래프의 모양을 띄웠을때, 다익스트라 알고리즘을 한눈으로 살펴볼 수 있다. 해당 다익스트라 알고리즘을 직접 구현해보자! #incl..
그리디 그리디란? 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘이다. 또는 관찰을 통해 탐색 범위를 줄이는 알고리즘이다. 이상적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. 3. 구현해서 문제를 통과한다. 현실적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿을 가진다. 3. 믿음을 가지고 구현해서 문제를 통과한다. 바로 연습문제를 통해 그리디 알고리즘을 맛을 보겠다. BOJ 11047번 : 동전 0 문제이다. 우리가 구현하고자 하는 것은 동전을 최소로 소모하면서 물겂값을 지불하는것이다. 우리는 50, 100 원의 갯수를 5개 이상 소..
해시 해시란? 해시 자료구조는 키에 대응되는 값을 저장하는 자료구조이다. 우리가 주민등록번호나 전화번호에 맞는 숫자와 이름의 쌍을 생성한다고, 예제를 두었을때, 특정 번호가 누구의 것인지를 알아내는 일을 할 때 쓰인다. 다음과 같이 전화번호가 존재한다고 예를 들었을 때, 모든 데이터를 배열에 삽입하여 관리할 수도 있다. 이렇게 하게 될때, 삽입 연산은 0(1) , 데이터를 찾는 과정을 수행할 시엔 0(N), 특정 데이터를 제거할 시엔 다시 O(N)의 시간이 소요된다. 그렇지만 해시 자료구조에선느 insert, erase, find, update 등의 연산이 모두 O(1)이다. 이와 같은 이유는 해시 함수는 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수의 역할을 수행하기 때문이다. 예를 들어, 3..
투 포인터 투 포인터란? 투 포인터란 배열에서 원래 이중 for문으로 O(N2)에 처리되는 작업을 2개 포인터의 움직으로 0(N)에 해결하는 알고리즘 그렇다면 투 포인터가 어떤 원리로 작동하기에 시간복잡도를 그렇게 줄일 수 있냐고 묻게 된다면 이렇게 말할 수 있다. 이중 for문에서 i = 0 일때 j 가 0부터 n -1 까지 돌고, 이처럼 i 가 n -1 일때까지 각각 인덱스는 i = 0, i = 1, i =... 일때까지 계산되어진 데이터를 전혀 쓰지않는다. 하지만 투 포인터를 이용한다면, i = 0일때 계산하면서 얻은 정보를 i = 1일때 활용하게된다. 그 전까지 계산된 값의 정보가 포인터의 이동으로 나타나는 것이다. 그래서 이전에 풀이하였던, 이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 있다. 반대로..
이분탐색 이분탐색이란? 이분 탐색이란 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이다. 위의 선형탐색의 배열을 한번 살펴보게 된다면, 특정 데이터를 찾기 위해서 우리는 기존에 앞의 모든 데이터를 순차적으로 탐색 후 우리가 찾고자 하는 데이터를 얻는 순으로 진행된다. 예를 들어, 22라는 데이터를 찾는다고 가정할때, 0 -> 1 -> 2 -> .. -> 6값에 도달하였을때 데이터를 찾게 된다. 반면에 이분탐색은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색으로 진행된다. 선형탐색이 0(N)에 동작하고 이분탐색이 0(lgN)에 동작하기 때문에 N의 크기가 커질수록 프로그램의 실행 속도에..
이진 검색 트리 이진 검색 트리의 단점: 이진 검색 트리 자체를 구현하는 것에 실수할 여지가 많고 자가 균형 트리가 적용되지 않은 이진 검색 트리는 시간복잡도가 안좋아서 높은 확률로 시간 초과가 발생하게 된다. 따라서, STL을 사용할 수 없는 환경에서의 이진 검색 트리를 사용하려고 노력하지 말자. 이진 트리 정의 이진 검색 트리를 정의하기 이전에 전에 공부했었던 이진 트리의 정의를 다시 떠올려보자. 각 노드의 자식이 2개 이하인 트리를 말합니다. 자식이 2개 이하이기 때문에 왼쪽 자식과 오른쪽 자식을 구별할 수 있다. 이진 검색 트리의 정의 왼쪽 서브트리의 모든 값은 모든 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리이다. 이진 검색 트리의 장점 순차적인 원소에 접근하게 된다면, 배열이나..

티스토리툴바