헝가리안 알고리즘 ( 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..

너비 우선 탐색 ( BFS , Breadth - First Search )자료구조 내에서 찾고자 하는 데이터를 찾는 방식은 여러 알고리즘과 기법이 존재한다.너비 우선 탐색은 그래프 탐색 알고리즘 중 하나이다. 가까운 정점부터 탐색을 진행하는 방식이다.시작 정점으로부터 거리가 가까운 정점들을 먼저 방문하고 그 다음 거리에 있는 정점들을 방문하는 방식으로 탐색이 진행된다. 이런 방식은 경로의 길이를 기준으로 탐색하는 문제, 최단 경로를 찾는 문제에서 특히 효과적이다. 시작 정점에서 출발해 연결된 정점들을 순서대로 Queue에 넣고큐에서 꺼낸 정점을 기준으로 다시 그 정점에 연결된 이웃들을 큐에 넣으며 탐색을 확장한다.깊이 우선 탐색이 한 경로를 깊에 따라가는 방식이라면,너비 우선 탐색은 한 계층씩 넓게 탐색..

깊이 우선 탐색 ( DFS , Depth - First Search )자료구조 내에서 찾고자 하는 데이터를 찾는 방식은 여러 알고리즘과 기법이 존재한다.깊이 우선 탐색은 그래프 탐색 알고리즘 중 하나이다.한 방향으로 갈 수 있는 곳까지 계속 탐색한 다음 , 막히면 다시 이전 분기점으로 돌아와 다른 경로를 탐색한다.이런 방식은 트리 구조 탐색 뿐만 아니라 , 미로 찾기 , 경로 탐색 , 사이클 검사 등 다양한 문제에 사용된다. 현재 정점에서 탐색을 시작해서 갈 수 있는 곳까지 계속 내려가며 탐색한다.더 이상 갈 곳이 없으면 되돌아가 다른 경로로 탐색을 이어나간다.한 경로를 끝까지 파고들어가기 때문에 "깊이 우선" 이라는 이름이 붙었다.탐색의 흐름은 재귀함수 호출 또는 스택 자료구조를 이용해 구현할 수 있다..

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 )정렬된 배열에서 중간값을 기준으로 탐색중간값보다 작으면 왼쪽 , 크면 오른쪽..

Big-O 표기법 속도 순 정리표Big-O 표기법을 빠른 순서 ( 성능이 좋은 순서 )로 정리한 표이다.시간 복잡도 기준으로 정렬되어 있다. 순위복잡도이름 / 성장 형태예시 알고리즘설명1O(1)상수 시간 ( Constant )배열 인덱스 접근 , 스택 Push / Pop입력 크기와 상관없이 한 번만 연산2O(log n)로그 시간 ( Logarithmic )이분 탐색 ( Binary Search ) , 균형 BST 탐색입력이 커져도 단계마다 절반으로 줄어든다3O(n)선형 시간 ( Linear )단순 순회 ( Loop ) , 선형 탐색입력 n 개를 한 번씩 처리4O(n log n)준선형 시간 ( Quasi - Linear )퀵정렬 , 병합정렬 , 힙정렬n 개 항목 x log n 단계 처리5O(n²)이차 시..

Big-O 표기법 ( 점근 표기법 )일반적으로 알고리즘의 시간복잡도를 나타내는데 사용한다. Big-O 표기법 , Big-Omega 표기법 , Big-Theta 표기법 등이 있다.보통 성능이 얼마나 나쁜지가 중요하므로 Big-O 표기법이 제일 많이 쓰인다.Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간 복잡도를 가질 때 사용한다.즉, Big-O 표기법은 입력 크기 n 이 커질 때 알고리즘의 실행 시간 ( 또는 메모리 사용량 ) 의 상한이 어떻게 증가하는지를 나타내는 점근적 ( Asymptotic ) 척도이다. 상수 시간 , 상수 배수 같은 세부 구현 차이는 무시하고 성장률만 본다는게 핵심이다. 핵심 규칙 ( 작동 원리 + 개념 요약 )입력 크기 n 을 먼저 정한다 ( 예시 : 배열..