CodeAngie

배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘이다.배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다.미리 구해둔 누적합을 통해 배열 중 특정 구간의 부분합을 쉽게 구할 수 있다.값을 미리 저장해 두는 점이 DP와 유사하다.배열의 값들이 변하지 않음1. 1차원 누적합 알고리즘1.1. 1차원 누적합그림과 같이 앞에서부터 차례대로 누적된 합계를 prefixSum 배열에 저장한다.첫 번째(0) 값은 arr 값과 prefixSum 값이 동일하다.현재 위치(i)의 arr 값에 prefixSum 배열에 저장된 직전 위치(i-1)까지의 합을 더하여 현재 위치의 누적합을 구하여 prefixSum에 입력한다.점화식은 다음과 같다.prefixSum[i] = prefixSum[i-1] ..

인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..

동적프로그래밍동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 방법이다.분할 정복과는 다르게 작은 문제를 푸는데서 답이 같은 문제가 중복적으로 일어날 경우 사용한다.보통 점화식을 만들 수 있다.1. 동적프로그래밍의 조건큰 문제는 작은 문제로 나눌 수 있고 작은 문제가 반복해서 나타난다.같은 문제라면 계산할 때마다 같은 답이 도출된다.2. 메모이제이션 (Memoization)메모이제이션은 한번 풀었던 작은 문제를 다시 반복해서 풀지 않기 위해 메모해두고 필요할 때 답만 꺼내 보는 것이다.담아 놓는 것이기 때문에 캐싱 (caching) 이라고도 불린다.메모이제이션을 통해 먼저 구한 결과를 담아 두면, 아래 피보나치 예시에서 점선으로 표시된 노드는 먼저 먼저 계산된 값을 사용하면 되기 때문에 반복해서 계산..

이분 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 1. 이분 탐색의 조건 반드시 오름차순으로 정렬된 상태에서 시작해야 한다. 2. 이분 탐색 알고리즘 시간복잡도: O(logN) 반복문과 재귀 두 가지 방법을 사용할 수 있다. 자료를 오름차순으로 정렬한다. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다. ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색) ⓑ target이 mid 값 보다 크면 start를 mi..

가장 긴 증가하는 부분 수열 알고리즘 이란, 왼쪽에서 오른쪽 방향으로 탐색할 때 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 부분 수열을 찾는 알고리즘이다. 0 1 2 3 4 5 6 10 40 20 50 30 40 60 위의 리스트에서 증가하는 부분 수열은 {10,40,50,60}, {10,20,50,60}, {10,20,30,40,60}, {40, 50, 60} 이 있다. 여기서 가장 긴 증가하는 부분 수열은 {10,20,30,40,60}이며, 부분 수열의 길이는 5가 된다. LIS 알고리즘은 두 가지 방법으로 구성될 수 있다. DP 활용 방법 이분탐색 활용 방법 1. LIS 알고리즘 (DP 활용) 시간복잡도: O(N**2) 1.1. DP 초기화 DP에는 부분 수열의 길이가 담기기 때문에 DP는..