0. 들어가며...해당 글은 ArrayList에서 원하는 숫자를 지우는 방법에 대한 글이다. ArrayList.remove() 함수로 지우면 되지 않겠냐 생각할 수 있지만 .remove(int i)를 넣으면, remove의 오버로딩된 함수 중 ArrayList.remove(int index)가 호출되어, i를 index로 가지는 Value를 ArrayList에서 삭제한다. 따라서 원래 의도한 'i라는 Value 지우기'는 실패한다.1. ArrayList.remove(int index)위에서 설명했듯이 remove에 원시 자료형 int를 넣으면 해당 인수를 index로 가지는 Value를 ArrayList에서 삭제한다.2. ArrayList.remove(Object o)우리가 실제 i라는 Value를 삭..

0. 들어가며개발을 하거나, 코딩테스트에서 정수론 관련 문제를 만나면 한 번씩 주어지는 입력의 크기가 Long형을 초월할 수 있을 때가 간혹 있다. 먼저 코테에서 자주 쓰이는 자료형인 int와 Long형의 최대, 최소값을 알아보자.정수형 타입데이터 표현 범위int-2,147,483,648 ~ 2,147,483,647 ($10^{10}$)long-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 ($10^{18}$)long이 정말 많은 수의 범위를 커버할 수 있음에도 불구하고 백준의 거의 소수같은 문제는 이러한 자료형을 뛰어넘는다. 이때의 대처법 2가지를 설명하겠다.1. 실수 자료형인 Double 사용 Double은 64bit 부동 소수점으로 표현된 자료형으로..

0. 정리하는 이유코테 문제를 풀다가 갑자기 순서가 헷갈렸다. 그래서 정리해놔야 겠다1. For 문 작동 순서1️⃣: 지역 변수 선언 및 초기화 (해당 부분이 For문 밖에 있어도 된다. 다만 그렇게 하면, for 문이 끝난 뒤에도 i 값이 유지된다.)2️⃣: 중앙의 조건 체크 (여기서 걸리면 for문 내용물에 들어가지 않고 바로 for 문이 끝난다.)3️⃣: 내용물 처리4️⃣: i 크기 올리기5️⃣: 다시 한 번 더 조건 체크

0. 무엇을 정리하나요필자는 문자열을 뒤집는 기술이 필요할 때, StringBuilder클래스의 reverse()를 자주 활용한다. 근데, 펠린드롬 수를 빠르게 구하기 위해, 다음과 같이 문제를 푸니 틀리는 것 아닌가! StringBuilder straight = new StringBuilder(num);StringBuilder reverse = new StringBuilder(num).reverse();콘솔에 찍어보니 두 객체 모두에 어떠한 입력값도 들어가지 않았다! 코테에서 이러한 에러를 겪었으면 적잖이 당황했을 것 같다. 오늘은 필자와 같이 당황할 사람들을 위해, StringBuilder의 생성자에 int i를 넣는 것과 String str을 넣는 것의 차이를 알아보려 한다.1. ne..

1. 문제 설명📌(1) 링크🔗  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr (2) 주목 포인트 🕵1️⃣ 늑대 >= 양 이면 모았던 양의 개수가 0이 된다!2️⃣ 현재 특정한 서브 트리를 방문 중이라 가정할 때, 해당 트리에서 최대 이익을 이미 냈다고 확신한다면, 조상 노드를 거슬러 올라가 다른 서브 트리를 파고 드는 것이 가능하다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: BACK-TRACKING, DFS해설에서 설명한 2️⃣번째 포인트 때문에, 이번 문제는 BACK-TRACKING에 가깝게 변형된 DFS를 사용해야 한다. 깊이 우선 탐색을 하는 성질은..

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

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