1. 슬라이딩 단조 큐란 무엇인가요?슬라이딩 단조 큐란, DECK을 활용해 구현한 슬라이딩 윈도우로, 슬라이딩 윈도우 구간 내의 최소값, 최대값을 O(1)에 찾기 위해 고안한 구현체이다. 단조라는 이름이 붙은 이유는, 구간 내 최소값을 찾고 싶을 경우, Deck 내부 원소들이 오름차순으로 유지되고, 구간 내 최대값이 찾고 싶은 경우 내림차순으로 유지되기 때문이다.사실 내가 만든 이름이다...😂슬라이딩 윈도우 심화 문제를 풀면서, 슬라이딩 윈도우를 Deck으로 구현한 형태가 꾸준히 나오는데, 인터넷 여기 저기 찾아봐도, 형태만 있을 뿐 이것의 제대로 된 이름이 없었다.따라서 정식 명칭은 아니지만! 설명의 편의를 위해 앞으로 현 구간 내의 최소값과 최대값을 찾기 위해 Deck으로 구현한 슬라이딩 윈도우를 ..

0. 그래프 탐색의 기본인 DFS와 BFS그래프 탐색이란 무엇인가?그래프 탐색이란, 정점과 간선으로 이루어진 그래프에서 특정 정점을 선택하고, 해당 정점에서 인접한 정점을 방문하는 것을 말한다. 이러한 정점 방문 방법에는 크게 2가지가 있는데, 이것이 앞으로 살펴볼 DFS와 BFS이다.우리는 위의 그래프를 예시로 사용하며 하나씩 이해해 보겠다.1. DFSDFS는 Depth First Search의 약자로 깊이 우선 탐색을 뜻한다. 말 그대로 방문하기로 정한 인접 정점의 최대 깊이까지 탐색을 마친 후, 다음 인접 정점을 확인하는 것이다. 알고리즘 논리는 다음과 같다.(1) 현재 정점과 인접한 정점을 방문한다.(2) 방문한 정점에서 아직 방문하지 않은 정점이 있다면 방문하지 않은 정점을 모두 방문할 때까지 ..

1. 기수 정렬이란?수들의 자릿값을 활용해, 데이터를 정렬하는 정렬방법(지금까지 배운 정렬들은 수 들간의 대소 관계를 비교하는 비교 정렬이었지만, 기수 정렬은 데이터 간의 대소 관계를 비교하지 않음.)시간 복잡도는 O(kn)이다. 여기서 K는 입력으로 주어진 데이터 중 가장 큰 자릿값을 말한다. 코딩테스트에서는 최대값이 10억을 넘어가는 경우가 드물기 때문에 실질적으로 O(N)의 시간안에 정렬이 가능하다는 소리이다.하지만 강철의 연금술사처럼 등가교환의 원칙이다. 해당 정렬을 구현하기 위해서 원래는 Queue가 10개가 필요해서 메모리를 많이 잡아먹는다. 이러한 메모리 사용량을 줄이기 위해 본 포스팅에서는 누적합 배열을 이용한 구현 방법을 소개하겠다.2. 원리0. 세팅현재 확인 중인 자릿값을 가진 숫자가 ..

