코린이의 소소한 공부노트

1. Problem - 비트 마스크 기법을 이용해 여러 연산을 수행해보자. 1) 비트 마스크 기법은 비트 연산자(&, | 등)를 활용해서 정수(int)의 이진 비트를 처리해 메모리를 적게 사용하면서 프로그램의 속도를 높이는 기법이다. 2) 모든 문제에 사용할 수 있는 것은 아니지만, 사용할 수 있다면 소스코드가 직관적으로 바뀌게 된다. - 예를 들어, 출석을 1, 결석을 0으로 표시한다고 했을 때 한 반에 32명인데 3번과 6번이 출석이라면 00000000 00000000 00000000 00100100 (2) = 36으로 표현할 수 있다. 3) 정수를 2진 비트로 표현할 때 음수를 표현하는 것은 2의 보수를 이용한다. // 8비트로 예를 들자면 30 = 0001 1110 -30 -> 1110 0001 ..

1. 개념 정리 1) 이진 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 2) 펜윅 트리(Fenwick Tree)라고도 불린다. 3) 세그먼트 트리보다 구현하기 편하고 속도가 빠르다. - 세그먼트 트리는 필요한 리프 노드만 채우기 때문에 불완전 트리지만, 인덱스 트리는 리프 노드를 모두 채워서 만들기 때문에 인덱스를 활용할 수 있다. - 데이터의 개수가 N개일 때, 세그먼트 트리를 만들기 위해 필요한 공간을 통상 4*N만큼 준비했었다면 인덱스 트리를 만들 때는 N만큼만 준비하면 된다. 4) 인덱스는 1부터 사용하고, 인덱스를 활용하면 해당 인덱스의 값이 몇 개의 데이터의 합인지 알 수 있다. - 8비트로만 간단히 예시를 들어보면, 3과 -3을 비트 and 연산을 해보면 다..

1. Problem - 주어진 트리에서 두 노드 node1, node2의 최소 공통 조상을 찾아보자. - 최소 공통 조상(Lowest Common Ancestor, LCA)는 특정한 두 노드의 공통된 조상 중 가장 가까운 조상을 말한다. - 이진 트리가 아니어도 적용되는 알고리즘이다. - 다이나믹 프로그래밍을 이용하는 알고리즘이다. 2. Input 1) int[][] graph - graph[i][j]: i는 j의 부모 노드 2) int n - 노드의 개수 3) int node1 4) int node2 3. Output 1) node1과 node2의 최소 공통 조상 4. Explanation 1) 트리에 있는 모든 노드에 대해서 각 노드의 깊이(depth)를 구한다. 2) 모든 노드에 대해서 각 노드의 ..

1. 개념 정리 1) 여러 개의 데이터가 연속적으로 존재할 때 특정 구간의 데이터의 합을 담은 이진 트리 2) 실제 구현은 트리가 아닌 배열로 하게 된다. - 배열은 인덱스가 있어 접근성이 좋기 때문이다. 3) 세그먼트 트리를 이용한 구간 합 처리의 시간 복잡도는 O(lgn)이다. 2. 예시 1) 구간 합의 데이터가 될 배열을 준비한다. int[] arr = {1,2,3,4,5,6,7,8}; 2) 구간 합 트리가 될 배열도 준비한다. int[] tree = new int[32]; // arr.length * 4 // 데이터의 개수가 N개일 때 필요한 부분 합 트리의 공간은 // N 이상의 2의 거듭제곱수 중 가장 작은 것 * 2이다. // 여기서 N=8이므로 8 이상의 2의 거듭제곱수 중 가장 작은 것은..

1. Problem - 그리디 알고리즘을 이용하여 거스름돈으로 지급할 동전의 최소한의 개수를 구해보자. - 그리디 알고리즘은 가장 큰 것부터 또는 가장 작은 것부터 선택하며 최적의 답을 찾아가는 알고리즘으로, 탐욕법이라고도 불린다. - 그리디 알고리즘은 정렬, 다이나믹 프로그래밍과 함께 사용되는 경우가 대다수이다. - 그리디 알고리즘이 항상 최적의 답을 도출하지는 않는다. 2. Input 1) 거스름돈 액수 3. Output 1) 거스름돈을 500원, 100원, 50원, 10원짜리 동전을 이용해서 지급할 때 필요한 동전의 최소 개수 4. Example 거스름돈으로 지급해야 하는 금액: 947원 // 500 < 947 < 1000 500원: 1 // 남은 금액: 447원 // 400 < 447 < 500 ..

