철학과 학생의 개발자 도전기

1. 개요 정의: 비트마스크는 정수의 이진수 표현을 사용하여, 각 비트가 특정 상태나 조건을 나타내도록 하는 기법이다. 활용 예: 설정 옵션, 접근 권한, 기능 플래그 등 다양한 상태를 효율적으로 저장하고 관리한다. 2. 특징 비트마스크로 집합을 표현하는 방식은 다음과 같다 k번째 원소 포함여부: A & (1

1. 개요 다익스트라 알고리즘은 가중치가 있는 그래프에서 두 노드 간의 최단 경로를 찾기 위한 알고리즘이다. 주로 네트워크 라우팅 프로토콜이나 GPS 장치에서 경로를 계획하는 데 사용됩니다. 이 알고리즘은 그래프의 한 정점에서 다른 모든 정점까지의 최단 거리를 계산한다. 2. 특징 가중치 포함: 모든 간선은 양의 가중치를 가진다. 음수 가중치가 있는 경우, 알고리즘이 올바르게 작동하지 않는다. 그리디 알고리즘: 다익스트라 알고리즘은 현재 상태에서 최적의 해를 선택하는 그리디(Greedy) 방법론을 사용한다. 시간 복잡도: 우선순위 큐(Priority Queue)를 사용할 경우 O((V+E)logV)이다. (V는 정점의 수, E는 간선의 수) 3. 코드 import java.util.Arrays; impo..

1. 개요 LCA 알고리즘은 주어진 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘이다. 비순환 그래프에서 두 노드를 연결하는 경로에 공통으로 존재하는 조상 노드 중 가장 가까운 조상을 찾는다. 이 알고리즘은 트리 구조에서 데이터의 계층적 관계를 분석할 때 유용하게 사용된다. 2. 특징 시간 복잡도: O(depth)이며 최악의 경우 O(N)이다. N은 원소 개수 두 노드의 depth를 맞춘 후, 하나씩 거슬러 올라가며 공통 조상을 찾는다. 3. 코드 public class LCATest { public static void main(String[] args) { // 예제 트리 구성 // 부모 인덱스 배열 (0번 인덱스는 사용하지 않음) int[] parentList = {0, 0, 1, 1, 2, 2..

1. 개요 최장 증가 부분 수열(LIS)은 주어진 수열 내에서 순서를 유지하면서 선택할 수 있는 가장 긴 증가하는 부분 수열을 찾는 문제다. 가장 긴 증가하는 부분 수열의 길이를 찾는 것이 목적이며, 해당 수열 자체를 구하는 것이 목표일 수도 있다. 2. 특징 다이나믹 프로그래밍 활용: LIS는 다이나믹 프로그래밍을 사용하여 해결할 수 있는 대표적인 예제 중 하나이다. 이 방식은 문제를 재귀적으로 분할하고, 중복 계산을 피하기 위해 이전에 계산된 결과를 저장한다. 이진 탐색 활용: 이진 탐색을 통해 LIS의 길이를 더 효율적으로 구할 수 있다. 이 방법은 수열의 각 요소를 순차적으로 검토하면서, 현재까지의 LIS를 유지하는 데 필요한 위치를 빠르게 찾아 업데이트한다. 시간 복잡도: 다이나믹 프로그래밍 방..

1. DFS 그래프의 깊은 부분을 우선적으로 탐색하는 방법 탐색을 시작한 정점에서 출발하여, 한 방향으로 갈 수 있는 경로가 끝날 때 까지 깊게 탐색하고, 더 이상 탐색할 곳이 없으면 마지막에 통과한 정점으로 되돌아가 다른 방향의 정점을 탐색 이 과정을 모든 정점을 방문할 때까지 반복 2. BFS 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문하는 방법 시작 정점으로부터 각 정점까지의 최단 경로를 찾는 데 사용됨 큐(Queue)를 사용하여 구현 3. 코드 import java.util.*; public class GraphTest { static List graph[]; static boolean visited[]; public static void main(String ..

1. 개요 정렬된 배열에서 특정 요소의 위치를 찾기 위한 알고리즘이다. 탐색 범위를 반으로 줄여가며 원하는 값을 찾는다. 배열이 정렬되어 있을 때만 사용할 수 있으며, 매우 빠른 탐색 속도를 가진다. 2. 특징 시간 복잡도: O(log n) n은 배열의 크기 탐색 범위를 매 단계마다 반으로 줄임으로써, 대규모 데이터셋에서도 빠른 탐색을 가능하게 한다. 3. 코드 public class BinarySearchTest { public static void main(String[] args) { int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 }; int target = 10; int resultIndex = binarySearch(arr, target); if (resultIndex..

1. 개요 계수 정렬은 비교를 사용하지 않는 정렬 알고리즘이다. 정렬해야 할 요소들의 값 범위가 제한적일 때 효과적이다. 정렬하려는 입력 배열에서 각 요소의 발생 횟수를 세고, 이 정보를 바탕으로 각 요소가 정렬된 배열에서 어디에 위치해야 하는지를 결정한다. 작은 정수를 정렬할 때 높은 성능을 보이며, 복잡한 비교 연산 없이 빠르게 정렬을 수행할 수 있다. 2. 특징 시간복잡도: O(n+k) n은 배열의 크기, k는 입력 데이터의 최대값 공간 복잡도: O(k) 각 입력 데이터의 발생 횟수를 저장하기 위한 배열 필요 3. 코드 import java.util.Arrays; public class CountingSortTest { public static void main(String[] args) { int..

1. 개요 숫자의 각 자릿수를 기준으로 정렬하는 비교 기반 정렬 알고리즘이 아닌, 분배식 정렬 방법이다. 데이터의 자릿수를 기준으로 순차적으로 정렬을 진행하며, 가장 낮은 자릿수(1의 자리)부터 시작하여 가장 높은 자릿수까지 차례대로 정렬하는 과정을 거친다. 데이터의 크기에 비해 상대적으로 자릿수가 작을 때 좋은 성능을 보인다. 2. 특징 시간복잡도: O(d(n+k)) n은 정렬할 요소의 개수, d는 자릿수의 개수, k는 기수(10진수인 경우 10) 공간 복잡도: O(n + k) 기수 정렬은 정렬을 위한 임시 배열 공간을 필요로 한다. 자릿수가 클수록 메모리 사용량이 많아진다. 3. 코드 import java.util.Arrays; public class RadixSortTest { public stat..