알고리즘19 [정렬 알고리즘] 버블, 선택, 삽입 정렬 c++ 구현 단순한 정렬 알고리즘 3가지를 알아보고자 한다. 아래 알고리즘 3개는 정말 단순하기 때문에 금방 이해하고 구현할 수 있다. 버블 정럴 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 시간 복잡도 O(n^2) 코드 구현 #include using namespace std; // 버블 정렬 함수 void bubbleSort(int arr[], int n) { for (int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; .. 2024. 2. 27. [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를 돌리는 것은 비효율적이므로 자기 그룹의 꼭대기에 있는 사람만 비교하는 것이다. 2와 8은 다른 그룹인 것을 알 수 있다. 트리에 값 추가하는 방법 parent[2] = 3; parent[7] = 3; parent[5] = 3; parent[8] = 4; 두 수가 같은 집합인지 알기 위해 필요한 함수 int find_root(int node) { if (parent[node].first == node) return node; //노드의 최적화: 항상 부모를 루트노드로 만듬 return parent[node] = fi.. 2024. 2. 22. [최소 힙] c++ 구현 및 설명 이미지 출처:https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC 힙의 정의 우선 순위 큐를 이해하기 위해서는 힙이라는 것을 알아야 한다. 완전 이진트리의 일종으로 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다. 힙의 특징키 값의 대소관계는 오로지 부모 노드와 자식노드 간에만 성립하여 형제 사이에는 대소 관계가 정해지지 않는다. (예를 들어 9와 14사이에는 우선순위가 있지만 14와 18사이에는 우선순위가 존재하지 않는다.) 힙의 시간 복잡도는 O(logn)이다. 힙의 종류최대 힙(Max Heap): (완전 이진 트리) + (부모 노드 > 자식 노드)최소 힙(Min Heap): (완전 이진 트리) + (부모 노드 < 자식 노드) 이미지 출처:http.. 2024. 2. 14. [DP] 동적 계획법 알고리즘 c++ 설명 목차 DP(다이나믹 프로그래밍) 메모리를 적절히 사용하여 시간 복잡도를 비약적으로 단축시킬 수 있는 방법이다. 일반적으로 하향식 또는 상향식으로 구현된다. 상향식 (타뷸레이션) 하위의 문제를 이용하여 더 큰 문제의 정답을 풀어나가는 방법이다. 결과 저장용 리스트나 사전을 DP 테이블이라고 한다. 보통 for문을 이용한 구현 방식이다. 하향식 (메모이제이션) 큰 문제에서 하위 문제로 접근하여 하위 문제에 대한 정답을 계산 했는지 확인하며 푸는 방식이다. 보통 while문을 이용한 구현 방식이다. 다이나믹 프로그래밍의 조건 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다. 이미지 출처: htt.. 2024. 2. 10. 이전 1 2 3 4 5 다음 728x90
