1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 에라토스테네스의 체, 문자열1️⃣ N의 최대값의 2배에 해당하는 부분에 대하여 소수 전부 찾아놓기 (N의 최대값: 1,000,000이라 가능)2️⃣ 입력 받기3️⃣ 입력보다 크거나 같은 값 중 펠린드롬 (뒤집어도 같은 수)인지 확인하기.(1) 시간복잡도 분석 🕓임의의 수: $N$ (최대값: 1,000,000) 에라토스테네의 체 만들기: $O(2N \log (\log 2N))$펠린드롬 수 찾기: input에서 제일 가까운 소수 이자 펠린드롬 수를 찾는 것이므로, 시간 복잡도 따로 계산하지 않아도 될 만큼 작은 반복안에 찾음.3. 코드 소개 🔎(1) SUDO CODE0️⃣ 1에서 2,000,000까지의 영역에서 소수 전부 찾아놓기1️⃣ ..

1. 문제 설명 📌문제 링크일반적인 매개변수 탐색이나 이분 탐색 문제보다 까다로웠던 점은,1️⃣ 통나무의 자를 수 있는 위치가 정해져 있다.2️⃣ 통나무의 가장 긴 조각을 작게 만들었을 때, 제일 처음 자른 위치도 같이 출력 해라.였다. 이걸 유념하며 문제를 풀어야 한다.2. 구현 방법 🗃️KEY WORD: Parametric Search, Binary Search, Greedy Algorithm0️⃣ 통나무를 자를 수 있는 위치를 받아서 오름차순으로 정렬한다.1️⃣ 이분탐색으로 통나무의 가장 긴 조각의 최소값을 구한다. 구하는 방법은 다음과 같다.1️⃣-1) f(w) = 모든 조각난 통나무의 길이가 w 이하인가? 라는 결정문제 함수를 만든다. 이를 만족하는 f(w) 중 가장 오른쪽에 있는 f(w)의..

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 에라토스테네스의 체문제에서 주어진 영역의 최소값 A, 최대값 B, 임의의 소수 K에 대하여, $A 0️⃣ $A 가능한 K를 모두 구하기 위해, n을 2라고 치고, 양변을 모두 2의 제곱근으로 나눈다. $√A 1️⃣ 1 에라토스테네스의 체), √√B까지의 숫자를 살펴보면 될 것이다.2️⃣ 구해진 소수들을 계속 제곱하며, B보다 작을 때까지 가능한 수의 개수를 센다. 이때 우리는 Long이 아닌 Double 자료형을 사용한다. double 자료형은 지수표기법으로 값을 나타내기 때문에 정밀도는 조금 떨어질 수 있으나, Long보다 큰 값도 overflow 없이 표현 가능하다. 이번 문제가 정확한 값을 구하는 것이 아닌 대소 비교임으로 충분히 ..

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

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

1. 문제 설명 📌문제링크문제 설명이 직관적이라 설명 생략2. 접근 방식 🗃️KEY WORD: custom Sorting정렬 문제 였지만, 직접 정렬 알고리즘을 구현하는 문제는 아니었고, 정렬의 기준을 직접 제작하는 것이 중요한 문제였다. 필자는 문제를 처음부터 정렬 알고리즘 직접 구현으로 가닥을 잘못 잡고 들어가서 엄청 헤멨다. 해당 내용은 배운 것들에 더 자세히 기술 하고 여기서는 어떻게 접근해야 하는지에 초점을 맞추겠다.(1) 정렬 기준Numbers 배열의 원소 중 임의의 하나를 A, A의 다음 원소를 B라고 하자. 이 숫자들을 문자열이라 가정했을 때, 다음과 같이 이어 붙일 수 있을 것이다. AB 형태BA 형태이 두 형태 중 무엇이 큰지를 대소 관계 비교하면 된다.AB > BA , A가 앞에 ..

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차원 배열 형식으로 주어진다. 이때 수들 중 임의의 수 하나를 다른 수 두개의 합으로 나타낼 있을 때, 이 임의의 수를 좋은 수라고 한다. 이러한 좋은 수가 배열 내에 몇 개인지 구하라2. 접근 방식 🗃️Key Word: Two-way Two Pointer두 포인터의 합 > target: R 포인터를 한 칸 내려 합을 하향 조정두 포인터의 합 : L 포인터를 한 칸 올려 합을 상향 조정두 포인터의 합 == target: 답을 +1 올리고 반복문 종료(1) 시간 복잡도는? N = 2000 으로 이중 반복문까지 허용 범위이다. 따라서N개 중에 하나 Target 값으로 찾기 (O(N))두 포인터 움직이며 Target 값 만들 수 있는지 찾기 (O(N))두 움직임은 ..

