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

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

1. 문제 설명 📌문제 링크문제를 보며, 찾아낸 조건은 다음 3가지 였다.1️⃣ 최소 개수의 회선을 복구하라2️⃣ 모든 서로 다른 2 대의 컴퓨터가 교신이 가능해야 한다.3️⃣ 슈퍼 컴퓨터에서 다른 컴퓨터로의 통신 최소 비용은 복구 이전과 같아야 한다.문제를 풀며 느낀 점은,3️⃣ 때문에 1️⃣은 있으나 마나 한 조건이 되었다. 3️⃣을 만족시키려면 다익스트라를 활용해서, 최단 경로를 찾아야 하고, 그 최단 경로에 사용된 회선보다 개수를 더 줄일 수 없기 때문이다. (줄이면, 어떤 컴퓨터에는 슈퍼컴퓨터가 도달하지 못한다.) 2️⃣ 또한 다익스트라를 활용하면, 최소 슈퍼 컴퓨터를 매개로 모두 교신할 수 있기에 따로 구현해야 하는 조건이 아니다. 따라서 다익스트라를 하며 거쳐가 경로를 기억하는 문제이다...

1. 문제 설명 📌문제 링크지헌과 성하의 새로운 약속 장소를 찾아주는 문제로서, 다익스트라를 통해 각자의 출발점에서 모든 정점까지의 최소 도달 비용을 구하고, 이를 통해 4가지 조건을 만족하는 약속 장소를 찾으면 된다.하지만, 출제자가 지문을 되게 모호하게 적어서, 조건의 진의가 헷갈린다.약속 장소의 조건은 다음과 같다.1️⃣ 각자의 출발점은 약속 장소가 될 수 없다.2️⃣ 둘 다 최소 비용으로 닿을 수 있는 장소여야 한다.3️⃣ 지헌이가 성하보다 먼저 도착하는 장소여야 한다.4️⃣ 위의 조건을 모두 만족하는 장소가 복수라면, 그 중 지헌이가 빨리 도착하는 장소를 고른다. (이 마저도 복수이면, 정점 번호가 빠른 것을 고른다.)이 조건을 보면,각자의 출발점이 아니면서, 지헌이가 성하보다 먼저 도착하면서..

1. 문제 설명 📌문제 링크N개의 수가 주어지는데, 이 중 하나를 택해보자. (택한 수를 E라 부르겠다.)이 E를 나머지 N-1개 중 2개를 합해서 만들 수 있으면 좋은 수라고 부르겠다.이떄 좋은 수의 개수는 몇 개 인가?2. 구현 방법 🗃️KEY WORD: 마주보는 투 포인터1️⃣ N개의 수를 arr이란 배열에 입력 받아서 오름 차순 정렬한다.2️⃣ 포인터를 3개 두어보자. 각각의 의미는 다음과 같다.E = 좋은 수가 될지 안될지 확인하는 target을 가리키는 포인터 (0부터 점점 오른쪽으로 간다.)L = N개의 정렬된 수 중 제일 좌측을 가리키는 포인터 (점점 오른쪽으로 간다.)R = N개의 정렬된 수 중 제일 우측을 가리키는 포인터 (점점 왼쪽으로 간다.) 3️⃣L과 R이 서로 만날 때 까지 ..

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. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 트라이0️⃣ 중요한 처음 세팅!: Tri 구조를 만드는데 구성요소는 다음과 같다.(a) `기본적인 자식 노드`: HashMap로 구현 (자식 알파벳 이름, 그것의 객체)(b) `lenMap`: 현재 조회 중인 문자 뒤로 부터 전부 물음표라고 쳤을 때, 그 와일드카드를 만족하는 문자가 몇 개 있는지 세는 자료구조, HashMap로 구현 (문자열의 길이, 만족하는 문자 개수)1️⃣ 입력: 문자열 그대로 받는 Tri 하나, 문자열을 뒤집어서 받는 Tri 하나씩 만들어 각각 따로 따로 입력 받음입력받으면서, 매번 LenMap의 값을 갱신한다.2️⃣ 찾기: 와일드카드 ?를 만나기 전까지, 트라이를 깊게 들어간다. 반환값이 될..

