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(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..

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. 기수 정렬이란?수들의 자릿값을 활용해, 데이터를 정렬하는 정렬방법(지금까지 배운 정렬들은 수 들간의 대소 관계를 비교하는 비교 정렬이었지만, 기수 정렬은 데이터 간의 대소 관계를 비교하지 않음.)시간 복잡도는 O(kn)이다. 여기서 K는 입력으로 주어진 데이터 중 가장 큰 자릿값을 말한다. 코딩테스트에서는 최대값이 10억을 넘어가는 경우가 드물기 때문에 실질적으로 O(N)의 시간안에 정렬이 가능하다는 소리이다.하지만 강철의 연금술사처럼 등가교환의 원칙이다. 해당 정렬을 구현하기 위해서 원래는 Queue가 10개가 필요해서 메모리를 많이 잡아먹는다. 이러한 메모리 사용량을 줄이기 위해 본 포스팅에서는 누적합 배열을 이용한 구현 방법을 소개하겠다.2. 원리0. 세팅현재 확인 중인 자릿값을 가진 숫자가 ..

1. 문제 설명 📌문제 링크1차원 배열이 주어지고, 해당 배열을 버블 정렬로 정렬한다고 했을때, 전체 과정 중에서 swap은 몇 번 일어났는지 구하라.2. 접근 방식 🗃️Key Word: Merge_sort, Two Pointer분할 정복, 투 포인터를 활용해 입력에 대해 병합 정렬을 실행한다.매 재귀 순간마다 정렬이 될텐데, 이때 자리 바꿈이 일어난 횟수를 센다.위의 과정에서 구한 자리 바꿈 횟수를 누적해 출력한다.전체 과정을 간략히 설명하면 다음과 같다.(1) 지금부터 병합 정렬이 무엇인지,(2) 버블 정렬로 정렬하라 했는데 왜 병합 정렬을 사용하고 그것이 통하는지,(3) 어떻게 구현하면 되는지세세하게 설명하겠다.(1) 병합 정렬이 무엇인지병합정렬은 분할 정복과 투 포인터를 활용해 값들을 정렬하는..