Swimmer

Sliding Window Sliding Window란, 배열의 첫번째 인덱스부터 차례대로 접근하되, 해당 인덱스에서 다시 일정 범위 내 원소들에 접근하는 방법이다. 원소의 개수가 N개, Window 크기가 K 개라면, 총 N x K 번의 인덱스 접근이 발생한다. K가 매우 클 때 이러한 방법은 Brute Force와 같아지고 Time Complexity : O(n^2)이 된다. 코딩 문제에서 Window 크기 K가 고정되어 있다면 난이도가 낮은 문제로 Sliding Window 개념만 구현해주면 된다. 만약, Window 크기도 변수로 설정된 문제라면 난이도가 중간인 문제이고, 이때는 Time Complexity가 O(n^2)이 아닌 O(n)으로 문제를 풀 수 있는 알고리즘을 생각해야 한다. Time ..

코딩 문제 int 배열이 주어졌을 때, 합이 최대가 되는 2가지 Element를 찾아라. (합 연산이 곱셈, 뺄셈 등의 연산으로 바뀔수도 있고, 각 연산 외에 또다른 연산 방법을 적용한 것일 수도 있다. 연산의 종류와 관계 없이 배열에서 특정 연산의 최댓값 or 최솟값을 찾는 2가지 Element를 찾아야 하는 문제로 추상화 가능하다.) 이번 글을 정리하게 된 이유는 아래 문제 때문이다. (LeetCode 11. Container With Most Water) https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75 Container With Most Water - L..

Container에서 최댓값 (혹은 최솟값)을 찾거나 N번째의 해당 값을 찾는 문제를 푸는 방법 1. Container를 정렬한 후 N번째 혹은 최대(최솟값)을 찾는다. 2. Heap 자료구조를 사용하여 Heap 속성을 유지하는 이진 트리를 만든 후, Root 노드에 접근하여 최댓값 (혹은 최솟값)을 찾거나 N번 Pop을 실행해 원소를 찾는다. 2번의 경우 Container를 정렬하지 않고 시간 복잡도 O(log n)으로 문제를 풀 수 있다. 코딩 문제로도 내기 좋은 문제인듯? 정렬을 쓰지 않아야 하는 조건이 있고, 시간 복잡도도 물어볼 수 있겠다. 2번을 사용하기 위해서는 Heap 자료구조에 대한 이해가 필요하다. 이는 아래 포스팅을 참고하자. [자료구조] 힙(Heap), 우선 순위 큐 Heap, 힙 ..

Heap, 힙 힙(heap)은 힙 속성을 만족하는 tree를 기반으로하는 자료구조 이다. 힙 속성은 다음과 같다. A가 B의 부모 노드라면, A 노드의 값은 B 노드의 값과 대소 관계가 성립한다. 이때, 부모 노드가 자식 노드보다 값이 크다면 '최대 힙', 반대라면 '최수 힙'이라고 지칭한다. 각 노드 간의 대소 관계는 오직 부모 노드와 자식 노드 간에만 성립되고, 형제 노드 사이에는 대소 관계가 정해지지 않는다. 힙은 자식 노드의 최대 개수에 따라 종류가 나니ㅜ는데, 보통은 자식 노드가 2개인 이진 힙 (Binary tree)에 사용한다. 힙을 사용하는 이유는 배열에서 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위함이다. 힙은 가장 큰 값 (혹은 가장 작은 값)이 Root 노드에 오는 특징이 있고..