트라이(Trie) 여러 문자열을 효율적으로 저장하고 탐색하기 위한 트리 형태의 자료구조로 시간 복잡도는 O(n)이다. 기본 원리  struct Trie{ Trie* next[26]; bool finish; Trie() :finish(false) { for (int i = 0; i insert(key + 1); } bool find(const char* key) { if (*key == 0) return finish; int curr = *key - 'a'; if (next[curr] != NULL) return next[curr]->find(key + 1); return false; }}; 문제 https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판휴대..

유니온 파인드(Union-Find) 서로소인 집합들을 분할하여 저장한 집합 Union(): 두 집합의 루트 부모를 합침 Find(): 자신의 루트 부모를 찾아 계속해서 거슬러 올라가는 과정 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어..

투 포인터(Two Pointer) 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작하여 원하는 값을 얻는 알고리즘이다. 문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net #include using namespace std; int arr[10000]; int main() { int N, M; cin >> N >> M; for (int i = 0; i > arr[i]; ..

next_permutation, prev_permutation 함수에 벡터의 iterator나 배열의 주소를 넣으면 다음 순열(next_permutation) 또는 이전 순열(prev_permutation)의 결과가 벡터나 배열에 적용된다. 만약 다음 또는 이전 순열이 없다면 False를 return 한다. 문제 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net #include #include using namespace std; int num[10000]; int main() { int n; cin >>..

비트 연산자정수 타입의 피연산자에만 적용될 수 있다. 기본 원리A^B는 값이 같으면 0 다르면 1을 반환한다.~A는 -A-1과 같다.시프트 연산자에서 빈 비트엔 모두 0이 채워지지만 >> 연산자에서 A가 음수인 경우엔 1이 채워진다. 문제https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 카카오 신입 공채 1차 코딩 테스트 문제 해설‘블라인드’ 전형으로 실시되어 시작부터 엄청난 화제를 몰고 온 카카오 개발 신입 공채. 그 첫 번째 관문인 1차 코딩 테스트가 지난 9월 16일(토) 오후 2시부터 7시까지 장장 5시간 동안 온라인��tech.kakao.com#include using namespace std;int main(){ int n ..

최단 경로 두 정점 사이의 경로 중 간선의 가중치 합이 최소인 경로를 찾는 알고리즘이다. 1. 다익스트라 알고리즘 가중치가 적은 순서대로 그 정점에 연결된 정점을 방문하면서 값을 갱신하는 알고리즘이다. 음의 가중치를 가진 경로는 구할 수 없다. 가중치 합의 최댓값은 가중치 최댓값 * (정점 개수 - 1) 이다. 1) 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, ..