1. 문제 설명 📌문제 링크지헌과 성하의 새로운 약속 장소를 찾아주는 문제로서, 다익스트라를 통해 각자의 출발점에서 모든 정점까지의 최소 도달 비용을 구하고, 이를 통해 4가지 조건을 만족하는 약속 장소를 찾으면 된다.하지만, 출제자가 지문을 되게 모호하게 적어서, 조건의 진의가 헷갈린다.약속 장소의 조건은 다음과 같다.1️⃣ 각자의 출발점은 약속 장소가 될 수 없다.2️⃣ 둘 다 최소 비용으로 닿을 수 있는 장소여야 한다.3️⃣ 지헌이가 성하보다 먼저 도착하는 장소여야 한다.4️⃣ 위의 조건을 모두 만족하는 장소가 복수라면, 그 중 지헌이가 빨리 도착하는 장소를 고른다. (이 마저도 복수이면, 정점 번호가 빠른 것을 고른다.)이 조건을 보면,각자의 출발점이 아니면서, 지헌이가 성하보다 먼저 도착하면서..

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

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

0. 알아볼 것1. Hash Map 이란? 형태의 데이터 쌍으로 이루어진 자료구조KEY를 활용해 HashMap에 VALUE을 저장, 삭제, 조회 하는데 평균 O(1)의 시간이 든다. 쌍을 ENTRY라고 부른다.KEY 값은 중복될 수 없고, VALUE 값은 KEY 값이 다르다면 중복저장이 가능하다.2. HashMap 내부 구조HashMap은 크게 HASH 함수와 Hash Bucket으로 이루어져 있다.Hash Bucket은 값을 저장하는 장소로 Array로 구현되어 있다.Hash 함수는 자료구조에 저장될 입력 값 마다의 Hash 값을 반환한다. 해당 Hash 값은 Hash Bucket의 Index이다. 따라서 Hash 함수는 입력 값이 저장될 위치를 알려주는 방향키 역할을 한다고 생각하면 되겠다.이제 실제..

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

