본문 바로가기

전체 글139

Sliding Window (슬라이딩 윈도우) TC O(N) Technique 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 .. 2023. 8. 1.
배열에서 연산의 최댓값 혹은 최솟값을 가지는 2개의 값 찾기 문제 (Two Pointers) 코딩 문제 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.. 2023. 8. 1.
Container에서 최댓값 (최솟값) 혹은 N번째 최댓값 (최솟값) 찾기 Container에서 최댓값 (혹은 최솟값)을 찾거나 N번째의 해당 값을 찾는 문제를 푸는 방법 1. Container를 정렬한 후 N번째 혹은 최대(최솟값)을 찾는다. 2. Heap 자료구조를 사용하여 Heap 속성을 유지하는 이진 트리를 만든 후, Root 노드에 접근하여 최댓값 (혹은 최솟값)을 찾거나 N번 Pop을 실행해 원소를 찾는다. 2번의 경우 Container를 정렬하지 않고 시간 복잡도 O(log n)으로 문제를 풀 수 있다. 코딩 문제로도 내기 좋은 문제인듯? 정렬을 쓰지 않아야 하는 조건이 있고, 시간 복잡도도 물어볼 수 있겠다. 2번을 사용하기 위해서는 Heap 자료구조에 대한 이해가 필요하다. 이는 아래 포스팅을 참고하자. [자료구조] 힙(Heap), 우선 순위 큐 Heap, 힙 .. 2023. 7. 30.
[자료구조] 힙(Heap), 우선 순위 큐 Heap, 힙 힙(heap)은 힙 속성을 만족하는 tree를 기반으로하는 자료구조 이다. 힙 속성은 다음과 같다. A가 B의 부모 노드라면, A 노드의 값은 B 노드의 값과 대소 관계가 성립한다. 이때, 부모 노드가 자식 노드보다 값이 크다면 '최대 힙', 반대라면 '최수 힙'이라고 지칭한다. 각 노드 간의 대소 관계는 오직 부모 노드와 자식 노드 간에만 성립되고, 형제 노드 사이에는 대소 관계가 정해지지 않는다. 힙은 자식 노드의 최대 개수에 따라 종류가 나니ㅜ는데, 보통은 자식 노드가 2개인 이진 힙 (Binary tree)에 사용한다. 힙을 사용하는 이유는 배열에서 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위함이다. 힙은 가장 큰 값 (혹은 가장 작은 값)이 Root 노드에 오는 특징이 있고.. 2023. 7. 30.
Interval, Scheduling 문제 (LeetCode 435) 문제 설명 Interval을 Scheduling 하는 문제는 코딩 문제의 대표적인 유형 중 하나이다. 예를 들어, 시계열을 기준으로 시작 시간과 종료 시간이 주어진 여러개의 수업이 있을 때, 이를 최대한 많이 수강할 수 있는 수업들을 Scheduling 하는 것이다. 이 문제는 Sorting과 Greedy Algorithm 개념을 활용해 풀 수 있다. 먼저 Scheduling 문제는 Greedy Algorithm을 적용할 수 있다. 이를 적용하기 위해서는 2가지를 고려해야 하는데, 첫번째는 각 Interval이 Sorting 되어야 한다는 것이다. 그리고 Interval의 종료 시간을 기준으로 Sorting 되어야 한다. 문제 예시 4개 수업의 시작 시간 및 종료 시간이 다음과 같이 주어졌을 때, 겹치지.. 2023. 7. 28.
LeetCode 62. Unique Path Level은 Medium으로 책정되었지만 좀 더 쉬운 난이도의 문제이다. 데이터 구조 Queue를 사용하고 Dynamic Programming 개념을 차용하면 풀 수 있다. class Solution { public: int uniquePaths(int m, int n) { int arr[100][100] = { 0 }; int AlreadyQueue[100][100] = { 0 }; queue grid; pair SearchGrid; grid.push(make_pair(0, 0)); arr[0][0] = 1; while (!grid.empty()) { SearchGrid = grid.front(); grid.pop(); // Go Down if (SearchGrid.first < (m - 1)){ ar.. 2023. 7. 27.

티스토리툴바