📕Programming/📝Algorithm

정렬 알고리즘 수행 애니메이션기본 정렬 3종류버블 정렬 (Bubble Sort)버블 정렬은 가장 간단한 정렬 알고리즘 중 하나이다.이 알고리즘은 인접한 두 원소를 비교하여 필요에 따라 서로 위치를 교환하는 방식으로 동작한다.가장 큰(또는 가장 작은) 원소가 배열의 가장 마지막으로 이동하면서 끝에서부터 정렬이 완료된다. 버블 정렬의 시간 복잡도는 O(n^2)이다. 동작 방식배열의 첫 번째 원소부터 마지막 원소까지 순회한다.현재 원소와 다음 원소를 비교하여 크기가 더 작은(또는 더 큰) 원소가 앞에 오도록 위치를 교환한다.배열의 마지막 위치까지 도달할 때까지 위의 과정을 반복한다.한 번의 순회를 마치면 가장 큰(또는 가장 작은) 원소가 배열의 마지막으로 이동하게 되므로, 다음 순회에서는 마지막 원소를 제외한..

도입완전 탐색 알고리즘은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 문제을 해결하는 방법이다.다른 말로, '무식하게 푼다(brute-force)'라고도 한다. 예를 들어, 두 점 사이의 최단 경로를 찾는 문제라면, 두 점 사이의 경로를 하나하나 전부 만들어서 그중 가장 짧은 것을 찾는다. 재귀 호출과 완전 탐색코드를 짜다 보면, 각 코드들의 형태가 유사해지는 작업들을 볼 수 있다.완전히 같은 코드를 반복해 실행하는 for문 같은 반복문이 그 예이다.이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(Recursive Function), 혹은 재귀 호출(Recursion)이다. 예로, 1부터 n까지의 합을 계산하는 함수를 만들어 보자.// 1부터 n까지의 합을..

도입부분 합이란 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열이다. 예를 들어 보자.N명의 시험 성적을 내림차순으로 정렬해 둔 배열 Socres[]가 있다고 하자.우리는 a등에서 b등까지의 평균 점수를 계산하는 함수 Average(a, b)를 만들고 싶다.이것을 계산하는 일반적인 방법은 Scores[a]부터 Scores[b]까지를 순회하며 각 수를 더하고 이것을 b-a+1로 나누는 것이다.이렇게 하면 반복문의 수행 횟수는 최대 O(N)이 된다.평균 점수를 한 번 계산할 거라면 이 방법으로 해도 충분하지만, Average()를 굉장히 여러 번 호출하게 될 거라면 이것을 좀 더 최적화할 수 없나 하는 생각이 든다.이럴 때 유용하게 사용되는 것이 부분 합(Partial su..

들어가며그래프는 정점(Vertex)과 간선(Edge)으로 이루어져 있다. 보통 정점과 간선이 모두 이어진 상태로 DFS건 BFS건 다양한 방법으로 탐색했다면,스패닝 트리는 정점과 간선을 연결하는 것부터 시작한다. 스패닝 트리는 간선의 수를 최소화해서 모든 정점을 연결하는 방식을 말한다.간선의 수의 최소화라는 의미는 3개 이상의 정점끼리 사이클이 생기면 안 된다는 의미이다.(ex. 1 3 2 1) 정리하면, N개의 정점을 N-1개의 간선으로 연결하되, 사이클을 포함하면 안 된다. 어떤 가중치 그래프에 대한 여러 개의 스패닝 트리 최소 스패닝 트리최소 스패닝 트리는 스패닝 트리 중에서 가중치의 합이 가장 최소인 스패닝 트리를 구하는 방식이다.비유하자면, 다익스트라 알고리즘 같은 방식이다. 위의 가중치..

분리 집합 (Disjoint Set)다익스트라-우선순위 큐 처럼 Disjoint Set은 최소 스패닝 트리를 구현할 때 아주 좋은 알고리즘이다.분리 집합 (Disjoint Set)을 다른 이름으로, 유니온-파인드 (Union-Find)라고도 한다. 분리 집합 (Disjoint Set)은 서로 공통원소가 없는 집합을 의미한다.예를 들어, 1인으로 된 100개의 팀이 서로 싸우는 게임이 있다고 하자.여기서, 팀끼리 서로 동맹을 맺으면 두 팀 중 한 팀이 다른 팀의 휘하로 들어가게 되고, 한 팀을 구성하게 된다.이를 전체 집합으로 놓고 보면, 이 집합을 여러 개의 부분집합으로 쪼갠 것이다.각 팀은 팀마다 번호가 있기 때문에, 두 개 이상의 팀에 속한 사람은 없다.이렇게 공통 원소가 없는, 부분 집합으로 나뉜 ..

동적 계획법(DP)DP는 하나의 큰 문제를 여러 개의 작은 문제로 나누어 계산하며, 그 결과를 저장하여 그 결과를 이용하여다시 큰 문제를 해결할 때 사용하는 방식이다. 분할 정복 알고리즘과 비슷하게 보이지만, 작은 문제에서 계산한 결과를 저장하여 나중에 다시 계산하지 않도록 하는 것이 DP의 핵심이자 시간 복잡도적인 측면에서 큰 이점을 보는 방식이다. 복권 1등 당첨 확률을 계산하는 알고리즘을 짜보자.int combination(int n, int r){ // 예외 사항 if (r == 0 || n == r) return 1; return combination(n - 1, r - 1) + combination(n - 1, r);}int main(){ __int64 start = GetTickCount64..

C 스타일의 난수 생성하기srand 함수를 사용하여 랜덤 시드를 구하고, 그 시드 값을 time 함수를 사용하여 현재 시간을 기준으로 하여고정된 값이 아닌, 계속 변화하는 값을 넣어 난수를 생성한다. 단점은 시드값이 너무 천천히 변한다는 점과, 랜덤값을 균등하게 생성하지 않는다는 점이다.그리고, 결론적으로 rand() 함수 자체도 그다지 뛰어나지 않은 함수라 웬만하면 C++을 사용하자. 생성될 난수에 최대 범위로 나눈 값을 +1 해주면 1~범위 까지의 값을 추출해 낼 수 있다.#include #include using namespace std;int main() { // 시간을 기준으로 시드값 설정 srand(static_cast(time(nullptr))); // rand() 함수로 나온 ..

들어가며레드-블랙 트리는 각각의 노드가 레드나 블랙인 색상 속성을 가지고 있는 자가 균형 이진 탐색 트리이다. 이게 무슨 소리냐? 이진 탐색 트리의 단점은 트리가 한 방향으로 쭉 뻗어나갈 수 있다는 단점이 존재한다.이런 단점을 보완한 것이 자가 균형 이진 탐색 트리인데, 조건이 맞지 않으면 트리가 재구성되어서 균형을 유지한다. 레드-블랙 트리의 조건1. 노드는 레드 혹은 블랙 중의 하나이다.2. 루트 노드는 블랙이다.3. 모든 리프 노드들(NIL)은 블랙이다.4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다.(즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는리프 노드를 ..