헝가리안 알고리즘 ( Hungarian Algorithm )헝가리안 알고리즘은 여러 작업을 여러 사람에게 배정할 때 , 전체 비용이 최소가 되도록 1대1 매칭을 찾는 알고리즘이다.예를 들어 이런 상황이라고 가정한다.사람작업 A작업 B작업 C욱진927한영643지은581 각 숫자는 그 사람이 그 작업을 할 때 드는 비용이다.목표는 다음과 같다.한 사람은 하나의 작업만 맡고 ,하나의 작업도 한 사람에게만 배정하면서 ,전체 비용이 가장 작아지게 만들기욱진 → 작업 B한영 → 작업 A지은 → 작업 C 처럼 배정할 수 있고 이때 전체 비용은욱진 B = 2한영 A = 6지은 C = 1총 비용 = 9 이런 식으로 계산한다.헝가리안 알고리즘이 필요한 이유사람과 작업 수가 적으면 모든 경우의 수를 직접 비교할 수 있다.3..

다익스트라 ( Dijkstra )가중치가 있는 길 찾기 기본형가중치 ( 거리 , 비용 )가 있는 그래프에서 시작점 → 모든 지점까지의 최단거리를 구하는 알고리즘가장 가까운 길부터 차근차근 확정하는 방식이다. 작동 원리네비게이션이 도로 전체를 훑어서 최단거리 지도를 만드는 과정이라고 보면 된다.출발점에서 가장 가까운 노드부터 확정한다.확정된 노드를 기준으로 주변 노드의 거리를 갱신 ( update ) 한다.다시 "가장 가까운 노드"를 뽑는다.이 과정을 반복하면 결국 모든 지점까지의 최단거리 테이블이 만들어진다.역할 : 하나의 시작점에서 모든 노드까지의 최단 거리를 구하는 알고리즘조건 : 간선 가중치가 음수가 아니어야 한다 ( 0 이상 )탐색 방식 : └ 지금까지 발견한 거리 중에서 제일 짧은 노드..

