1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 재귀, DFS해당 문제에서 실행해야 하는 작업에는 3가지로 왼쪽 자식 방문, 현 노드에 대한 처리, 오른쪽 자식 방문가 있다. 해당 문제는 '이 순서를 어떻게 할 것인가?'에 대한 기준을 세우면 쉽게 풀린다. 왜냐하면, 전위, 중위, 후위 순회는 미리 정해진 순서를 재귀적으로 반복하기 때문이다. 각 순회 별 3가지 작업에 대한 순서는 다음과 같다.1️⃣ 전위 순회: 현 노드에 대한 처리➜ 왼쪽 자식 방문 ➜ 오른쪽 자식 방문2️⃣ 중위 순회: 왼쪽 자식 방문 ➜ 현 노드에 대한 처리 ➜ 오른쪽 자식 방문3️⃣ 후위 순회: 왼쪽 자식 방문 ➜ 오른쪽 자식 방문 ➜ 현 노드에 대한 처리예를 들어 보면, 후위 순회를 진행한다고 해보자. 먼저 ..

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

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

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: Parametric Search, Binary_Search,DFS(1) 가중치 양방향 그래프를 인접리스트로 구현한다.(2) 이분탐색을 활용해, 한번에 옮길 수 있는 물건의 최대 중량을 구한다. (이분 탐색은 다음과 같이 진행 된다.)a. 문제에서 주어진 최대 중량과 최소 중량을 활용해 중앙값을 구한다.b. 해당 중앙값을 한 번에 옮길 수 있는 최대 중량이라 쳤을 때, 도착지까지 옮기는 게 가능한지 확인한다.c-1. 가능하다면 최소 중량을 현 중앙값 + 1 올려서, 다음에 구할 중앙값을 상향 조정 한다.c-2 .불가능하다..

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(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. 문제 설명 📌문제 링크한 개 이상의 일이 존재하고, 일마다 시작시간, 끝시간, 완료했을 때 이익 이 주어질 때, 주어진 일련의 일들에서 나올 수 있는 최대 이익을 반환하라.조건선택한 일들은 서로 일의 진행 시간이 겹치면 안된다.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: QUICK SORTING사실 JAVA 내부 라이브러리에 있는 Sorting을 쓰면 간단히 해결되는 문제이지만, Qucik Sorting 연습을 위해 Quick Sorting을 사용해 보았다. quick sorting의 경우, 최악의 시간 복잡도가 O( $N^2$ )이라서 문제에 제시된 최대 데이터 량을 보면, 시간초과가 나야 하는 것이 맞다. (아마 Quick Sorting을 쓰면 시간 초과가 나는 테스트 케이스를 안 넣어놓은 것 같다.)(1) 큰 흐름(1) 현재 정렬해야 하는 영역의 중앙값을 PIVOT으로 선정(2) PIVOT을 영역 최좌단 값과 자리 교체. (pivot은 비교 대상에 속하지 않도록 하기 위함.)(3) PIVOT을 제외..

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

1. Quick 정렬은 무엇인가?Pivot(중추)가 되는 값을 하나 선정해서 그 값보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 모은다. 이제 나눠진 두 그룹 내에서 다시 Pivot을 선정하고 이 과정을 반복한다. 값을 더 이상 쪼갤 수 없을 때까지 반복하면 모든 값이 정렬되어 있다.2. 원리병합정렬과 마찬가지로 분할 정복을 활용하는 또 다른 예시이다. 병합 정렬에서는 선 분할 후 정복 이었다면, quick 정렬은 선 정복, 후 분할 형식이라 생각하면 되겠다.정복에는 마주보는 투 포인터가 활용된다. 어떻게 쓰이는지는 밑의 예시에서 자세히 설명하겠다. (1) Pivot 정하기 (정하는 방식은 때에 맞게 자유)(2) Pivot보다 큰 값은 오른쪽으로 몰기, 작거나 같은 값은 왼쪽으로 몰기 (정복 by 투 포..

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. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: 누적 합, 이분 탐색동굴의 높이인 H와 깊이인 N이 각각 \(10^{5}\)이므로, 완전 탐색으로 하나의 행마다 모든 열을 조회한다면 1초에 \(10^{10}\)번 이상의 연산을 해야해서 시간 초과가 날 것이다.해당 문제는 *거꾸로 매달려 있는 종유석을 어떻게 처리할 것인가?* 에 대한 명확한 가이드라인만 계획할 수 있다면 풀 수 있는 문제이다. 종유석 처리방법에 따라 두 가지 방법으로 풀 수 있는데, 하나는 누적 합이고 다른 하나는 이분 탐색이다.(1) 누적합a. 결론 먼저1. "석순과 종유석 입력을 분류하여 Y축 위치에 따른 각 산물의 위치를 저장하는 배열 구현"2. "각 배열의 누적합 구하기 (석순 누적합 배열을 sum_S[i], ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: 구간 합누적합 배열 S에서 A~B 구간 내의 구간합을 구할 경우 어떻게 표현했는가?S[B] - S[A-1] 이였다. A가 구간내에 합해지도록 A-1까지의 구간합을 제거했다. 이러한 원리는 구간 내에 알파벳이 몇 번 등장하는가 찾는 이번 문제에서도 사용할 수 있다.위 그림과 같이, a가 A구간에서 한번, B구간에서 한번 나온다고 하자. 그러면, S[A] = 1, S[B] = 2가 될 것이다. 구간을 확인하면 문자열이 A의 위치를 넘어서서 B까지 구간을 정하는 순간 a는 한개이다. S[B]-S[A]는 A+1 ~ B까지의 구간합임으로 2-1 = 1이 나온다. 반면 S[B] - S[A-1]은 A의 위치부터 B까지의 거리에서 a의 개수임으로 S[..

1. 문제 설명 📌문제 링크f(n) = n이란 숫자의 약수들의 합g(n) = 1~n까지 각 숫자의 약수들의 합 즉 f(1) ~ f(n)의 합2. 접근 방식 🗃️KEY WORD: 누적 합, 시간 복잡도에 대한 감f(n)을 구한다. (1~ 1000000 까지 전체 수에 대해 구한다.)모든 f(n) 배열을 1로 초기화 (1은 무조건 약수에 포함되므로)f(ij) += i(i = 2 ~ 1000000까지 모두 순회, j = 1부터 1씩 증가함. 즉 `ij=i의 배수를 나타냄.`)g(n)은 f(n)의 누적으로 구한다.답을 출력한다.f(i*j) = i를 진행하면, i의 배수에는 i를 무조건 더하고 i가 1~ 1000000까지 모든 수를 순회하기 때문에 각 숫자마다 자신의 약수를 빠짐없이 더할 수 있다. 여기서 다..