Little bIT awesome

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

CI (빌드와 테스트 자동화) Continuous Integration 여러 명의 많은 개발자들이 코드 베이스를 계속해서 통합하는 것이다. 여러 개발자들의 코드를 각각 가능한 빠르게 배포하는 것을 의미 → 즉, 코드를 통합한다는 것 개발이 끝난 후 코드 품질을 관리하는 고전적 방식의 단점을 해소하기 위해 나타난 개념 말 그대로 코드 변경 사항이 정기적으로 빌드 및 테스트되어 (가능한 매시간 또는 매일) 공유 리포지토리에 통합되는 과정을 통해 계속 품질을 유지하면서 개발을 진행하는 방법 CD (배포 자동화) Continuous Delivery 내부 사용자(내부 QA, 마케터, 기획자)나 사용자에게 서비스를 지속적으로 배달한다. 즉, 코드 베이스가 항상 배포 가능한 상태를 유지하는 것을 의미 Continuo..

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

큐 (Queue) Queue 라는 단어의 사전적 의미는 '대기줄', '줄을 서서 기다리다' 먼저 줄을 선 사람이 먼저 서비스를 받듯이 Queue도 먼저 들어온 자료가 먼저 빠져 나가는 FIFO(First In First Out) 구조이다. Offer 과 Poll 대신 Enqueue, Dequeue 등으로도 표현된다. Queue의 특징 정해진 한 곳을 통해서 삽입과 삭제가 이루어지는 스택과는 달리 큐의 삽입과 삭제는 양 끝에서 이루어진다. 새로운 원소의 삽입은 항상 큐의 뒤쪽에서, 원소의 삭제는 큐의 앞쪽에서 이루어지며 프론트와 리어라는 용어를 다음과 같이 정의한다. 프론트(front) : 큐의 삭제 연산이 이루어지는 곳 리어(rear) : 큐의 삽입 연산이 이루어지는 곳 큐의 연산자 메서드 설 명 boo..