♣ 누적합누적합은 배열의 일부 구간에 대한 합을 쉽게 구할 수 있는 알고리즘으로, 배열의 값이 변하지 않는다면 누적합 역시 변하지 않는다는 점을 이용한다. 미리 구해둔 누적합을 이용하여 배열 중 특정 구간의 합을 쉽게 구할 수 있다. 미리 구해둔 합을 사용한다는 점에서 DP와 비슷하다.  ♣ 1차원 배열에서의 누적합arr = [1, 2, 3, 4, 5]arr_sum = [1, 3, 6, 10, 15]i항부터 j항까지의 부분배열에 대한 누적합 = s[j-1] - s[i-1]arr_sum 에서 3항부터 5항까지의 부분배열에 대한 누적합 = arr_sum[j-1] - arr_sum[i-1] = arr_sum[4] - arr_sum[2]   ♣ 백준 알고리즘 10986번  위의 문제는 배열이 주어졌을 때, 이 ..

♣ 투 포인터 복습https://jy-deeplearning.tistory.com/132 투 포인터(백준 알고리즘 1644번)♣ 투 포인터 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘. 시작점과 끝점 두 개의 점으로 접근할 데이터의 특정 범위를 표현할 수 있다. *대표적인jy-deeplearning.tistory.com ♠ 백준 알고리즘 2470번  이 문제는 주어진 여러 가지 용액을 두 가지씩 골라 혼합했을 때, 가장 0에 가까운 용액의 특성값을 가지는 조합을 구하는 문제이다. 각 용액의 특성값은 음수와 양수 모두 가능하다.   예제를 보면 다섯 가지 용액의 특성 중 두 개를 뽑아 더했을 때 가장 0에 가까운 조합이 -99, 98 이다.   ♠ 문제 해결 아이디..

♠ 세그먼트 트리세그먼트 트리란? 특정 구간(segment)에 대한 구간 값을 트리에 저장한 자료 구조.  nums = [1, 2, 3, 4, 5] 배열(리스트) 안의 숫자를 모두 더한다고 했을 때, 위의 숫자배열은 짧기 때문에 처음부터 끝까지 요소를 하나씩 가져오면서 더해도 되지만 배열 길이가 길어질수록 시간이 오래 걸리게 된다. 그래서 어느 정도 구간의 합은 미리 구해서 저장하고 필요할 때만 사용하는 방법으로 세그먼트 트리를 사용한다.  세그먼트 트리는 이진트리를 기본으로 한다. 배열의 길이 n이 2의 제곱꼴인 경우, 완전이진트리가 되며 그때 트리의 높이는 logN이다. N이 2의 제곱꼴이 아닌 경우, 높이는 H=[logN]이다. 길이가 10인 배열을 세그먼트 트리로 나타내면 다음과 같다.  그리고 ..

♠ 기본 내용그래프는 정점(노드)와 간선으로 이루어져 있는데 간단한 그래프 형식이라면 노드와 간선의 존재만 고려하면 된다. 하지만 여기에 '가중치'라는 개념이 추가될 때가 있다. a 노드와 b 노드를 이어주는 x라는 간선이 있을 때, 이 간선이 weight라는 가중치를 가질 수 있는 것이다. 이 경우 a -> b로 갈 때 weight 만큼의 비용이 필요하게 된다.  예를 들어 한 도시에서 다른 도시로 가는 최단 거리를 구한다고 해보자. 이때 각 도시는 노드, 각 도시를 잇는 경로는 간선이 된다. 또한 한 도시와 다른 도시를 잇는 경로의 거리는 가중치가 된다. A 도시에서 B 도시로 갈 때, 다양한 경로를 이용하여 이동할 수 있겠지만 그 중에서도 가중치가 가장 작은, 즉 최단 거리를 찾는 문제에서 데이크스..

♠ BFS(Breadth-First-Search) 의 개념 그래프 탐색하나의 정점(노드)로부터 시작하여 차례대로 모든 노드를 한 번씩 방문하는 것. BFS도 그래프 탐색 방법 중 하나이다. BFS는 루트 노드(혹은 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. 따라서 시작 노드로부터 가까운 노드를 먼저 방문하고, 멀리 떨어져있는 노드를 나중에 방문하는 순회 방법이다.  ♠ BFS의 특징- BFS는 시작 노드에서 목표 노드까지의 최단 경로를 구하는 데 유용하다. 시작 노드로부터 가까운 노드부터 탐색하기 때문이다. DFS의 경우, 이와 달리 깊이를 끝까지 탐색한 후 옆으로 이동하기 때문에 최단 경로를 구하기 어렵다. - BFS를 구현할 때는 노드 방문 여부를 검사해야 한다. 방문 여..

♠ 슬라이딩 윈도우   윈도우(특정 범위)가 있을 때 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘. 고정된 범위를 탐색할 때 유용하며 중복으로 연산을 제거하면서 효율을 높일 수 있다. 한 칸씩 이동하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다. 투 포인터와 비슷하지만, 슬라이딩 윈도우는 고정된 범위를 탐색하는 것이기 때문에 두 개의 포인터가 없어도 된다.   위의 배열에서 연속적인 4개 숫자의 합이 최대인 값을 구한다고 가정한다. [1, 3, 2, 6] => 합: 12[3, 2, 6, -1] => 합: 10[2, 6, -1, 4] => 합: 11[6, -1, 4, 1] => 합: 10  이렇게 계산을 하면 중복되는 부분이 생긴다. 중복을 줄이기 위해..