순열 순열(permutation)은 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산을 뜻한다. 가령 {1,2,3}이라는 집합에서 순서를 고려하여 3가지 숫자를 뽑는경우는 {1,2,3], {1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1} 6가지 경우의 수가 나오게되고 이처럼 특정 집합의 요소들을 순서를 고려하여 뽑는 경우를 순열이라고 한다. n개의 집합에서 r개의 요소를 뽑는 경우를 nPr이라고 하고 공식은 위와 같다. 구현 1. 내장 함수 기반 구현 c++은 내부적으로 순열을 구현해주는 next_permutation()함수를 가지고 있다. (algorithm 헤더안에 포함) 인자값으로 범위를 넣어주면 되는데 [fisrt, last) 범위로 값을 넣어주면된다. 따라서 (1,2,3)..
정의 유클리드 호제법(유클리드 알고리즘)은 최대공약수 (GCD : Greatest Common Divisor)를 구하는 알고리즘이다. 다른 두 수를 각각 A, B (단 A > B), A를 B로 나눈 나머지를 r 이라고 가정할때 A와 B의 최대공약수는 B와 r의 최대 공약수와 같다. 즉 GCD(A,B) = GCD(B,r) = GCD(A, A%B) 코드 반복문 구현 int gcd(int a, int b) { int tmp; while (b > 0) { tmp = a % b; a = b; b = tmp; } return tmp; } 재귀 구현 int gcd(long long int a, long long int b) { if (b == 0) return a; else return gcd(b, a % b); }..
1. 해시맵이란? 인덱스 대신에 Key값을 통해서 배열에 접근 할 수 있게 해주는 자료구조이다. Key - Value 쌍으로 구성되어있으며 Key를 Hash Function을 통해서 인덱스화하고 이를 기반으로 값을 저장해준다. 만약 우리가 100만명의 유저의 전화번호 데이터를 가지는 테이블이 있다고 가정해보자. 이 100만명의 사람들중 특정 유저의전화번호 정보를 수정해야 하는 일이 발생한다면 이사람의 정보를 수정하기 위해서는 먼저 100만개의 테이블에서 내가 수정하고자 하는 유저의 정보가 테이블의 몇번째 인덱스에 있는지 부터 찾아야 할것이다. 그러면 처음부터 끝까지 내가 원하는 유저를 찾을떄까지 탐색을 진행해야하고, 최악의 경우 100만번의 연산이 필요하게된다. 이는 굉장히 비효율적이고 오랜 시간이 걸리..
1. 이진탐색이란? 이진탐색(Binary Search)은 처음부터 끝까지 모든 케이스를 탐색하는 일반적인 선형탐색(Linear Search)와 달리 데이터의 배열의 중간값을 확인해보고 해당값보다 크거나 작은 경우를 체크해가며 탐색해야하는 데이터를 반씩 줄여나가는 탐색방법이다. 만약 n개의 데이터가 들어있는 배열 arr[n] 이 있다고 가정하면, 일반적인 선형탐색의 경우 처음부터 모든 데이터를 확인해봐야하기 떄문에 데이터를 탐색하는데 O(n)이 걸리게된다. 만약 탐색해야하는 데이터가 n개이고 찾아야 하는 데이터 또한 n개라고 가정해보면 O(n) 탐색을 총 n번 해야하므로 O(n^2)의 시간이 걸리게된다. 2. 설명 데이터를 탐색해야하는 다음과 같은 배열이 있다고 가정하자. arr = [1, 2, 3, 4,..
개요 Floyd Warshall 알고리즘은 Dijkstra 알고리즘과 마찬가지로 그래프에서 정점간의 최단경로를 찾기 위한 대표적인 최단경로 알고리즘중 하나이다. 비슷한 알고리즘이지만 Dijkstra는 한 특정 지점에서 다른 모든 지점까지의 최단경로를 구하는 Single-source shortest path algorithm이고, Floyd Warshall의 경우 모든 지점에 대해 그 점을 제외한 다른 지점들 까지의 모든 최단경로를 구하는 All-pairs shortest path algorithm이라는 차이점이 있다. 이번 글에서는 모든 쌍에 대해 최단 경로를 구하는 Floyd Warshall알고리즘에 대해 알아보고자 한다. 아이디어 위 사진처럼 i, j, 1 이라는 3개의 노드가 연결된 그래프가 있다고..
