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

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

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

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

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

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

1. 무한 배낭 문제 0/1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 무한 배낭 문제는 각 물건이 무한히 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다. 무한 배낭 문제는 0/1 배낭 문제와 유사한데 현재 물건을 담을지 말지 판단할 때 현재 물건을 이미 담았던 배낭을 통해 탐색하는 과정만 다...

1. 다중 배낭 문제 0/1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 다중 배낭 문제는 각 물건이 1개 이상 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다. 이때 각 물건이 무한히 있지는 않다. 다중 배낭 문제는 이를 0/1 배낭 문제로 변형하여 해결할 수 있다. 2. 단순 변형 ...

1. 0/1 배낭 문제 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제로 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 중 0/1 배낭 문제는 짐을 쪼갤 수 ...