백트래킹 문제를 풀다가 중복제거, 오름차순 정렬 등을 좀 더 간단하게 하고 싶어서 정리한 내용입니다. 기존에 정리한 글https://gbleem.tistory.com/124 백트래킹1. 백트래킹쉽게 말해서 가능한 모든 경우의 수를 다 해보는 알고리즘이다.재귀 함수를 사용하여, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘! 문제를 보고, 주어진gbleem.tistory.com 1. 순열 구하기기본 형식의 백트래킹 코드를 돌리면 순열을 구할 수 있다. 1 ~ n까지의 숫자 중에서 m개를 뽑는 경우중복은 제거void Choose(int cur){ if (cur == m) { for (const int& a : ans) { cout  4 2를 input으로 넣었을 때 아래와 같은 ..

1. 다익스트라 알고리즘가중치가 있는 그래프의 최단경로를 구할 때 사용하는 알고리즘 다익스트라 알고리즘의 동작 방식은모든 노드의 최소 비용을 INF로 초기화한다.시작한 노드의 최소비용은 0, 직전 노드는 자기 자신으로 두고 시작이후 최소 비용이 가장 낮으면서 방문하지 않은 노드를 선택하여 최소 비용을 업데이트 한다.아래의 그림을 통해 어떤 방식으로 동작하는지 알 수 있다.최소 비용이 가장 낮은 A로 시작하여 모든 연결된 노드의 최소비용을 갱신 (A 방문)이후 최소비용이 가장 낮은 E노드를 시작으로 더 작은 최소비용이 되는 경로가 있다면 갱신 A->E->C가 기존의 A->C 보다 최소비용이 작으므로 갱신! (E 방문)이 방식을 모든 노드 방문할 때 까지 반복하기결과우리가 C까지의 경로를 알고 싶다면, C의..

1. 정렬 알고리즘1 - 1. 버블정렬배열에서 두개의 원소 선택하고 비교 후, 왼쪽 원소가 오른쪽 원소보다 큰 경우 swap 한다.시간 복잡도는 O(N^2), 공간 복잡도는 O(1)만약 아래 코드에서 swap이 발생하지 않는 경우 break하는 코드를 넣으면, 정렬된 경우 시간 복잡도를 O(N)으로 줄일 수 있다.더보기#include #include using namespace std;int main(){ vector vec = { 4,6,2,9,1 }; for (int i = 0; i vec[j + 1]) swap(vec[j], vec[j + 1]); } } for (const auto v : vec) cout  1 - 2. 선택 정렬배열의 한가지 값을 선택하고, 자신을 제외한 나머지 값들과..

1. 백트래킹쉽게 말해서 가능한 모든 경우의 수를 다 해보는 알고리즘이다.재귀 함수를 사용하여, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘! 문제를 보고, 주어진 전체 배열의 크기가 크지 않을 때 사용해 볼 법한 알고리즘이다.(너무 큰 경우 시간 초과가 날 것이다) 가장 기본적인 형태로, N개 중 M개를 뽑는 문제가 존재한다.https://www.acmicpc.net/problem/15649 코드 설명기본적으로 아래와 같은 형태로 재귀함수를 구성하게 된다.isused 라는 이미 사용한 것인지를 체크하는 배열을 통해 중복을 제거하게 된다.Choose라는 함수 안에서 경우의 수를 뽑는 과정이 이루어진다.cur은 현재 뽑은 갯수가 되고, cur이 m이 되는 순간 특정 처리를 해주면 된..

비트 마스킹이란 0과 1을 이용해서 연산하는 방식을 말한다.이 방식을 통해서 효율적인 연산이 가능할 때가 있다. 많이 안 써본 방식이기 때문에 관련 수업을 들은 후 내용을 정리하게 되었다.추가적으로 아래 글을 참고해서 정리해 보았다.https://blog.encrypted.gg/1093 [실전 알고리즘] 부록 C - 비트마스킹네 반갑습니다. 이번 부록 C에서는 비트마스킹을 다뤄보겠습니다.  이번 강의에서는 간단하게 비트 연산자들을 살펴보고 비트마스킹을 익힌 후에 문제를 같이 풀어볼 예정입니다. 이것도 다른blog.encrypted.gg  1. 비트 연산자0은 false 1은 true를 뜻한다.AND (둘다 참인 경우 참)0 & 0 = 00 & 1 = 01 & 1 = 1OR (둘중 하나만 참이어도 참)0 ..