1. Problem - 한 문자열(A)에 다른 문자열(B)이 포함되어 있는지 단순 비교, KMP, 라빈-카프 알고리즘 3가지를 이용해 확인해 보자.. 1) 단순 비교: A의 맨 앞에서부터 B가 있는지 확인한다. 2) KMP(Knuth-Morris-Pratt): 접두사(prefix)와 접미사(suffix), pi[]를 이용해 비교 연산량을 줄인 알고리즘 - pi[i]에는 B의 부분 문자열 B[0]~B[i]에서 길이가 부분 문자열보다 짧은 것 중 접두사와 접미사가 같은 것을 찾은 후 가장 긴 값을 저장한다. - pi[3]==1이라면, B[0]~B[3]에서 접두사와 접미사의 공통부분의 길이가 1이라는 것이다. 3) 라빈-카프(Rabin-Karp): 문자열을 해시(hash) 기법을 이용해 데이터를 단순하게 바꿔..

1. Problem - 이분 매칭 알고리즘을 이용하여 X 집단이 Y 집단을 선택하는 방법을 찾아보자. - X 집단에 속하는 원소들이 Y 집단을 선택하는 조건이 주어질 때, 모든 조건을 만족하면서 X 집단의 모든 원소가 Y 집단의 원소를 선택하게 만든다. - 이때 X 집단에 속하는 원소 a, b에 대해 a!=b라면 Y(a)!=Y(b)가 성립해야 한다. 2. Input 1) List wishlist - wishlist[i] = X 집단의 원소 i가 선택하고자 하는 문자가 담긴 list 3. Output 1) X 집단의 원소 x와 x가 선택한 Y 집단의 원소 y를 차례대로 출력 4. Example // X = {1,2,3}, Y={A,B,C} // 1번의 조건: A, B, C // 2번의 조건: A // 3번..

1. Problem - 방향 그래프(directed graph)에서 SCC를 찾아보자. - 강한 요소 결합(Strongly Connected Component, SCC)이란 그래프에 있는 노드 중에서 서로 도달이 가능한 노드들의 집합을 말한다. - 쉽게 말하면, 그래프 안에서 사이클을 이루는 노드의 집합이다. - 타잔 알고리즘은 정점에 대해 DFS(깊이 우선 탐색)을 실행하며 SCC를 찾는다. 2. Input 1) int[][] graph - graph[i][j]는 i번 노드에서 j번 노드로 향하는 간선을 뜻한다. 2) static int vertex - 그래프 내에 존재하는 노드의 수를 의미한다. 3. Output 1) SCC의 개수 2) 각 SCC에 속하는 노드의 번호를 출력 4. Example //..

1. Problem - 제시된 그래프를 보고 노드의 순서를 정해보자. - 위상 정렬은 순서가 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘이다. - 위상 정렬에 이용되는 그래프는 싸이클이 없는 방향 있는 그래프(Directed Acyclic Graph, DAG)이다. 2. Input 1) int[][] graph - 그래프의 간선을 표시한 2차원 배열 - graph[i][j]: i번에서 j번으로 연결되어있다는 뜻이다. 3. Output 1) 그래프의 노드들이 위상 정렬된 결과를 출력 4. Example // 각 노드들의 연결을 확인한 후, 노드별로 진입차수를 계산한다. // 진입차수란 노드로 들어오는 간선의 개수를 말한다. indegree=[0, 1, 1, 1, 1, 2..

1. Problem - 1부터 n까지의 수 중 소수를 찾아보자. 2. Input 1) int n 3. Output 1) [1, n]의 자연수 중 소수를 찾아 출력 4. Explanation 1) 기본 알고리즘 - x는 1부터 n까지의 수 중 하나이다. - 2부터 x-1까지 1씩 증가시켜 가며 x를 나눠본다. 1개라도 x를 나누어 떨어지게 한다면 x는 소수가 아니다. 2) n의 제곱근까지만 찾아보는 알고리즘 - x는 1부터 n까지의 수 중 하나이다. - a*a = x가 되는 a를 구한다. 이때 a가 자연수가 아니라면 소수점 이하를 버린다. - 2부터 a까지 1씩 증가시켜 가며 x를 나눠본다. 1개라도 x를 나누어 떨어지게 한다면 x는 소수가 아니다. 3) 에라토스테네스의 체를 이용한 알고리즘 - 1부터 n..