1. 문제 설명 📌문제 링크슬라이딩 윈도우에서 더 나아가서, 윈도우 구간안에 최소값을 매번 출력하는 문제이다.2. 접근 방식 🗃️KEY WORD: Sliding Window, Data Structure (Deque)파이썬에서는 추가시간이 주어줘서 우선순위 큐를 이용해도 풀리지만, Java에서는 풀리지 않는다. 왜 우선순위 큐로는 안되는지에 대해 4번 항목에서 설명하겠다.(1) 전체 접근 방식ArrayDeque로 슬라이딩 윈도우를 구현한다.(해당 deque는 현재 구간인 값들만 가지고 있으며, 오름차순으로 값의 순서를 유지한다. (front = 최소값))슬라이딩 윈도우를 오른쪽으로 한 칸씩 움직인다.구간에 신규로 추가될 값을 A라고 쳤을 때, A와 deque의 rear(꼬리)를 비교한다rear > A:..

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. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: SIMULATION3. 코드 소개 🔎import java.util.*;class Solution { public int solution(int[] wallet, int[] bill) { int answer = 0; Arrays.sort(wallet); Arrays.sort(bill); while(wallet[0] 4. 배운 것들 🎯없음. 꾸준함을 위한 재물

1. 문제 설명 📌문제 설명문제 설명 생략2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy 알고리즘은 매 선택의 순간에 당시 할 수 있는 최선의 선택을 하는 것이 전체 문제에서도 최적의 해를 구하는 것임을 가정하는 알고리즘이다.여기서는 미사일의 묶음을 끝지점 기준 오름 차순으로 정렬하고, 미사일 묶음의 최대한 끝지점에서 차례대로 요격해 나가면 최소한으로 요격 미사일을 사용하는 것이다. 해당 방법은 다음과 같은 이유로 유효하다.미사일을 만나면 무조건 요격해야 한다. 안하고 지나치는 경우는 없다.따라서 미사일을 만나면 최대한 겹치게 삭제해야 한다.하나의 미사일 묶음 A가 다른 미사일 묶음과 최대한 겹치는 경우는 A의 끝지점에서만 발생한다.예를 들어보겠다.다음과 같이 폭격 미사..

1. 문제 설명 📌문제 링크아날로그 시계의 초침이 시침 혹은 분침과 겹칠 때마다 알람을 울릴 건데, 주어진 시작 시간부터 끝시간 내에 알림이 몇 번 울렸는지 횟수를 반환하는 함수를 작성하는 문제. 시계의 초,분,시침은 연속적으로 움직인다. 따라서 겹치는 시기가 0.001초 단위일 수도, 0.00001초 단위일수도 있다. 이를 다 생각해서 겹치는 횟수를 구해라! (Lv2 맞나?? Lv3로 격상해야할 듯...)2. 접근 방식 🗃️KEY WORD: SIMULATION시계 침들의 겹침 현상을 최대한 코드로 구현해야 한다. 하지만 연속적으로 이루어지는 움직임 속에서 겹치는 순간을 포착한다는 것은 불가능한 일이다. 따라서 겹친다의 기준을 다음과 같이 정한다.(1) 겹친다의 기준각도 상 초침이 시침 혹은 분침보다..

1. 문제 설명 📌문제 링크회의시간의 시작과 끝이 주어질 때, 최대한 많은 강의를 회의실에 배정해라 (A 강의의 끝시간과 B 강의의 시작 시간이 같으면 연달아 배정할 수 있는 것으로 간주한다.) 2. 접근 방식 🗃️KEY WORDS: GREEDY ALGORITHMGreedy Algorithm은 선택의 순간에 최적의 선택지를 고르는 것이 전체 문제에서 최적의 선택을 하는 것이라 가정하는 알고리즘이다.빨리 끝나는 순으로 회의를 정렬제일 빨리 끝나는 회의가 A라면 A 회의 이후에 시작할 수 있으면서도, 최대한 빨리 끝나는 회의를 선택하는 것이 전체 문제에서 봤을 때 최대한 많은 강의를 고를 수 있는 방법임.2번을 모든 회의를 돌아보며 더 이상 고를 수 있는 회의가 없을 때까지 반복 3. 코드 소개 🔎..

1. 문제 설명 📌문제 링크문제에서 수열이 주어지는데, 수열은 기본적으로 모두 더해진다. 하지만 만약 사용자가 임의의 수 2개를 골라서 괄호를 쳤을 경우, 해당 수는 곱해진다. 모든 수는 단 하나의 괄호에 포함되거나 아니면 괄호에 아예 포함되지 않는 2가지 선택지밖에 없다고 했을 때, 수열로 만들 수 있는 최대값을 구하라.예를 들어 수열이 [0,1,2,4,3,5]로 주어졌을 때, 괄호가 없다면 합은 15이지만, 다음과 같이 괄호를 활용하면 0 + 1 + (2*3) + (4*5) 가 되면 값이 27로 최대가 된다.2. 접근 방식 🗃️KEYWORD: GREEDY ALGORITHM(1) 경우의 수 생각하기먼저 주어진 두 개의 수로 최대값을 만들 수 있는 경우는 무엇이 있을까?두 수 모두 0보다 클 때: 이..

1. 문제 설명 📌문제 링크설명이 직관적이라 추가 설명 생략2. 접근 방식 🗃️KEY WORD: Greedy Algorithm동전 수가 무한하기 때문에 Greedy 알고리즘을 적용하면 된다. Greedy 알고리즘은 매 순간 최적의 선택을 하는 것이다. 여기서 최적의 선택은 가능한한 큰 단위의 동전을 사용하여 동전 개수를 줄이는 것이다. 따라서 내림차순으로 동전 단위를 하나씩 훑으며, K원을 최대한 큰 단위의 동전으로 차감한다.내림차순으로 동전 조회만약 현재 조회 중인 동전으로 K원을 나눌 수 있다면? 나눈 몫만큼 동전을 사용 가능한 것임으로 몫을 답에 누적시킴K원은 (해당 동전의 단위 x 몫) 만큼 차감되었으므로, 나머지만큼만 남아있는 것이다. 따라서 K = K%단위로 갱신한다.1,2,3번을 K ==..

1. 그리디 알고리즘은 무엇인가요? 💡Greedy Algorithm은 매 선택의 순간마다 당시에 고를 수 있는 최선의 선택지를 골라가는 것이 전체에서 봤을 때 최선의 선택이라고 가정하는 알고리즘이다.예를 들어 다음과 같은 문제가 있다고 해보자.현재 A의 시점에서 고를 수 있는 선택지 중 C가 최단거리이다. 그러므로 C를 선택한다.C 시점에서 고를 수 있는 선택지 중 최단 거리로 갈 수 있는 노드는 G이다. 따라서 G를 선택한다. 두번의 선택 후 무조건 F를 비용 0으로 갈 수 있다고 할 때, 전체 노드는 다음과 같다.매 순간 갈 수 있는 최선의 선택지를 골랐더니 전체에서 봤을 때도 최선의 선택이었다. 이와 같이 매 순간의 최선 = 전체의 최선 이 성립할 때, 이러한 논리를 Greedy 알고리즘이라 한다..

1. JSON 이란 무엇인가요? 💡(1) 정의JSON이란 JavaScript Object Notation의 약자로 Javascript 객체 형태로 되어있는 데이터 교환 양식이다.JS 객체의 형태 : javascript 객체는 (key: value) 형태의 값들이 나열된 구조이다. java에서 HashMap과 유사하다고 볼 수 있다. js에서는 따로 변수에 대한 타입 선언이 필요 없기 때문에 객체 문법이 비교적 간편하다.(2) 특징a. 언어 독립적인 양식이다.분명 JS 객체 형태를 기반으로 만들어진 양식이지만, javascript 뿐만 아니라 대다수의 언어, 그 언어 기반 프레임워크에서 활용할 수 있다.b. 상태를 교환한다.JSON을 통해 주고받는 데이터란 특정 객체 혹은 값들의 상태이다. 기능을 의미하..

0. 알아볼 내용Java의 객체 직렬화에는 두 가지 종류가 있다.첫 번째로, Serializable 인터페이스를 구현한 클래스의 객체를 Byte Stream 직렬화하는 것 이다.두 번째로, RESTful API Sever를 구현할 때, 데이터 교환을 위해 객체를 JSON 직렬화하는 것 이다.두 가지의 차이점은 어렴풋이 알지만, 제대로 구분하여 기억하지 않았더니, 두 방법의 구현 방식과 활용법이 서로 뒤죽박죽 섞여 있었다. 이를 해결하기 위해 두 가지 형태의 직렬화에 대해 정확히 알아보고, 그 차이점을 구분하려 한다.여기서는 먼저 두 직렬화의 의미만 간략히 알아보고 차이점 설명에 더 집중하겠다.만약 더 자세히 알고 싶은 분은 각 항목 별 더 알아보기링크를 통해 확인하기 바란다.다음과 같은 클래스의 객체를 ..

1. 문제 설명 📌문제 링크문제 내용이 직관적이기 때문에 부가 설명은 생략하겠다.2. 접근 방식 🗃️KEY WORD: BFSoils라는 1차원 배열을 만든다. 해당 배열의 index 는 land의 열이고, value는 열 당 얻을 수 있는 석유의 양이다.land 전체에 대해서 이중 반복문으로 석유(1)이 있는 위치를 찾는다만약 석유를 찾는다면 해당 위치부터해서 연결된 석유 덩어리를 BFS로 찾는다.BFS로 해당 위치에서 시작해 석유 덩어리를 모두 찾았으면, 지금까지 거친 적 있는 열에 지금까지 찾은 석유량을 더한다.(예를 들어, 열을 1,2,3 거쳤고, 찾은 석유량이 7이면 oils[1] += 7, oils[2] += 7, oils[3] += 7 이 된다.)3. 코드 소개 🔎먼저 전체 코드를 보여주..

1. 문제 설명 📌문제 링크문제에서는 다음 3가지 단방향 그래프를 제시하고 있다.도넛형은 순환형 그래프이고, 간선의 개수와 정점의 개수가 같다.막대형은 비순환형 그래프이고, 정점의 개수 - 간선의 개수 = 1 이다.팔자형은 순환형 그래프이고, 간선의 개수 - 정점의 개수= 1 이다.이러한 3가지 유형에 해당하는 그래프가 최소 2개 이상 주어진다. 이때 주어진 모든 그래프를 잇는 정점을 하나 그린다. 우리는 이번 문제 풀이에서 해당 정점을 뿌리 정점이라 부르겠다. (문제에서 마땅히 해당 정점을 지칭하는 용어가 없어서 임의로 명명하겠다.) 뿌리 정점을 부착한 예시는 다음과 같다.이때 뿌리정점의 번호, 도넛형 그래프의 수, 막대 그래프의 수, 팔자형 그래프의 수 를 순서대로 기록한 1차원 배열을 출력하면 된..