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번 반..

0. 사전에 정의할 변수r과 c: 특정 원소의 행과 열 위치N: 2차원 배열의 크기 (2차원 배열은 정사각형 형태)1. 원리90도 회전을 할 경우, 행이 열이 되고, 열이 행이 된다. (서로의 역할이 바뀜)시계 방향으로 회전하면, Before(r,c) = After(c, n-1-r)반시계 방향으로 회전하면, Before(r,c) = After(n-1-c, r)각각 역할 전환 ➜ 하나는 대칭 이동, 하나는 그대로 이다. 왜 그렇게 되는가 그냥 현상이라서 그렇게 알고 가야할 것 같다.

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

4. 구현(1) 순차 탐색저번 게시글에서 설명한 작동원리 그대로 구현한 방식이다.방문한 정점과 그렇지 않은 정점 구분을 위해서, 방문배열을 사용한다.현재 정점에서 갈 수 있는 간선을 통해 dist[] 배열을 최신화하고, 방문 배열을 통해, 현재까지 방문하지 않은 정점 중 시작 정점에서 최단 거리로 갈 수 있는 정점을 택해야 한다.여기서 최악의 경우, 정점의 수가 N개라면, 매번 N번의 정점을 탐색해 다음 방문해야할 정점을 찾아야 하고, 이 행위를 모든 정점을 방문할 때까지 반복해야 하므로 최악의 시간복잡도는 O(N^2)이 든다.import java.io.*;import java.util.*;public class 순차탐색_다익스트라 { static int [] dist = new int [N]; ..

1. 개념(1) What? 다익스트라 알고리즘이 무엇인가요? 💡다익스트라 알고리즘은 한 정점에서 다른 정점으로 가는 최단 거리 비용을 구하는 알고리즘이다.다익스트라를 사용하면 시작 정점 S에서 직,간접적으로 연결된 모든 정점으로 가는 최단 거리 비용을 한 번에 구할 수 있다.(2) Why? 왜 해당 알고리즘을 써야 하나요? 🤔💭해당 알고리즘을 처음 접한다면 아마 지금까지 가중치가 없는 그래프에 대해서 정점 간의 최단 거리를 구하는 문제만 접해왔을 가능성이 높다. 가중치가 없는 그래프에서의 정점 간의 최단 거리는 BFS를 활용하면 쉽게 풀렸다. 왜냐하면 정점 사이를 잇는 간선의 개수가 곧 비용임으로 BFS를 돌렸을 때, 만나기까지 사용하는 간선의 개수만 세면 되었기 때문이다.하지만 가중치가 있는 그래..

GCD와 LCM의 관계A와 B의 최대공약수를 G, 최소공배수를 'L'이라 할 때, 다음 식이 성립한다.(A*B)/G = LWHY? 왜 Lcm = G*a*b 예요?최소공배수는 두 수 A,B의 공통된 배수 중 최소값임. 최소가 되려면, 불필요한 계산이 없어야함. 서로가 필요로 하는 최소의 값인 서로소만 곱하여 표현하면 그것이 최소공배수다.