알고리즘

C++ 프림(Prim) 알고리즘으로 MST 찾기

1. 프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘이다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것이다. 하늘색으로 표시한 경로가 최소신장트리이다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적이다. 2. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요하다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 한다. (보통 Min Heap을 이용해서 구현한다.) 가장 먼저, 그래프에서 아무 노드나 선택하므로 가장 번호가 ..

CPU 스케줄링(Scheduling) 알고리즘 정리 및 요약 | FCFS, SJF, Round Robin

CPU 스케줄링이란 CPU 이용률을 극대화하기 위해서는 멀티프로그래밍(multiprogramming)이 필요하다. 하지만 만약 CPU core가 하나라면 한 번에 하나의 프로세스만 실행 가능할 것이다. 이때 필요한 것이 CPU 스케줄링이다. 즉, CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이라고 할 수 있다. CPU 스케줄러(CPU Scheduler)와 선점형(Preemptive), 비선점형(non-preemptive) 스케줄링 CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 한다. CPU 스케줄러는 프로세스들이 다음과 같은 상황에 있을 때 스케줄링을 결정한다. 실행(running) 상태에서 대기(waiting) 상태로..

라빈-카프 알고리즘 (Rabin-Karp) 해시값을 통한 문자열 비교

정의 / 시간 복잡도 O(n) 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다. 간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 된다. 이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 된다. 예를 들어 ABCD와 ABED라는 문자열이 있을 때 ABCD의 해시 값은 65 * 3^3 + 66 * 3^2 + 67 * 3^1 + 68 * 3^0 = 2618 ABED의 해시 값은 65 * 3^3 + 66 * 3^2 + 69 * 3^1 + 68 * 3^0 = 2624 이므로 ABCD와 ABED 두 문자열은 서로 일치하지 않는다는 결과가 된다. 간혹 해시 값이 서로 충돌하는 해시 충돌 ..

보드 게임 관련 AI 알고리즘 [구현 예정]

테트리스 - 유전 알고리즘 (Gnome Algorithm) 오목 - 최소극대화 알고리즘 (Min Max Algorithm) 체스 - 최소 극대화, 알파-베타 가지치기 (Alpha–beta pruning) , Move Ordering, 전치 테이블 (Transposition table), Quiescence search 미로 찾기 - 다익스트라 > A* > JPS 각 알고리즘 별로 퍼포먼스 차이 결과 도출할 예정 지뢰 찾기 - Straightforward Algorithm, The Tank Solver Algorithm, Two Endgame Tactics 오델로 - 최소 극대화, 휴리스틱

스위핑 알고리즘 (Sweeping algorithm)

스위핑 알고리즘(sweeping algorithm)은 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태다. 추천 문제 2170 선 긋기 2836 수상 택시 10000 원 영역 5419 북서풍 3392 화성 지도 10534 City Park

LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

Longest Common Subsequence? Substring? LCS는 주로 최장 공통 부분수열(Longest Common Subsequence) 또는, 최장 공통 문자열(Longest Common Substring)을 뜻한다. 해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다. 최장 공통 문자열(Longest Common Substring) 최장 공통 부분수열(Longest Common Subse..

BSP(Binary Space Partitioning)알고리즘을 응용해 로그라이크류 게임 방만들기

이진 공간 분할법(Binary Space Partitioning, BSP) 은 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다. doom은 3차원처럼 보이지만 실제로는 2차원이고 그 2차원을 나타내기 위해 사용됐다. BSP알고리즘을 통한 로그라이크류 방만들기 0: 빈 공간 1 : 방, 3: 가로분할 길, 4: 세로분할 길 로그라이크 게임을 하다보면 일정한 맵을 돌려쓰는 게임도 있긴하지만 매번 새로운 맵을 생성하는 게임들이 존재한다. 매번 새로 맵을 생성할때 BSP알고리즘을 응용하여 새로 맵을 만들수 있다. 위에서 설명한 BSP알고리즘에서 둔각을 찾아 반복하여 나누는 방법이 아니라 2차원상에서 직사각형 모양으로만 방을 나눠..

시간 복잡도에 따른 알고리즘 목록

O(1) 배열 인덱스 접근 (예, arr[5];) 배열에 저장되있는 트리의 부모 또는 왼/오른쪽 자식 노드 검색 단일 연결 리스트에 노드를 삽입 이중 연결 리스트의 다음 또는 이전 요소에 접근 스택 푸시 팝 큐 삽입 삭제 해싱 (Hash Table) O(log n) 이중 탐색 이진 트리에서 최소 또는 최대값 검색 분할 정복 알고리즘 중 일차적인것들만 피보나치 수열 계산 O(n) 배열 순회 연결 리스트 순회 이진 검색 정렬이 되어있지 않은 연결 리스트 요소 제거 두 문자열간 비교 회문인지 검사 계수/버킷 정렬 O(n log n) 병합 정렬 힙 정렬 퀵 정렬 분할 정복 알고리즘 중 O(n^2)로 구현되있는것들 O(n^2) 버블 정렬 삽입 정렬 선택 정렬 단순한 2차원 배열 순회 O(n!) 브루트포스 탐색 방..

최소 스패닝 트리 (MST) / 크루스칼 알고리즘 (Kruskal Algorithm)

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 크루스..

데드락 (Deadlock) 의미 & 조건

데드락(Deadlock)이란? 멀티 프로그래밍 또는 멀티 스레드 환경에서는 여러 프로세스 또는 스레드가 한정된 자원을 동시에 사용하기 위해 항상 경쟁 상태에 놓여 있고 프로세스가 필요한 자원을 획득하지 못하고 영원히 자원을 기다리는 상태이다. 시스템 모델 설명 자원이란 CPU, 파일, 메모리, 락객체(세마포어나 뮤텍스 같은 Synchronize Object) 등등 컴퓨터 시스템에서 여러분이 사용할 수 있는 모든 것들을 총칭하는 추상적인 용어다. 요청(Request) : 프로세스가 특정 자원을 시스템에게 요청하면 시스템은 현재 이 자원이 사용 가능하다면 프로세스에게 할당 한다. 불가능하다면 자원이 사용 가능해 질 때까지 기다린다(Wait state). 사용(Use) : 자원에 대한 허가가 떨어지면 프로세스..