알고리즘

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

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) : 자원에 대한 허가가 떨어지면 프로세스..

백준 골5 달성

흠 지금부터 난이도 급상승

시간 복잡도 (Time Complexity)와 공간 복잡도 (Space Complexity)

알고리즘 성능 평가 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다. 그중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 한다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 1. 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스다. 빅-오 표기법 예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷..

[실1] 11403 - 경로 찾기

플로이드 와샬 #include #define INF 100000 #define NODE 1000 using namespace std; int graph[NODE][NODE]{ 0 }; void Floyd_washall() { int n; cin >> n; for (int i = 0; i > graph[i][j]; } for (int k = 0; k < n; k++) // 거쳐가는 노드 { for (int i = 0; i < n; i++) // 출발지 노드 { for (int j = 0; j < n; j++) // 도착지 노드 { if (graph[i][k] && graph[k][j]) graph[i][j]= 1; } } } ..

C++ STL 설명과 for-range 기반 loop

STL(Standard Template Library)은 C++ 내 템플릿 클래스들의 집합이며, 개발자에게 도움줄 수많은 자료구조와 함수들이 구현 되어있다. 기본 4가지로 구성 되어있다. 알고리즘 헤더 파일 내 (정렬, 탐색 컨테이너 (선형,비선형 자료구조) 예) , 함수 이터레이터 (반복자) 모든 컨테이너들은 이를 지원하지 않음. STL은 기본적으로 범위 기반 for문을 돌려 원소에 접근할 수가 있다. 핵심은 4번에 있다, 이를 실행할 수 있는 조건이 바로 .begin() 함수다 즉 첫 원소의 주소를 이터레이터 형태로 반환하는 함수다. 예) for(auto item : 컨테이너 이름) 여기서 한 가지 의문점이 들 수도 있는데 const auto : const auto& : auto : auto& : 위..

BOIDS (군중 알고리즘) RTS AI

스타크래프트의 하이브리드 최적 경로 마이크로 관리는 RTS 게임의 가장 중요한 기능이다. 싱글 유닛 또는 한 그룹의 유닛을 드래그해서 선택을 하여 적을 공격하게끔 하는 것이며 이러한 AI 기능은 구현하고자 할 때 큰 골치거리다. 두 가지의 구현 방법이 있다. 퍼텐셜 필드 알고리즘 : 목표점으로 이끄는(attractive) 인공적인 포텐셜 필드와 장애물로부터 멀어지게 내보내는(repulsive) 인공적인 포텐셜 필드를 형상공간에 구축하는 알고리즘. 군중 이동 알고리즘 : 군중 이동(새 떼라던지 물고기들의 움직임 등 여러 집단이 함께 움직이는)에 대한 알고리즘. 게임 유닛들의 내비게이션은 주로 A*와 같은 최단 경로 알고리즘을 사용한다. 하지만, RTS와 같이 월드가 수시로 변화하는 게임에는 적합하지가 않다..

깊이 우선 탐색 BFS / 너비 우선 탐색 BFS 개념

깊이 우선 탐색 (DFS; Depth First Search) 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘을 의미한다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행한다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 하는 것이다. 빠르게 모든 경우의 수를 탐색하고자 할 때 사용한다. 스택 이나 재귀함수 로 구현한다. 너비 우선 탐색 (BFS; Breadth First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색 하는 알고리즘이다. 즉, 깊게 (deep) 탐색하기 전에 넓게 (wide) 탐색 하는 것이다. 두 ..

해시 테이블

해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다. 해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다. 해시 함수(Hash Function)을 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Function) 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)으로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에 사용되는 대표적인 해시 알고리즘에는 ..