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개의 원소는 변하지 않았다.이를 활용해, 맨 처..

1. 구간합 알고리즘이란?1차원 배열에서 특정 구간 내의 원소들의 합을 구하는 알고리즘이다.2. 왜 써야 하는가?위의 예시에서 A에서 B까지의 구간 합을 구한다면, 어떻게 구할 것인가? 혹자는 2번 index부터 7번 index까지 for 반복문을 활용해 차례대로 더할 것이다. 혹자는 0에서 A번까지의 누적합을 구하고, 0~B번까지의 누적합을 구해, 둘을 빼서 구할 것이다. 만약 단일 계산이라면, 이런 식의 풀이는 n번의 반복일 뿐이니 괜찮을 수 있다. 하지만, 문제에서 여러 개의 구간합을 반환하길 바란다면? 매번 이러한 반복문을 반복하는 것은 비효율적이다. 이는 시간 초과로 이어질 수 있다.시간 복잡도로 계산해 보겠다. 최악을 상정해야하니, N개의 원소를 가진 배열에서 0~ N~1까지의 계산을 K번 반..

1. 그리디 알고리즘은 무엇인가요? 💡Greedy Algorithm은 매 선택의 순간마다 당시에 고를 수 있는 최선의 선택지를 골라가는 것이 전체에서 봤을 때 최선의 선택이라고 가정하는 알고리즘이다.예를 들어 다음과 같은 문제가 있다고 해보자.현재 A의 시점에서 고를 수 있는 선택지 중 C가 최단거리이다. 그러므로 C를 선택한다.C 시점에서 고를 수 있는 선택지 중 최단 거리로 갈 수 있는 노드는 G이다. 따라서 G를 선택한다. 두번의 선택 후 무조건 F를 비용 0으로 갈 수 있다고 할 때, 전체 노드는 다음과 같다.매 순간 갈 수 있는 최선의 선택지를 골랐더니 전체에서 봤을 때도 최선의 선택이었다. 이와 같이 매 순간의 최선 = 전체의 최선 이 성립할 때, 이러한 논리를 Greedy 알고리즘이라 한다..

1. 시간 복잡도 란?(1) 개념시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.(2) 표기 방법의 종류시간 복잡도를 표기하는 방법에는 다음의 3 가지가 있다.이름설명빅-오메가 표기법문제를 풀기 위해 주어진 상황이 최선의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-세타 표기법문제를 풀기 위해 주어진 상황이 보통의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-오 표기법문제를 풀기 위해 주어진 상황이 최악의 상황일 때 필요한 연산 횟수를 나타내는 표기법예를 들어 설명1~100의 숫자가 랜덤한 순서로 저장된 배열이 주어졌을 때, 해당 배열에서 56의 INDEX를 찾아서 출력하라 라는 문제를 풀어야 한다고 하자.이때 내가 선택한 방법은 배열의 첫 번째 인덱스부터 일일히 조회이다.빅-오..