1. 문제 설명 📌문제 링크문제 설명이 어려워서 부연 설명을 하겠다.N개의 울타리와 너비가 X인 룰러가 있다. 울타리의 경우 너비는 1로 고정이고, 높이만 1차원 배열 형식으로 주어진다. 당신은 룰러를 활용하여 페인트를 칠할 것인데, 너비가 X임으로, X 너비 내의 울타리는 한 번에 칠하게 될 것이다. 여기서 중요한 조건은 다음과 같다. (1) 룰러의 부분이 허공에 닿으면 안된다.왼쪽과 같이 일련의 울타리가 주어진다면, 오른쪽 그림의 테두리 안 쪽만 롤러를 돌려 칠할 수 있다는 말이다. 즉 롤러 너비 X 내에 제일 작은 울타리가 색칠의 기준이 된다. (2) 칠한데는 또 칠할 수 있다.다음과 같이 롤러의 너비가 3일 때, 처음 맞딱뜨리는 구간에서는 최대로 칠할 수 있는 높이가 1일 것이다.롤러를 한 칸 ..

1. 문제 설명 📌문제 링크용액마다 특수값이 존재두 용액을 골라서 둘의 특수 값을 합했을 때, 그 합이 0에 가장 가까운 조합을 구하여라2. 접근 방식 🗃️KEY WORD: Two way Two pointer용액의 특수값을 1차원 배열에 입력받고, 해당 배열을 오름차순으로 정렬한다.index = 0에 L 포인터, index = N-1에 R 포인터를 둔다L+R > 0 일 경우, R 포인터를 한 칸 후진 시켜서 합을 하향조정한다.L-R 일 경우, L 포인터를 한 칸 전진 시켜서 합을 상향조정한다.0에 가까운 값을 구해야함으로, 둘 사이의 합의 절대값이 최소인 경우를 찾으면 된다.(왜냐하면, 두 포인터 사이의 합의 절대값이 커질수록 0에서 멀어지기 때문이다.)(1) 단뱡항 투 포인터로 답을 구할 수 없는 ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: one-way Two pointer단방향 투 포인터를 사용하는 전형적인 문제이다. 왼쪽 포인터(L)과 오른쪽 포인터(R)을 둔다. 해당 구간 내 수들의 합을 sum이라 하겠다.sum : R 포인터를 전진시킨다.sum >= M: L 포인터를 전진시킨다. (만약 sum == M이면 답이 되는 경우의 수를 +1 올린다.)구간 내의 합은 구간 내의 값이 원소 하나인 경우도 포함한다. 따라서 arr[0] == M 인 경우도 예외 없이 계산에 포함되도록 해줘야 한다.나는 3번의 규칙을 지키기 위해 배열을 N+1로 만들어 값들을 1부터 채우고, 포인터들은 0부터 시작하도록 하였다.3. 코드 소개 🔎import java.io.*;import java..

0. 글이 흘러가는 방향먼저 개념 설명을 하고, 투 포인터를 활용하는 대표적인 문제 2개를 직접 풀어보며, 개념에 대한 보충을 하겠다.1. 개념1차원 배열에 두 개의 포인터를 두고, 두 포인터에 의미를 부여하여 문제를 푸는 기술배열 안에서 특정 조건의 값을 구하는 문제에서, 일반적으로 시간 복잡도가 O((N^{2}))가 든다면, 투 포인터 기법을 활용하면 시간 복잡도를 O(N)으로 줄일 수 있다. (이유는 활용을 살펴보며 설명하겠다.)(1) 유형투 포인터를 운용하는 유형에는 크게 2가지가 있다.a.단방향 운용L 포인터와 R 포인터가 한쪽 방향으로만 움직이는 것이다. 슬라이딩 윈도우의 양끝을 의미한다고 보면 된다. 슬라이딩 윈도우와 다른 점은 포인터에 따라 구간의 길이가 가변적이라는 것이다.b. 양방향 운..