Little bIT awesome

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 예를 들어 { 6, 2, 5, 1, 7, 4, 8, 3 } 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 된다. { 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 이기 때문 일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용하는 것 아래에서 length[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미한다. ..

동적 계획법 (DP: Dynamic Programming) 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘 중복 계산을 줄여서 계산 속도를 높일 수 있으며, 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다. 일반적으로 재귀를 사용해서 구현되며 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피한다. 동적 계획법의 조건 1. 최적 부분 구조 (Optimal Substructure) '큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질 즉, 작은 문제의 최적해를 구한 후 그것을 이용하여 큰 문제의 최적해를 구할 수 있다. 2. 중복 부분 문제(Overlapping Subproblems) '동일한 작은 문제를 반복적으로 해결'해야 하는 성질 즉, ..

그리디 알고리즘 (탐욕법, Greedy Algorithm) 최적의 값을 구해야하는 상황에서 사용되는 근시안적인 방법론 '현재 상황에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 단, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 하고 있음 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 주로 문제를 분할 가능한 문제들로 분할하여 각 문제들에 대한 최적해를 구한 뒤, 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다. [문제] 노드에서 가장 합이 높은 방법을 선택하기 각 상황에서 '최적'이라고 생각하는 방법을 선택 → 가장 높은 수를..

그래프를 구현하여 표현하는 방법에는 여러가지가 있지만 일반적으로 인접행렬과 인접리스트 방식이 있다. 이 두가지 방식은 서로 정반대의 특징을 갖기 때문에 한 방식의 장점이 다른 방식의 단점이 되는 경우가 나타난다. 따라서, 구현하려는 알고리즘, 그래프의 종류에 따라 적절하게 사용하여야 한다. 인접 리스트를 이용한 그래프 구현 package boj.study.week6; import java.util.ArrayList; public class adjacencyList { public static void main(String[] args) { int initSize = 6; ListGraph adjList = new ListGraph(initSize); adjList.put(1, 2); adjList.put..

DFS DFS는 Depth First Search의 약자로 깊이 우선 텀색을 말한다. DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. 위의 그림처럼 0에서 1로, 1에서 3으로 갔을 때 더 이상 갈 곳이 없으면 백트래킹을해서 다시 1로 가게 됨 이후에 방문하지 않은 4를 방문하게 되는 형태 해당 분기에서 갈 수 있을떄까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방식 대게 Stack을 사용하고 모든 노드를 방문하고자 할 때 사용한다. BFS보다 더 간단하게 구현되지만 검색 속도 자체는 BFS에 비해 느리다. BFS BFS는 Breadth First Search의 약자로 너비 우선 탐색을 말한다. BFS는 재귀적으로 동작하..

간혹가다 브루트포스와 백트래킹, 그리고 DFS(깊이우선탐색)를 혼동하는 경우가 있어 이에 대해 정리를 한 번 하고 가는게 좋다. "a + b + c + d = 20을 만족하는 두 수를 모두 찾아내시오 (0

백트래킹 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 판단하고 그러한 경우에 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다. 더 이상 탐색할 필요가 없는 상태(노드)를 제외하는 것을 가지치기(Pruning)라고도 한다. 즉, 이 방법을 통해 우리는 모든 경우의 수를 체크 하지 않고 필요한 것만 체크하여 전체 풀이 시간을 단축할 수 있게 된다! 백트래킹을 사용해 해결할 수 있는 문제는 의사결정, 최적화, 열거하기 등의 경우가 있다. 사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 Exponential(지수, 2n2� 꼴)이며, 대부분 Dynamic Programming, 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다. 하..

분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬이 있으며, 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 분할 정복 설계 1) Divide 원래 문제를 더 작은 하위 문제로 분할하는 과정이다. 이 단계에서 문제를 해결하기 쉬운 형태로 나누어야 한다. 이 과정은 주어진 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 나눌 수 있을 때까지 계속된다. 2) Conquer 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. 3) Combine (= Merge) Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 ..

이분 탐색(Binary Search)이란? '정렬된 배열'에서 '특정 값'을 찾는 알고리즘을 의미 이분 탐색은 탐색 범위를 절반씩 줄여나가기 때문에 선형 탐색에 비해 빠른 속도를 보장한다. 하지만, 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요하다. 이분 탐색 과정 배열의 '중간 값'을 선택하여 찾고자 하는 값과 비교한다. 만약 중간 값이 찾고자 하는 값보다 크면 '배열 왼쪽 부분'에서 탐색을 다시 진행하고, 중간 값이 찾고자 하는 값보다 작으면 '배열 오른쪽 부분'에서 탐색을 다시 진행한다. 중간 값이 찾고자 하는 값과 같으면 탐색을 종료한다. 이분 탐색의 사용처 이진탐색은 데이터가 오름차순으로 정렬되어 있을 때 특정한 값을 찾아야 하는 경우..

TimSort 창안자인 Tim Peters의 이름을 따서 팀 정렬(Tim sort) 알고리즘이라고 부른다. 처음 만들어졌을 때는 Python을 위해 C언어로 구현되었으나 현재 Java, Android, Google Chrome, swift 등에서 표준 정렬 알고리즘으로 채택되었다. 특징 '실제 데이터는 대부분 이미 정렬되어 있을 것이다.'라는 가정에 기반한 정렬 알고리즘 삽입정렬과 병합정렬을 적절히 조합한 알고리즘 현업에서 병합정렬, 퀵정렬보다 널리 쓰이는 정렬 알고리즘 현실세계의 데이터들이 완전 무작위로 배열돼 있기 보단 어느 정도 정렬된 상태로 배열돼 있는 경우가 많다면 정렬을 해야하는 전체 배열을 작은 덩어리들로 잘라 각각의 덩어리를 Insertion Sort로 정렬한 뒤 Merge Sort로 병합..