1. Quick 정렬은 무엇인가?Pivot(중추)가 되는 값을 하나 선정해서 그 값보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 모은다. 이제 나눠진 두 그룹 내에서 다시 Pivot을 선정하고 이 과정을 반복한다. 값을 더 이상 쪼갤 수 없을 때까지 반복하면 모든 값이 정렬되어 있다.2. 원리병합정렬과 마찬가지로 분할 정복을 활용하는 또 다른 예시이다. 병합 정렬에서는 선 분할 후 정복 이었다면, quick 정렬은 선 정복, 후 분할 형식이라 생각하면 되겠다.정복에는 마주보는 투 포인터가 활용된다. 어떻게 쓰이는지는 밑의 예시에서 자세히 설명하겠다. (1) Pivot 정하기 (정하는 방식은 때에 맞게 자유)(2) Pivot보다 큰 값은 오른쪽으로 몰기, 작거나 같은 값은 왼쪽으로 몰기 (정복 by 투 포..

1. 병합 정렬은 무엇인가?병합 정렬은 (1) 세세하게 나눈다. ➜ (2) 하나씩 정복한다 의 방식으로 정렬되지 않은 일련의 데이터를 정렬시키는 방법이다.2. 원리다음 3가지 순서를 따라서 진행된다.(1) *더 이상 쪼갤 수 없을 때까지 데이터를 분리시킨다.* ( 분할 by 재귀)(2) 인접한 데이터 그룹끼리 대소관계 비교를 통해 정렬시킨다. (정복 by 투 포인터)(3) 정렬된 데이터를 다시 하나의 그룹으로 간주하고, 데이터 전체가 하나의 그룹이 될 때까지 (2)번을 반복한다.3. 예시비 정렬된 일련의 데이터를 위의 방식을 차례대로 수행하여 정렬시켜보겠다.7, 2, 4, 3, 1, 5, 6의 일련의 데이터를 오름차순으로 정렬시킨다고 가정해보자.(1) 분할 by 재귀재귀를 통해 데이터들을 더 이상 쪼갤 ..

1. 원리사전 세팅: 정렬되지 않은 1차원 배열이 주어졌고, 해당 배열을 오름차순으로 정렬함을 전제로 한다.배열의 첫 원소를 조회한다.다음 원소와 대소관계를 비교하고, 그에 따라 적절한 조치를 한다.조회중인 원소 > 다음 원소: 둘의 자리를 바꾼다.조회 중인 원소 다음 원소: 아무 조치 없이 지나간다.2번 과정을 배열 끝까지 반복한다. 이러면 정렬되지 않은 영역 최우단에 정렬되지 않은 값 중 최대값이 위치하게 된다.(즉 3번 과정 1번 당 하나의 원소가 정렬된다.)3번 과정을 배열 내의 모든 원소가 정렬될 때까지 반복한다.2. 예시위 사진과 같이 주어졌을 때,5가 1보다 큼으로 둘의 자리를 바꾼다.5가 3보다 큼으로 둘이 자리를 바꾼다.5는 7보다 작음으로 자리를 바꾸지 않는다.7이 2보다 큼으로 자리를..

0. 글이 흘러가는 방향먼저 개념 설명을 하고, 투 포인터를 활용하는 대표적인 문제 2개를 직접 풀어보며, 개념에 대한 보충을 하겠다.1. 개념1차원 배열에 두 개의 포인터를 두고, 두 포인터에 의미를 부여하여 문제를 푸는 기술배열 안에서 특정 조건의 값을 구하는 문제에서, 일반적으로 시간 복잡도가 O((N^{2}))가 든다면, 투 포인터 기법을 활용하면 시간 복잡도를 O(N)으로 줄일 수 있다. (이유는 활용을 살펴보며 설명하겠다.)(1) 유형투 포인터를 운용하는 유형에는 크게 2가지가 있다.a.단방향 운용L 포인터와 R 포인터가 한쪽 방향으로만 움직이는 것이다. 슬라이딩 윈도우의 양끝을 의미한다고 보면 된다. 슬라이딩 윈도우와 다른 점은 포인터에 따라 구간의 길이가 가변적이라는 것이다.b. 양방향 운..

0. 알아볼 것1. 슬라이딩 윈도우란?길이가 N인 1차원 배열안에 길이가 W인 움직이는 구간을 생성하여, 해당 구간을 한 칸씩 움직이면서 구간 내 정보를 추출하여 문제를 해결하는 기술(N과 W는 상수)W인 구간을 움직이는 것이 마치 창문을 밀고 당기는 것과 같다고 하여, 움직이는 구간을 슬라이딩 윈도우라고 명명함.2. 활용(1) 구간합1차원 배열에서 특정 구간 내의 합을 원하는 문제에서 활용.a. 어떻게 활용?배열의 길이가 N, 슬라이딩 윈도우의 길이가 W이고 해당 창문을 오른쪽으로 한 칸씩 움직인다면, 매 움직임 마다, 이전 위치에서의 W-1의 원소는 변하지 않고 구간 내에 유지된다. 예를 들어 N = 10, W = 3이라 가정하면,그림과 같이 W-1인 2개의 원소는 변하지 않았다.이를 활용해, 맨 처..