1. 문제 설명 📌문제 링크문제에서 원하는 것은 A의 전화번호를 치고 있던 와중에, B의 전화번호를 완성시켜서, B로 전화가 걸리는 일이 없으면 일관성이 TRUE, 전화가 한 번이라도 걸리면 FALSE라는 뜻이다.즉 '하나의 전화번호가 다른 전화번호의 접두어가 되는지?'를 확인하라는 문제이다.2. 구현 방법 🗃️KEY WORD: TRI기본적인 트라이를 그대로 사용한 문제라 따로 부연 설명할 것이 없다. 아직 트라이에 대한 개념이 없다면, 미리 학습 하고 오시길 바란다.0️⃣ HashMap을 활용하여 전형적인 트라이 구조 트리를 구현한다. + 문자열을 삽입하는 insert 매소드를 구현한다.1️⃣ 문자열 (이하 str)을 트라이에 삽입한다.2️⃣ 만약 str을 삽입하는 도중에, 현재 조회 중인 문자가 ..

1. 문제 설명 📌문제 링크벨만 포드 알고리즘 공부하고 한 번 써보라는 견본 문제이다.주어지는 간선 정보는 모두 단방향이다.2. 구현 방법 🗃️KEY WORD: BELLMAN-FORD ALGORITHM0️⃣ 형태로 모든 간선을 저장, 최소 비용 배열인 dist [] 선언.(N: 정점의 수, M: 간선의 수, dist 배열은 Long.MAX_VALUE로 초기화)1️⃣ 출발지를 1로 설정하고, N-1만큼 모든 간선을 돌면서 다음 구문을 실행한다.1️⃣-1) 현재 조회중인 간선의 출발지를 A, 도착지를 B, A➜B의 가중치를 C라고 할 때,dist[A] != ∞︎︎ && dist[B] > dist[A] + C이면, dist[B] = dist[A] + C로 최신화 해준다.2️⃣ 위 과정을 끝낸 후, 벨만 ..

1. 문제 설명 📌문제 링크가중치 양방향 그래프가 주어질 때, 출발지에서 도착지 까지 한번의 이동으로 가져갈 수 있는 물건의 최대 중량을 구하여라.2. 접근 방식 🗃️KEY WORD: Parametric Search, Binary_Search,DFS(1) 가중치 양방향 그래프를 인접리스트로 구현한다.(2) 이분탐색을 활용해, 한번에 옮길 수 있는 물건의 최대 중량을 구한다. (이분 탐색은 다음과 같이 진행 된다.)a. 문제에서 주어진 최대 중량과 최소 중량을 활용해 중앙값을 구한다.b. 해당 중앙값을 한 번에 옮길 수 있는 최대 중량이라 쳤을 때, 도착지까지 옮기는 게 가능한지 확인한다.c-1. 가능하다면 최소 중량을 현 중앙값 + 1 올려서, 다음에 구할 중앙값을 상향 조정 한다.c-2 .불가능하다..

1. 문제 설명 📌문제 설명2. 접근 방식 🗃️KEY WORD: BLACK-RED TREE, BST(Binary_Search_Tree)(0) BLACK-RED TREE 로 구현된 TreeSet을 활용한다.일반 BST일 때의 Depth를 저장하는 int [] depth 배열도 만든다.(1) TreeSet에 0과 N-1을 넣는다. (Null Pointer Exception 방지)depth[0]과 depth[N-1] 의 값은 -1을 넣는다. (계산에 영향을 주지 않기 위함)(2) TreeSet에 root 노드부터 끝노드까지 차례로 조회한다.조회했을 당시의 해당 노드보다 작으면서 최대값과 크면서 최소값인 노드가 무엇인지 구한다.(3) depth[현재 노드] = (2)에서 구한 둘 중 depth 값이 더 큰 ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD : Binary Search, Parametric Search, Greedy Algorithm(1) 집 간의 최소 거리와 최대거리를 활용해, 임의의 거리 d를 산정한다.(2) '모든 공유기 사이의 거리가 최소한 d 이상인가?'를 boolean 값으로 계산한다.(3) (2)번이 true면, start = mid + 1로 거리를 상향 조정, false면 end = mid - 1로 하향 조정한다.(4) start와 end가 엇갈렸을 때, start - 1이 답이다.(1) Parametric Search 이용해당 문제는 가장 인접한 두 공유기 사이의 최대 거리 즉 최소값 중에서 최대값을 구하는 최적화 문제이다. 최적화 문제는 바로 풀기 어렵기 때..

