코린이의 소소한 공부노트

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

1. Problem - 크루스칼 알고리즘을 사용하여 모든 노드를 연결하는 최소 비용을 구해보자. - 최소 비용 신장 트리(minimum cost spanning tree)를 만드는 대표적인 알고리즘이다. - 각 노드를 연결하는 간선의 정보(연결된 노드, 비용)를 이용해 간선을 정렬한 후 사이클을 만들지 않게 적은 비용의 간선부터 차례대로 선택해 나간다. - 최소한의 비용으로 모든 노드를 이어야 하기 때문에, 사이클을 만드는 것은 비용 낭비가 된다. - 간선을 선택하기 전에 사이클 테이블을 확인해야 하는데, 이는 이미 연결된 노드인지 알아보기 위함이다. 사이클 테이블은 union-find(합집합 찾기) 알고리즘을 이용한다. 2. Input 1) int[][] graph - 연결된 노드를 표현 2) int[..

1. Problem - 여러 개의 노드 중 2개를 선택했을 때, 두 노드가 같은 그래프에 있는지 알아보자. - 합집합 찾기(union find) 알고리즘은 i번 노드에 대한 부모 노드의 값을 arr[i]에 저장해서 m번 노드와 n번 노드의 부모가 같다면 같은 그래프에 있다고 판단하는 알고리즘이다. - 한 그래프의 노드들을 연결할 때 부모 노드가 여러개가 생긴다면 더 작은 값으로 저장한다. 이 과정을 합침(union) 과정이라 한다. - 합침 과정에서 최종 부모를 찾기 위해 재귀적으로 메서드를 호출하게 된다. - 찾기(find) 과정에서는 두 노드의 부모를 찾아 같은지 확인한다. 2. Input 1) int[][] graph - 연결된 노드를 표현 2) int a, b 3. Output 1) a, b가 같..