다익스트라 알고리즘 ( Dijkstra's Algorithm )가중치가 있는 그래프에서 한 정점 ( Vertex ) 에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다."다익스트라는 최단 경로를 찾는 알고리즘이다"에츠허르 다익스트라 ( Edsger W. Dijkstra ) 가 고안한 알고리즘이다.다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다.네비게이션에서 최단 거리 길 찾기게임에서 AI 가 "가장 짧은 길"로 이동네트워크 라우팅 경로 계산 핵심 아이디어가장 가까운 노드부터 차근차근 확정해 나아가는 방식 ( Greedy 방식 )시작점의 거리를 0 으로 설정아직 방문하지 않은 노드 중 현재까지 거리값이 가장 작은 노드를 선택이 노드를 통해 갈 수 있는 주변 노드들의 거리값을 갱신 ( Rel..

A-Star 알고리즘 ( A* )A-Star 알고리즘은 게임 개발이나 인공지능에서 가장 자주 쓰이는 경로 탐색 알고리즘이다.유니티의 NavMesh 같은 시스템도 기본적으로 A* 의 원리를 기반으로 만들어졌다.이름A-Star ( A* ) 알고리즘목적출발지에서 목적지까지 최단 경로를 찾기특징현재까지의 거리 + 앞으로의 예측 거리를 동시에 고려사용 예시미로 찾기 , 길 찾기 AI , NPC 이동 , RTS 유닛 이동 등자료구조우선순위 큐 ( Priority Queue ) 또는 Open / Closed List 사용 A* 는 각 노드의 점수를 계산하면서 최적의 경로를 탐색한다. 1. 점수 계산식각 노드마다 세 가지 값을 계산한다.f(n) = g(n) + h(n)g(n)시작점에서 현재 노드까지의 실제 비용 ( ..

탐색 알고리즘 ( Search Algorithms )C# 에서 탐색 알고리즘은 데이터 안에서 원하는 값을 찾는 방법이다.탐색은 정렬 여부 / 탐색 범위 / 구조 형태 ( 리스트 , 트리 , 그래프 등 ) 에 따라 여러 가지로 나뉜다. 1. 기본 탐색 알고리즘 ( 배열 , 리스트 )데이터가 정렬되어 있는지 여부에 따라 달라진다. 1-1. 선형 탐색 ( Linear Search )하나씩 순서대로 비교하는 가장 단순한 방법정렬되어 있지 않아도 사용 가능BigO : O(n)int LinearSearch(int[] arr, int target){ for (int i = 0; i 1-2. 이진 탐색 ( Binary Search )정렬된 배열에서 중간값을 기준으로 탐색중간값보다 작으면 왼쪽 , 크면 오른쪽..

Inside-Out Fisher–YatesInside-Out Fisher–Yates 은 일반적인 피셔 예이츠 ( Fisher Yates ) 셔플의 변형 버전이다.핵심 아이디어는 새로운 배열을 만들면서 동시에 섞인 상태를 채워 넣는 것이다. 동작 과정 길이가 같은 새 배열을 준비한다.i = 0 부터 n-1 까지 순회하면서랜덤 인덱스 j 를 0 ~ i 범위에서 뽑는다.새 배열의 i 에 원본 배열의 i 를 넣는다.만약 j != i 라면, 새 배열의 i 대신에 j 위치의 원소와 교체한다.이렇게 하면 새 배열이 완전히 무작위로 섞인다. 의사코드 ( PseudoCode ) 표현for i = 0 → (배열의 마지막 인덱스)까지 반복한다 0부터 i까지 범위에서 무작위 인덱스 j를 선택한다 만약 j ≠..

퀵 정렬 ( Quick Sort )퀵 정렬은 분할 정복 ( Divide and Conquer ) 방법을 사용하는 정렬 알고리즘이다.배열에서 피벗 ( Pivot )을 선택하고 , 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한다.이 과정을 재귀적으로 반복하여 정렬한다.배열에서 기준값 피벗 ( pivot )을 하나 정한다피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 보낸다이렇게 나뉜 두 구간을 다시 퀵 정렬로 정렬한다더 이상 나눌 수 없을 때까지 재귀적으로 반복한다 동작 과정1. 배열에서 하나의 원소를 피벗 ( pivot )으로 선택한다.2. 피벗보다 작은 원소들은 왼쪽 , 큰 원소들은 오른쪽에 배치한다.3. 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 재귀적으로 정렬한다.4. 더 ..

피셔 예이츠 셔플 ( Fisher Yates Shuffle )피셔 예이츠 셔플은 배열이나 리스트의 원소들을 무작위 ( Random )로 섞는 알고리즘이다.모든 가능한 순열이 동일한 확률로 발생하도록 보장한다는 특징이 있다.피셔 예이츠 셔플은 처음 기술한 로널드 피셔와 Frank Yates 의 이름을 따서 명명되었다.도널드 커누스의 이름을 따서 커누스 셔플이라고 부르기도 한다.배열의 끝에서부터 앞으로 이동하면서,현재 위치 i 와 0 ~ i 사이 임의의 위치 j 를 뽑는다.arr[ i ] 와 arr [ j ] 를 교환한다.배열의 처음까지 진행하면, 전체 배열이 무작위로 섞인다. 동작 과정1. 배열의 끝에서 시작한다. ( i = n - 1 )2. 현재 인덱스 i 와 0 ~ i 사이의 무작위 인덱스 j 를 선..

삽입 정렬 ( Insertion Sort )삽입 정렬은 배열을 앞에서부터 차례대로 보면서, 현재 원소를 알맞은 위치에 삽입하는 방식의 정렬 알고리즘이다.이미 정렬된 부분 배열을 유지하면서, 새로운 원소를 하나씩 삽입하는 방식이라 삽입 정렬이라 부른다.배열의 두 번째 요소부터 시작해앞쪽 정렬된 부분과 비교하며 자신보다 큰 값을 밀어낸 뒤,빈 자리에 현재 값을 삽입한다. 동작 과정예를 들어 [ 5 , 3 , 8 , 4 , 2 ] 를 오름차순 정렬한다고 가정1. 초기 상태- 첫 번째 원소 ( 5 ) 는 이미 정렬된 상태로 간주 2. [ 3 ] 삽입- 5 > 3 → [ 5 ] 에서 [ 3 ] 의 위치를 찾음 → [ 5 ] 앞에 삽입- [ 3 , 5 , 8 , 4 , 2 ] 3. [ 8 ] 삽입- [ 3 , 5..