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. 구현 방법 🗃️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. 문제 설명 📌문제 링크최소한으로 플러그 빼는 횟수 세라! (다시 꽂는 횟수는 세지 마라!)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..

1. 문제 설명 📌문제 링크한 개 이상의 일이 존재하고, 일마다 시작시간, 끝시간, 완료했을 때 이익 이 주어질 때, 주어진 일련의 일들에서 나올 수 있는 최대 이익을 반환하라.조건선택한 일들은 서로 일의 진행 시간이 겹치면 안된다.A라는 일의 endTime = X 이고, B라는 일의 startTime = X이면 A와 B를 연달아 일할 수 있다. 이는 겹치는 것으로 간주하지 않는다.2. 접근 방식 🗃️KEY WORD: DP(1) 초기화(가) 각각 산재되어 있는 startTime, endTime, profit을 같은 일 단위로 묶어서 나열 ➜ class Job + ArrayList(나) ArrayList를 시작 시간이 이른 순으로 정렬(다) DP용 배열 maxProfit[] 만들기 (maxProfit[..

1. 문제 설명 📌문제 링크해당 문제는 자신이 사용하는 언어의 내부 라이브러리 정렬을 사용하지 않고 O(nlog(n))에 문제를 푸는 것이 관건이다.(문제에서도 진짜 라이브러리 정렬을 썼는지 안 썼는지는 양심에 맡겼다...)2. 접근 방식 🗃️Key word: Merge sort병합 정렬의 최악의 시간 복잡도가 O(nlog(n))이기 때문에 쓰면 풀린다. 하지만 한 가지 백준과 다른 점이 있어 1시간 동안 헤멘 부분이 있다. 리트코드는 알고리즘 자체의 시간 뿐만 아니라, 자료구조를 사용하며 생기는 메모리 오버 헤드, 가비지 컬랙션 부담에 따른 실행 시간 증가 또한 실행시간에 포함시키는 듯 하다.그렇게 느낀 이유는 내가 Merge_sort를 하면서 부분 정렬된 값들을 넣을 tmp 임시 배열을 매 재귀..

1. 문제 설명 📌문제 링크배열을 정렬해서, 인접한 두 값의 차의 최대값을 반환해라2. 접근 방식 🗃️KEY WORD: RADIX SORT해당 문제는 java의 native 정렬 알고리즘을 활용해도 되지만, 기수 정렬(Radix-sort)를 활용해보고 싶어서, 해당 알고리즘을 활용해서 문제를 풀어보았다. 그저 정의 그대로 구현한 것 뿐이라, 따로 접근 방식을 설명할 것이 없다. Radix-sort에 대해 모르시는 분들은 다음 링크에 내용이 적혀 있으니 한번 보고 오는 것을 추천 드린다.https://dalcheonroadhead.tistory.com/5583. 코드 소개 🔎import java.util.*;class Solution { public int maximumGap(int[] nums..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: QUICK SORTING사실 JAVA 내부 라이브러리에 있는 Sorting을 쓰면 간단히 해결되는 문제이지만, Qucik Sorting 연습을 위해 Quick Sorting을 사용해 보았다. quick sorting의 경우, 최악의 시간 복잡도가 O( $N^2$ )이라서 문제에 제시된 최대 데이터 량을 보면, 시간초과가 나야 하는 것이 맞다. (아마 Quick Sorting을 쓰면 시간 초과가 나는 테스트 케이스를 안 넣어놓은 것 같다.)(1) 큰 흐름(1) 현재 정렬해야 하는 영역의 중앙값을 PIVOT으로 선정(2) PIVOT을 영역 최좌단 값과 자리 교체. (pivot은 비교 대상에 속하지 않도록 하기 위함.)(3) PIVOT을 제외..

1. 문제 설명 📌문제 링크예시로 나온 C++ 코드를 눈으로만 읽어서는 이해가 어렵다. 따라서 N과 A[] 배열에 각각 값을 넣어보며 생각해보길 바란다. 코드의 주요 골자는, 반복 Loop 중에서 최초로 어떠한 수도 SWAP이 일어나지 않는 Loop는 몇 번째냐? 를 구하는 것이다.2. 접근 방식 🗃️KEY WORD: Bubble Sort버블 정렬 자체는 사용하지 못한다. 왜냐하면 입력 데이터의 최대 개수가 500,000 인데, O(N^2)인 버블 정렬을 이용하면 10^9를 넘겨 시간초과가 나기 때문이다. 해당 문제는 Bubble Sort 자체가 아니라, Bubble sort이 작동하는 방식에 대한 정확한 이해를 필요로 한다.다음과 같은 배열이 주어졌을 때, 첫 번째 Loop를 돌며 버블 소트를 진행..