본문 바로가기

알고리즘을 위한 간략 정리

 (30)
[C++] 유니온 파인드(Union-Find) 핵심 요약 유니온 파인드는 그래프 탐색으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다. 트리 구조로 이루어진 자료구조 중 한가지로 생각되기도 한다. 연산 Find - 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union - 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 예제 코드 #include using namespace std; int parent[9]; //배열에 해당하는 것 int find (int x){ if (parent[x]== x) return x; //배열 인덱스와 값이 같다면 해당 값 리턴 retu..
[C++] BFS(Breadth-First Search) 핵심 요약 너비 우선 탐색 시작 노드에 인접한 노드들부터 차근차근 탐색하는 알고리즘 간선의 비용이 동일한 최단거리 문제에서 활용된다. 구현 방식 1. 큐를 사용한다 큐에 노드를 push하고, 방문 처리한다. 노드를 큐에서 pop하고, 인접 노드를 모두 push한 뒤 방문 처리한다. 2. while문의 조건을 통해 모든 노드를 탐색할 때까지 돌린다. 3. while문 안에 for문을 넣어 인접 노드를 탐색한다. 1. 입력이 배열로 주어질 때 배열에 입력값들을 넣은 뒤, 이동해야 하는 방향(주로 상하좌우)을 탐색한다. 이때, 이동 방향은 dx[4] = {-1, 1, 0, 0} 과 dy[4] = {0, 0, 1, -1}을 이용하여 처리하는 편이다. 이 경우 방문 정보는 bool 형의 2차원 배열로 처리한다. ..
[C++] DFS(Depth-First Search) 핵심 요약 깊이 우선 탐색 루트 노드에서 시작하여 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 기법 특징 주로 재귀로 구현된다. 트리 순회의 경우 모두 DFS이다. 방문 여부(visited) 체크나 깊이 지정을 해야 무한 루프에 빠지지 않는다. 구현 방법 스택 재귀
백트래킹(Back-Tracking) 핵심 요약 해를 찾는 도중 해가 아니어서 막힐경우, 되돌아가서 다시 해를 찾아가는 기법 시간 복잡도를 감소시킬 수 있는 기법 최적화 문제, 결정 문제 등을 풀 때 활용한다. 유망성 판단(promising)이 중요하다! 사용처 DFS 등 대표 문제 백준 9663, N-Queen 문제. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net
분할 정복(Divide & Conquer) 핵심 요약 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 -> 분할 각 문제에 대한 답을 계산 -> 정복 이를 병합해 문제를 해결하는 알고리즘 -> 조합 즉, 알고리즘을 각개 격파한다고 볼 수 있다! 구현 방법 보통 재귀로 많이 구현된다.
비트마스킹(Bitmasking) 비트마스킹 데이터 타입마다 각 메모리 사용 크기가 있다. 만약 int 라고 하면 4byte 즉, 32 bit의 크기를 가진다. 표현하면 0000 0000 0000 0000 0000 0000 0000 0000이 될 것이다. (0과 1을 씀) 만약 아이템이 있고 없고를 구현해야할 때 bool 변수 32개를 쓰는 대신에 하나의 비트를 다룰 수 있을경우, 우리는 int 자료형 하나로 32개의 아이템이 있고 없고를 표현할 수 있다. 또한 비트 연산은 연산 속도가 빠르다는 장점을 가지고 있다. 만약 2번째 아이템이 있다면 0100 이런식으로 0을 1로 바꾸어 표현하는 것이다. &, |, ~, ^, >>, n - shift 연산자 오른쪽 혹은 왼쪽으로 n비트 만큼 이동 후 뒤에는 0으로 채움 공집합 만들기 int s..
DP(Dynamic Programming) 핵심요약 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 간단한 구현, 복잡한 점화식 최적의 원리가 성립해야함. 최적의 원리 "어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.” 문제 풀이 순서 문제 탐색 DP 배열에 어떤 값을 저장할 것이고, 인덱스는 어떤 것을 의미할지 정의를 한다. dp 벡터를 선언할 때 최소값을 찾을경우 MAX로, 최대값을 찾을경우 MIN으로 선언한다. DP식(점화식) 세우기 메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 어떻게 구할지를 고민한다. 검증 및 구현(시간 복잡도) 문제 유형 결과값들 더하기. 결과값들 중 최대, 최소 구하기. 배낭 채우기(..
투 포인터(TWO-POINTER) 핵심 요약 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해서 값을 얻는 형태 주로 while문으로 구성 문제 유형 연속된 수들의 합 부분 배열의 합 풀이 방법 포인터 2개가 같은 방향 포인터 2개가 양 끝에서 반대로 진행(이분 탐색과 유사)

티스토리툴바