📝 Computer Science

[C++] 투 포인터(Two Pointer)

투 포인터(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]; ..

[C++] next_permutation, prev_permutation

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 >>..

[C++] 비트 연산자

비트 연산자 정수 타입의 피연산자에만 적용될 수 있다. 기본 원리 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(..

동기와 비동기 & Blocking과 Non-Blocking

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

[C++] 최단 경로(다익스트라, 플로이드 와샬, 벨만 포드)

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

[C++] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 깊이 우선 탐색은 한 방향으로 계속 가다가 더 이상 갈 수 없으면 부모 노드로 돌아와 다른 방향으로 탐색한다. 주로 Stack이나 재귀 함수를 이용해 구현한다. 모든 노드를 방문하거나 가중치, 이동 과정에 제약이 있을 경우에 사용하면 좋다. 자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있다. BFS보다 좀 더 간단하나 단순 검색 속도 자체는 BFS보다 느리다. 너비 우선 탐색은 현재 노드에서 가장 가까운 노드를 먼저 방문해 탐색한다. 주로 Queue를 이용해 구현한다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾는 경우에 사용하면 좋다. 기본 원리 https://www.acmicpc.n..