1. 문제 설명 📌문제 설명2. 접근 방식 🗃️KEY WORD : Binary Search, Parametric Search(1) 모든 지방 예산의 합 총 예산, 그대로 예산 책정 하고, 제일 컸던 지방 예산을 출력(2) 모든 지방 예산의 합 > 총 예산: 예산 최소값과 최대값 사이에서 이분 탐색을 통해, 모든 예산을 처리하면서 최대인 값을 찾아서 출력 (1) Parametric Search 쓰인 곳모든 예산을 처리할 수 있는 최대값 구하기 ➜f(d) = 예산 상한액이 d일 때, 이걸로 총 예산 M 내에서 전부 처리 가능한가? 여러 개위와 같이 최적화 문제를 결정 문제 여러개로 바꾸어 푼다.f(d) = true가 나오는 값 중 최대한 오른쪽에 있는 값을 구하면 답이다. (즉 f(d) = true가..

1. 문제 설명 📌문제 링크문제x 중심선 위에 n개의 Thread가 존재한다. $T_{i}$라 불리는 i번째 Thread의 길이는 $l_{i}$와 해당 Thread의 시작 지점 위치인 $x_{i}$로 나타내어 진다. 두 변수 모두 Integer 이다. 우리는 각각의 Thread 마다 매듭을 짓고 싶어 한다. 매듭의 위치 또한 반드시 Integer여야 한다. 매듭은 Thread 안의 어느 지점에서든 상관 없이 만들어질 수 있고, Thread의 길이가 매듭에 의해 줄어들지 않는다고 가정한다. 당신은 또한 어떠한 Thread도 또 다른 Thread에 의해 완전히 포함되어지지 않는다고 가정한다. 어떤 의미냐면, $x_j$ 우리는 가장 가깝게 인접한 두 매듭 사이의 거리를 가능한 한 크게 만들기 위해서 각 Th..

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

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

1. 문제 설명 📌문제 링크최소한으로 플러그 빼는 횟수 세라! (다시 꽂는 횟수는 세지 마라!)2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHM(0) 사전 세팅: 멀티탭을 나타내는 SET, 각 전자 기기의 현재 조회 중인 위치 기준 가장 가까운 index를 나타내는 QUEUE[전자기기 번호], 명령 순서를 나태는 ORDER[]를 미리 구현해둔다.(1) QUEUE[] 채우기: 앞서 말했다시피, index는 각 기기의 번호이고, 배열마다 자신만의 큐를 가지고 있다. 큐에는 해당 index 번호 기기가 나온 index를 만날 때마나 삽입한다. 이렇게 되면, 큐의 front에는 가장 처음 조우한 index가 적혀 있을 것이다.(2) SET(멀티탭) 채우기: 멀티탭을 나타내는 SET을 채운다..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHM(1) 목적지의 x축 혹은 y축에 일치할 때까지 대각선 가로지르기로 이동한다. 비용 = Math.min(2*S, W)(2) 목적지와 x축 혹은 y축이 일치한 이후에는 한칸 이동과 대각선 가로지르기 중 최소 비용을 택해서 이동한다.a. S > W인 경우 (목적지 - 현 위치) == 짝수일 경우 W로만 이동, 홀수 일 경우, 목적지-1까지 W로 이동 후 마지막 한 번을 S로 이동b. S 인 경우, S로 쭉 이동 3. 코드 소개 🔎import java.io.*;import java.util.Arrays;import java.util.StringTokenizer;public class Main { /* ..

1. 문제 설명 📌✨ 문제 링크 ✨문제 설명이 꽤 직관적이다. 다만 내가 한 번에 이해하지 못한 부분이 있어, 그에 대한 부연 설명을 하고 다음 장으로 넘어가겠다.교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).문제의 입력으로 일련의 데이터가 공백으로 구분되어 주어지는데, 해당 데이터의 index = 공장, value = 해당 공장에서 사야할 라면의 개수 라는 뜻이다.2. 접근 방식 🗃️KEY WORD: DP(가) 문제에서 주어진 3가지 방법을 숙지한다.i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.i번 공장과 ..

1. 문제 설명 📌문제 링크문제 설명이 직관적이라 추가 설명 생략2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHM(1) 회의의 시작 시간과 끝 시간을 묶어서 하나의 객체로 만들기. 또 이 객체들을 ArrayList로 묶기(2) 회의를 끝 시간이 빠른 순으로 정렬 (끝 시간이 같다면 시작 시간이 빠른 순으로 정렬)(3) int prev_end_time 초기값: ArrayList.get(0)의 끝시간(4) ArrayList를 순회하며 prev_end_time 인 경우 ans_cnt +1 올리고, prev_end_time = now.endTime으로 경신(1) Greedy Algorithm 인 것은 어떻게 알았니? 🤔결론: 회의를 끝 시간 순으로 정렬 했을 때, 순서가 [meeting..