본문 바로가기

분류 전체보기

 (51)
유니온 파인드 #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* using System.Collections; using System.Collections.Generic; using UnityEngine; [System.Serializable] public class Node { public Node(bool _isWall, int _x, int _y) { isWall = _isWall; x = _x; y = _y; } public bool isWall; public Node ParentNode; // G : 시작으로부터 이동했던 거리, H : |가로|+|세로| 장애물 무시하여 목표까지의 거리, F : G + H public int x, y, G, H; public int F { get { return G + H; } } } public class GameManage..
A * 알고리즘 길 찾기 알고리즘의 대표적인 예로 A * 알고리즘이 존재한다! 최단 경로로 시작점부터 목표지점까지 경로를 탐색하는 알고리즘으로서 매우 재미있고 유용한 알고리즘이다. A* 알고리즘은 지난 블로그에 작성한 DFS, BFS 알고리즘의 활용버전이라고 생각하며 앞으로 공부해볼 다익스타라 알고리즘과 흡사한 유형이라고 생각할 수 있겠다. A* 알고리즘 ● A * 알고리즘 : 출발 꼭짓점에서부터 목표 꼭짓점까지 최단 경로를 탐색하는 휴라스틱기반의 그래프 탐색 알고리즘. 계산 방식 ● F(n) = g(n) + h(n) - g(n) = 시작 노드부터 현재 노드까지의 비용 - h(n) = 현재 노드에서 목표 노드까지의 예상 비용 보통 h(n)을 휴리스틱 함수라고 일컫는다. 해당 휴리스틱 함수를 어떻게 지정하냐에 따라, 알고..
Fill 함수 Fill 함수란? 일반적으로 배열에서 초기화를 진행하였을때, 특정 원소를 초기화 시키거나 모든 값을 초기화 시켜야할 때의 작업을 단순하게 알고리즘으로 초기화시켜주는 함수이다. 어렵게 풀이한것 같은데 다음과 같이 설명을 이어서 하자면, #include using namespace std; int main() { int arr[5]; for (int i = 0; i < 5; i++) { arr[i] = 10; } for (int i = 0; i < 5; i++) { cout
SWaD 1주차 문제 1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. 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..

티스토리툴바