1. 정의Union-Find 알고리즘은 이름 그대로 밑의 두 가지를 수행하는 알고리즘이다.union: 2개의 서로소 집합을 합쳐 하나의 집합으로 만든다.find: 하나의 원소가 속한 집합이 무엇인지 찾는다.하지만 이를 위해 집합의 명칭과 원소의 명칭을 따로 선언해서 별개로 관리하면, 알고리즘 자체보다 변수가 무엇을 뜻하는지 찾는데 시간을 더 쏟게 될 것이 뻔하다. 따라서 알고리즘의 가독성과, 변수 관리의 효율을 위하여 트리 자료구조를 활용해서 알고리즘을 구현한다.위 그림에서 하나의 트리에 묶이는 노드들이 곧 하나의 집합에 묶이는 원소들이다. 따라서 집합으로 표현하면 {2,4,5}, {3,6,7}로 나눌 수 있다. 이제 다시 union과 find를 이에 맞춰서 정의해보자.union: 2개의 서로소 집합의 ..

1. 오일러 피 함수란? $$φ(n) = n이하\;자연수\;중\;n과\;서로소인\;수의\;개수$$ $φ(12) \; = \; 4$이다.2. 사전 학습오일러 피 함수의 증명을 위해서 다음 챕터에서 오일러의 곱 공식을 살펴볼 것인데, 사전에 학습해야할 내용이 있어서 미리 소개하겠다.1️⃣ 소인수: 임의의 수 K의 소수이면서 인수인 수이다. 예를 들면 12의 소인수는 2와 3 이 있다.2️⃣ 소인수 분해: 임의의 수 K를 소수로만 인수 분해하는 것이다. 예를 들어 12를 소인수 분해하면, $12\,=\,2^{2}\,*\,3$이다.3️⃣ 서로소: A와 B가 서로소라는 뜻은, A와 B의 공약수가 1말고는 없다는 뜻이다.4️⃣ $φ()$: 오일러 파이라고 읽는다.5️⃣ $\prod_{p \mid N}$: 여러 값의 합..

1. Parametric Search 란?최적화 문제를 여러 개의 결정 문제 + 이분 탐색으로 변환시키는 문제 접근 방법이다. 여기서 3가지 키워드가 나왔는데, 이분탐색이 뭔지는 많은 사람들이 알테니, 최적화 문제와 결정 문제에 대해 먼저 설명하고 가겠다.(1) 최적화 문제문제의 조건을 만족하는 해의 범주가 존재하고, 그 중에서 최적의 답(최소값, 최대값 등)을 구하는 문제를 말한다.Thread Knots라는 문제를 예시로 들어보면, 해당 문제는 'n개의 매듭을 성공적으로 놓았을 때, 가장 가까운 두 개의 매듭 사이의 최대 거리를 출력하라'고 요구한다.그렇다면, 여기서 가능한 해의 범주는 n 개의 매듭을 각 Thread에 성공적으로 놓는 모든 경우이고,최적의 해는 가장 가까운 두 매듭 사이의 최대 거리일..

1. 벨만포드 알고리즘이란?음수인 가중치가 존재하는 그래프에서도 최단 경로를 구할 수 있게 해주는 알고리즘.ONE TO ALL 알고리즘: 시작점을 고르면, 해당 정점에서 모든 정점까지의 최단 경로를 구할 수 있다.다익스트라와 달리, 음수 가중치가 있어도 최단 경로 구할 수 있다.음수 사이클이 존재하는지도 확인 가능: 음수 사이클이 존재한다면, 사실 하나 이상의 정점으로의 최단 경로가 $- \infin$가 되기 때문에, 최단경로를 구하는 게 무의미해짐. 따라서 최단 경로를 구하는 게 무의미한지 여부도 파악 가능!음수 사이클가중치 그래프에서 정점 A에서 시작해서 A로 돌아왔는데 가중치의 합이 음수인 경우, 해당 사이클을 음수 사이클이라고 한다.해당 예시에서는 사이클을 돌수록 출발지에서 A,B,C까지의 거리가..

