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. 문제 설명 📌문제 링크최소한으로 플러그 빼는 횟수 세라! (다시 꽂는 횟수는 세지 마라!)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) 병합 정렬이 무엇인지병합정렬은 분할 정복과 투 포인터를 활용해 값들을 정렬하는..

1. 원리사전 세팅: 정렬되지 않은 1차원 배열이 주어졌고, 해당 배열을 오름차순으로 정렬함을 전제로 한다.배열의 첫 원소를 조회한다.다음 원소와 대소관계를 비교하고, 그에 따라 적절한 조치를 한다.조회중인 원소 > 다음 원소: 둘의 자리를 바꾼다.조회 중인 원소 다음 원소: 아무 조치 없이 지나간다.2번 과정을 배열 끝까지 반복한다. 이러면 정렬되지 않은 영역 최우단에 정렬되지 않은 값 중 최대값이 위치하게 된다.(즉 3번 과정 1번 당 하나의 원소가 정렬된다.)3번 과정을 배열 내의 모든 원소가 정렬될 때까지 반복한다.2. 예시위 사진과 같이 주어졌을 때,5가 1보다 큼으로 둘의 자리를 바꾼다.5가 3보다 큼으로 둘이 자리를 바꾼다.5는 7보다 작음으로 자리를 바꾸지 않는다.7이 2보다 큼으로 자리를..

1. 문제 설명 📌문제 링크1번 퍼즐사용자의 레벨이 1이라 했을 때, 첫 번째 퍼즐은 사용자의 레벨 >= 퍼즐의 난이도 조건에 부합함으로 시간을 3분 드려서 퍼즐을 완료한다.2번 퍼즐사용자의 레벨 퍼즐의 난이도 이다.이 경우 문제의 요구조건처럼 직전 퍼즐을 (퍼즐의 난이도 - 사용자의 레벨) 만큼 다시 풀어야 한다. 그래서 2번 퍼즐을 푸는데는 1*3+4 = 7분의 시간이 든다.3번 퍼즐이것도 마찬가지로 사용자의 레벨 퍼즐의 난이도 임으로 (퍼즐의 난이도 - 사용자의 레벨)*4 + 2 = 10분 이 든다.따라서, 사용자의 레벨이 1이면 모든 문제를 푸는데 총 20분이 소요된다.문제에서는 limit 이라는 제한시간이 주어진다.제한 시간 안에 퍼즐을 다 풀 수 있는 최소 레벨이 몇인지 구하여라2. 접근 방..