1. 그래프의 특징과 종류방향이 있는 그래프 가중치가 있는 그래프 순환이 있는 그래프  2. 그래프 구현2 - 1. 인접 행렬을 이용한 그래프배열의 인덱스는 노드세로 방향 출발 노드가로 방향 도착 노드배열의 값은 노드의 가중치 2 - 2. 인접 리스트를 이용한 그래프  결론인접 행렬크기가 고정되어 있기 때문에 노드가 많고 연결이 적은 그래프에서 낭비가 심한 단점이 있다.간선의 정보를 O(1)에 얻을 수 있는 장점이 존재인접 리스트대부분의 경우 인접 행렬에 비해 메모리를 절약할 수 있다.평균적으로 간선의 정보를 얻는데 시간이 좀 더 걸림  3. 그래프 탐색3 - 1. BFS최단 경로를 보장하는 탐색 방식queue를 사용한다.방문 처리를 queue에 push할때 진행한다.#include #include #i..

1. 집합집합은 코딩테스트나 알고리즘에서 순서와 중복이 없는 원소들을 가지는 자료구조를 뜻한다.예를 들어, A = {1 ,6, 6, 6, 4, 3} 일때 A를 집합으로 생각하면 {6,3,4,1} 이런 식으로 정리 될 것이다.코딩테스트에서는 주로 상호 배타적 집합에 집중하게 된다.상호 배타적 집합이란 A와 B라는 집합이 있을 때서로간의 교집합이 없는 집합을 뜻한다.그 이유는, 그래프 문제에 사이클을 확인하는 경우가 많은데 이때 상호 배타적 집합 개념을 활용해서 문제를 풀기 때문이다.  2. 집합의 연산주로 집합은 트리로 표현하게 된다. 또한 상호 배타적 집합을 나타내기 때문에 배열을 사용해서 구현한다.이때 각 집합은 대표 원소가 있어야 한다.대표 원소는 집합을 트리로 나타낼 때 루트가 되는 노드가 대표 원..

업데이트) 병합 정렬과 이분탐색 알고리즘 추가자세한 예시는 해당 글에 있고, 전반적인 정리는 아래 링크의 글을 참고하면 된다.https://gbleem.tistory.com/128 정렬 및 탐색 알고리즘 정리1. 정렬 알고리즘1 - 1. 버블정렬배열에서 두개의 원소 선택하고 비교 후, 왼쪽 원소가 오른쪽 원소보다 큰 경우 swap 한다.시간 복잡도는 O(N^2), 공간 복잡도는 O(1)만약 아래 코드에서 swap이 발생하gbleem.tistory.com 1. 버블 정렬개념앞에서부터 시작해서 자기 자신과 하나 뒤에 값을 비교하는데, 자신보다 작은 값이 나온 순간 swap을 해주는 과정을 통해 정렬한다.한바퀴 순환을 하고나면, 맨 뒤의 값이 가장 큰 값이 된다.N개의 데이터가 있을 때, 이중 for문을 모두..

1. 트리 개념노드, 간선으로 이루어진 구조코딩테스트에서는 이진 트리만 알고 있으면 충분하다.  2. 이진 트리 표현하기2 - 1. 배열로 표현하기루트를 인덱스 1로 시작왼쪽 자식은 부모 노드의 인덱스 x2오른쪽 자식은 부모 노드의 인덱스 x2 + 1이 방식의 단점은 배열의 공간이 조금 낭비된다는 점이다.그러나 매우 간단하기 때문에, 많이 사용하는 방식이다. 2 - 2. 이진 트리 순회하기현재 노드를 부모 노드로 생각했을 때전위 순회 : 부모 -> 왼쪽자식 -> 오른쪽 자식 중위 순회 : 왼쪽 자식 -> 부모 노드 -> 오른쪽 자식후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모 노드위에서 그린 그림을 기반으로 예를 들어보자더이상 갈 곳이 없거나, 우선순위가 자기 노드인 경우 방문하는 식으로 동작한다..

해시 구조는 데이터 값(키)이 들어오면,  "해시 함수"를 통해 변환된 값을 기반으로 버킷에 넣어주는 구조를 가진다.이때, 해시 함수가 변환한 값이 최대한 중복되지 않도록 (해시 충돌이 적게 발생하도록) 하는 것이 중요하다. 1. 해시 함수1 - 1. 나눗셈법 해시 함수공식 : h(x) = x mod k가장 기본적인 해시 함수로 나눗셈법을 이용한 함수가 있다."키"를 소수로 나눈 나머지를 활용하는 방식이다.이때, 소수를 사용하는 이유는 충돌을 줄일 수 있기 때문이다.예시) x = 3, 6, 9, 12, 15, 18, ... (3의 배수)15라는 수로 나눈 경우3 ~ 15 까지의 수는 각각 3, 6, 9, 12, 0 에 해당하는 버킷에 들어가게 된다.그러나, 이후의 값(18 ~)에 있어서 3, 6, 9, ..