1. 트라이란?트라이는 트리의 일종으로서 대량의 문자열을 빠른 시간 안에 삽입, 삭제, 조회 하기 위해 고안된 알고리즘이다.2. 트라이의 원리'선두의 문자가 같은 녀석들끼리 최대한 같은 가지에 밀어 넣는다.'1️⃣ 노드 하나 = 문자 하나, 수직적으로 문자열의 문자를 하나씩 저장함2️⃣ A의 길이 B의 길이 인데, $A\subset{B}$ 인 경우, A와 B는 직계존속 (A = 부모 노드, B = 자식 노드)3️⃣ $A\nsubseteq{B}$ 인데, 둘이 같은 선두 문자를 가질 때, A와 B는 방계임 (형제 관계 이거나, 삼촌-조카 관계)이를 기초로 한 트라이의 한 형태이다. 해당 트라이에 넣은 문자열은 다음과 같다.["frodo", "front", "frost", "frozen", "frame", "..

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

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) 역할 전환** ➜ **(2) 하나는 대칭 이동, 하나는 그대로** 이다. 왜 그렇게 되는가 그냥 현상이라서 그렇게 알고 가야할 것 같다.

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

0. 구현 설명에 앞서...본 포스팅은 'JAVA를 활용해 다익스트라 구현을 어떻게 하는가?'에 대해서 바로 다룰 예정이다. 혹시 이론 공부가 필요하신 분들은 다익스트라 개념 정리 포스트를 한번 읽고 오시길 당부 드린다.1. 순차 탐색알고리즘 이론 그대로 코드로 옮긴 구현 방법이다.0️⃣ 시작점에서의 최단 거리 배열 (dist) 만들고 INF로 초기화1️⃣ 현 시점에서 방문하지 않은 노드 중 최소 비용으로 방문할 수 있는 노드(이하 A) 방문2️⃣ 해당 노드와 인접한 노드(이하 B)를 활용해 dist 배열을 최신화 한다.2️⃣-1) dist[B] > dist[A] + A ➜ B 간선 비용 일 시 dist 배열 최신화3️⃣ 모든 노드를 방문할 때까지 1️⃣,2️⃣ 과정을 반복한다.(1) 시간 복잡도 분석노..

1. 정의양수인 가중치만 있는 그래프에서 시작점을 $v_{start}$라고 할 때, $v_{start}$에서 모든 정점까지의 최단 경로를 구하는 알고리즘최단 경로:A ➜ B 의 최단경로는 A에서 B까지 가는 경로 중 최소 비용을 사용하는 경로를 의미한다.가중치가 없는 그래프에서는 간선의 수가 적을수록 최단 경로가 될 것이고, 가중치가 있는 그래프에서는 가중치를 작게 사용할 수록 최단 경로가 될 것이다.2. 원리KEY WORD: GREEDY ALGORITHM1️⃣ 시작점에서 각 노드까지 걸리는 최소 거리를 저장하는 배열을 만든다. (최소 거리 DASH-BOARD)2️⃣ 현 시점에서 방문하지 않은 노드들 중, 시작점에서 가장 최소 비용으로 갈 수 있는 노드(이하 A)를 매번 고른다.3️⃣ A와 인접한 노드들..

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

1. 정의A = Bq + R일 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 위의 정의를 활용하면 연쇄적인 나눗셈으로 A,B의 최대공약수를 소인수 분해 없이 구할 수 있다.2. 구현개발 언어로 이를 구현하기 위해서는 %(mod) 연산자를 알고 있어야 한다. A%B의 결과값은 A를 B로 나누었을 때, 나머지를 반환한다.큰 수를 A, 작은 수를 B라고 해보자.1️⃣ 큰 수를 작은 수로 나누고 나머지를 얻는다. 이때 나머지를 R이라 하자.A % B = R2️⃣ 작은 수를 나머지로 나눈다. 이때 나온 나머지 값을 R'라고 하자.B % R = R'3️⃣ 2번을 작은수가 나머지로 나누어 떨어질 때까지 반복한다.R % R' = 04️⃣ 작은 수를 나누어 떨어지게 만든 R'는 유클리드 호제법을 따라 거슬러..

1. 겪었던 문제LeetCode 문제를 풀며, 로직이 맞는 것 같은데도, 제출 시 계속 답이 틀리게 나와서, Debuging을 해보았습니다.제가 풀었던 문제는 이것입니다.문제를 안 푸셔도 알 수 있게 간단히 말씀드리면,target에 있는 값을 key = target[i], value = i 로 해서 map에 집어넣으려고 했습니다. target의 값은 다음과 같았습니다.target = [5,10,8,11,3,15,9,20,18,13]근데 System.out.println()으로 찍어보니 다음과 같이 나왔습니다!{1=3, 2=5, 3=4, 4=1, 5=0, 6=0, 8=2, 9=6, 10=1, 11=3, 13=9, 15=5, 18=8, 20=7}target에 없는 1이나 2 같은 값이 들어있던 것입니다. m..