유니온 파인드(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 ..

동기와 비동기 & Blocking과 Non-Blocking 1. 동기(Synchronous)와 비동기(Asynchronous) 함수를 실행시킴과 동시에 반환 값이 기대되는 경우는 동기라 표현하고 그렇지 않은 경우는 비동기라고 표현한다. 동기: 실행되었을 때 값이 반환되기 전까지는 Blocking 상태이다. 비동기: Blocking 되지 않고 이벤트 큐에 넣거나 백그라운드 스레드에게 해당 task를 위임하고 다음 코드를 실행하므로 기대되는 값이 바로 반환되지 않는다. 2. Blocking과 Non-Blocking 간단히 말해서 호출된 함수가 호출한 함수에게 제어권을 건네주는 유무의 차이라고 볼 수 있다. 1) Blocking I/O 프로세스(스레드)가 커널에게 입출력 작업을 요청하는 recvfrom() 함..

최단 경로 두 정점 사이의 경로 중 간선의 가중치 합이 최소인 경로를 찾는 알고리즘이다. 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, ..