문제 링크 1. 문제 풀이 두 정수 $A$, $B$ 의 차를 산술 연산자를 활용하여 구하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws I...

문제 링크 1. 문제 풀이 두 정수 $A$, $B$ 의 합을 산술 연산자를 활용하여 구하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws I...

1. LIS 기존 2중 반복문을 활용한 LIS 는 간단하게 구현할 수 있다는 장점이 있지만 $O(N^2)$ 의 시간복잡도라는 성능의 아쉬움이 있었다. LIS를 구하는 과정에서 이분 탐색을 활용하면 시간복잡도를 $O(N\log{N})$ 까지 개선할 수 있다. 2. 이분 탐색을 활용한 LIS 주어진 수열이 \(\{10, 45, 30, 35...

1. LIS LIS는 Longest Increasing Subsequence의 약자로 최장 증가 부분 수열을 의미한다. 컴퓨터 공학에서 LIS 문제는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제로 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. LIS는 DP 문제로 전체 수열의 LIS를 더 작은 부분 수열의 LIS를...

1. 퀵 정렬 퀵 정렬(Quick Sort)은 정렬 알고리즘 중 하나로 분할 정복을 통해 정렬하는 알고리즘이다. 이름 그대로 빠른 정렬이 특징인 정렬 알고리즘이다. 2. 퀵 정렬 성능 평균 시간복잡도 $O(N\log{N})$ 최선 시간복잡도 $O(N...

1. 병합 정렬 병합 정렬(Merge Sort)은 정렬 알고리즘 중 하나로 분할 정복을 통해 정렬하는 알고리즘이다. 병합 정렬 또는 합병 정렬이라고 불린다. 2. 병합 정렬 성능 평균 시간복잡도 $O(N\log{N})$ 최선 시간복잡도 $O(N\lo...

1. 선택 정렬 선택 정렬(Selection Sort)은 정렬 알고리즘 중 하나로 정렬되지 않은 부분에서 최솟값이나 최댓값을 찾아서 정렬되지 않은 첫 원소와 자리를 교환하는 방식으로 정렬하는 알고리즘이다. 원리가 간단하기 때문에 한 번쯤 배워볼 만하다. 2. 선택 정렬 성능 평균 시간복잡도 $O(N...

1. 삽입 정렬 삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로 정렬되지 않은 각 원소를 정렬된 부분의 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘이다. 원리가 간단하기 때문에 한 번쯤 배워볼 만하다. 2. 삽입 정렬 성능 평균 시간복잡도 $O(N^2)$ ...

1. 버블 정렬 버블 정렬(Bubble Sort)은 정렬 알고리즘 중 하나로 원소의 이동이 거품이 수면으로 올라오는 듯한 모습으로 보이기 때문에 지어진 이름이다. 코드가 단순하기 때문에 간단한 정렬 알고리즘으로 한 번쯤 배워볼 만하다. 2. 버블 정렬 성능 평균 시간복잡도 $O(N^2)$ ...

1. 무한 배낭 문제 0/1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 무한 배낭 문제(Unbounded Knapsack Problem)는 각 물건이 무한히 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다. 무한 배낭 문제는 0/1 배낭 문제와 유사한데 현재 물건을 담을지 말지 판단할 때 현재 ...