1. 슬라이딩 단조 큐란 무엇인가요?슬라이딩 단조 큐란, DECK을 활용해 구현한 슬라이딩 윈도우로, 슬라이딩 윈도우 구간 내의 최소값, 최대값을 O(1)에 찾기 위해 고안한 구현체이다. 단조라는 이름이 붙은 이유는, 구간 내 최소값을 찾고 싶을 경우, Deck 내부 원소들이 오름차순으로 유지되고, 구간 내 최대값이 찾고 싶은 경우 내림차순으로 유지되기 때문이다.사실 내가 만든 이름이다...😂슬라이딩 윈도우 심화 문제를 풀면서, 슬라이딩 윈도우를 Deck으로 구현한 형태가 꾸준히 나오는데, 인터넷 여기 저기 찾아봐도, 형태만 있을 뿐 이것의 제대로 된 이름이 없었다.따라서 정식 명칭은 아니지만! 설명의 편의를 위해 앞으로 현 구간 내의 최소값과 최대값을 찾기 위해 Deck으로 구현한 슬라이딩 윈도우를 ..

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. 문제 설명문제 링크서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다. 2. 접근 방식인접 리스트 형태로, 노드와 연결 정보를 저장한다. 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다. 따라서 BFS를 돈 횟수만큼 군집체가 존재하는 것이므로, BFS를 실행한 횟수를 반환하면 된다.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int n, int[][] computers) { ..

1. 문제 설명문제 링크(1) 일거리의 시작 시간, 끝 시간, 일을 끝냈을 때의 이익 이 주어진다.(2) 시작 시간과 끝 시간의 범위가 겹치는 일은 같이 하지 못한다. 반면 어떤 일이 끝나자마자 다른 일은 시작할 수 있다.예를 들어, job A의 끝 시간이 3시 이고 job B의 시작시간이 3시이면 두 일 거리는 연달아 할 수 있다. 반면 job C가 3~5시이고 job D가 4~6시이면 두 일은 일의 시간 범위가 겹치므로 같이하지 못한다.(3) 이때, 겹치지 않게 일을 해서, 최대 이익을 얻으려고 한다. 주어진 일거리들 중에서 가질 수 있는 최대 이익은 몇인가?2. 접근 방식KEY WORD: DP(1) 주어진 문제가 시작시간, 끝시간, 이익을 따로 따로 주기에 이를 하나의 일(job) 단위로 하나로 묶..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: DATA STRUCTURE(0) 현재 조회 중인 수를 value, 출력해야 하는 수를 now라고 해보자.(1) value (2) stack의 top과 now를 비교한다.(3) top이 크면 어떤 방법을 써도 수열을 만들 수 없다. NO를 출력하자.(왜냐하면, 수열은 무조건 stack에서 pop되는 값으로 만들어야 하기 때문이다. stack에는 오름차순으로 값이 저장되기에, 현 stack의 top 값이 크다고 새로 push를 받으면 더 큰 값밖에 들어오지 않는다. stack의 top이 now보다 작을 때는 같은 값이 들어올 때까지 기다리면 되는 것과 상반된다.)(4) top == now 이면 stack에서 pop해서 값을 뺀다.Stack은 진짜 sta..

1. 문제 설명문제 링크(1) 오늘이 몇년, 몇월, 며칠인지 알려주고, 개인정보의 유형별로 정보 보관 기간을 알려준다. (2) String 배열 형태로, 정보가 수집된 날짜, 개인정보의 유형이 주어질 때, 주어진 배열에서 오늘 파기될 정보가 무엇인지, 번호를 배열 형태로 반환하라. 2. 접근 방식KEY WORD: 문자열 자르기해당 문제의 입력은 다음과 같이 주어진다. todaytermsprivaciesresult"2022.05.19"["A 6", "B 12", "C 3"]["2021.05.02 A", "2021.07.01 B", "2022.02.19 C", "2022.02.20 C"][1, 3]"2020.01.01"["Z 3", "D 5"]["2019.01.01 D", "2019.11.15 Z", "2..

1. 문제 설명문제 링크 2. 접근 방식KEY WORD: BFS생각 해야할 점: 하나의 정점이 자신의 위치를 안다는 것은 단방향 그래프에서 해당 정짐이 다른 모든 정점들과 서열를 가진다는 것이다. 이 때, 해당 서열은 간접적으로 파악이 되도 된다.간접적으로 파악된다는 것은 무슨 뜻인가?해당 그림은, 문제에서 예시로 주어진, 정점들간의 관계이다. 문제에서는 2번이 1,4,3번에게 패하고, 5번에게 이겼음으로 4등이라고 했다. 5번은 그 2번에게 졌음으로, 1,3,4번에게도 간접적으로 진 것이다. 따라서 2, 5번은 모든 정점에 대해서 서열을 가진다.(1) 단 방향 그래프를 두 개 만들기첫 번째 방법은 단 방향 그래프 2개 만들기 이다.우리의 핵심은, 현재 조회 중인 정점이 간접적으로라도, 모든 정점과 서열..

1. 문제 설명2. 접근 방식KEY WORD: BFS, IDEA해당 문제는 문제를 풀기 위한 IDEA만 생각해낸다면 간단한 BFS 문제이다. 문제에 대한 접근 방식은 다음과 같다.(1) 입력받은 좌표의 변두리 부분도 페인트를 칠할 수 있다. 가령파란색으로 칠한 부분을 봐라. 만약 입력 좌표 그대로 2차원 배열을 만든다면, 해당 변두리 부분은 배열을 벗어나게 되어, 페인트를 칠할 때 골치가 아파진다. (자칫 잘못하면 OutOfArrayIndex 에러가 나기 때문이다!!)따라서 우리는 해당 좌표도 배열 내에서 받을 수 있도록 2차원 배열을 테두리까지 넉넉하게 만들고, 여기에 입력받은 좌표값들을 집어넣는다.int [][] map = new int [row+2][col+2]그러면 이렇게 받을 수 있다. 파란색으..

1. 문제 설명문제 설명2. 접근 방식KEY WORD : BACK-TRACKING(0) 사전 세팅1차원 배열(arr)을 n의 크기만큼 만들고 배열의 index = 행 , 배열의 value = 열로 생각한다.예를 들어 배열이 다음과 같을 때, 그림으로 나타내면 이렇게 된다.index(행)0123value(열)1302(1) 만약에 arr[i] = j 라고 한다면 2차원 배열 [i] [j] 에 퀸을 두겠다는 소리이다. 이게 가능한지 체크한다. 체크하는 방법은0 ~ i-1 까지의 배열 값을 이용해, 이전에 놔둔 퀸의 공격 경로와 겹치는지 확인하면 된다. 확인법은 다음과 같다.(1-1) 좌하단 확인대각선이 일치하는 값들은 모두 행+열의 합이 같다. 이를 이용한다. 우리의 경우는 index가 행이고 value가 열..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: 브루트 포스(1) 문자열로 받은 숫자를 한 자릿수가 되게 나누어서 배열에 저장한다.(2) 전체 숫자가 n개라면 그 중 k개를 뽑아서 나열한다. (순열, k = 1 ~ n )(3) 나열된 k개의 수를 합쳐서 하나의 숫자로 만들고, 소수 판별한다. (소수 판별법 이용)(4) 소수 판별이 확정되면 해당 수가 이전에 나왔는지, hashSet으로 체크한다. 없으면, 소수의 개수를 +1 올린다.  ※추신※(1)나는 한자리 수를 합치는 것을 원래의 수 * 10 + 새로 들어온 한 자리 수로 그때 그때 바로 했다.(2)소수 판별법을 모른다면, 정리 잘 한 사람 링크를 보고 오기 바란다. 해당 링크에서는 왜 n의 제곱근까지만 나눠서 확인하면 되는지 나와있다.(3)소..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: 이분 탐색무엇을 기준 으로 이분탐색을 해야할까?이분 탐색 문제를 풀 때, 제일 어려운 부분이다. 어려운 문제일수록 무엇을 기준으로 이분 탐색을 해야할지 감이 서지 않는다. 나 또한 그랬다. 그래서 다른 사람의 풀이 아이디어까지 봤다. 분명 1년 전에 같은 문제를 백준으로 풀었는데, 안 떠올라서 좀 좌절 했다 ㅜ(1) 기준 : M 시간 당 각 심사대에서 처리하는 사람의 수내 기준에서 어려웠던 점은 규칙 - 심사대가 비더라도, 사람은 다른 심사대가 빌 때까지 기다렸다가 들어갈 수 있다. 였다. 이 자율성 때문에, 문제의 유형을 생각하지 못한 것 같다. 하지만 기억해야할 점은, 무엇을 이분 탐색 해야할지 모르겠을 때는, 반환하는 답을 기준으로 탐색할 것이..

1. 문제 설명문제 링크2. 접근 방식이건 뭐 Priority Queue 쓸 줄 아냐고 묻는 문제였다.PQ를 만든다. (default로 오름차순 정렬이니 건들일 것이 없다.)문제에서 제공하는 Order에 따른다. (0이면 출력, 나머지면 저장)3. 코드 분석import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PriorityQueue pq = new PriorityQueue(); ..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: Sorting, HashMap음악 객체를 만든다. ( 멤버 변수: 자신의 고유번호, 장르, 플레이 횟수 )입력 값들을 전부 음악 객체로 바꿔서 ArrayList에 추가한다.HashMap을 만든다. Key = 장르 , value = 장르에 해당하는 곡들의 플레이 총합2번에서 만든 ArrayList를 정렬한다. 정렬 기준은 문제 그대로다. -> Comparator를 단순화한 Lamda 식을 이용해 구현답변용 ansList를 만들고, 답변에 장르별로 몇 번 들어갔는지를 나타내는 genreAddedCount라는 HashMap도 하나 더 만든다.genreAddedCount는 Key = 장르, value = 장르 별로 답변 List에 나온 횟수 이다. .get..