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

1. 병합 정렬은 무엇인가?병합 정렬은 (1) 세세하게 나눈다. ➜ (2) 하나씩 정복한다 의 방식으로 정렬되지 않은 일련의 데이터를 정렬시키는 방법이다.2. 원리다음 3가지 순서를 따라서 진행된다.(1) *더 이상 쪼갤 수 없을 때까지 데이터를 분리시킨다.* ( 분할 by 재귀)(2) 인접한 데이터 그룹끼리 대소관계 비교를 통해 정렬시킨다. (정복 by 투 포인터)(3) 정렬된 데이터를 다시 하나의 그룹으로 간주하고, 데이터 전체가 하나의 그룹이 될 때까지 (2)번을 반복한다.3. 예시비 정렬된 일련의 데이터를 위의 방식을 차례대로 수행하여 정렬시켜보겠다.7, 2, 4, 3, 1, 5, 6의 일련의 데이터를 오름차순으로 정렬시킨다고 가정해보자.(1) 분할 by 재귀재귀를 통해 데이터들을 더 이상 쪼갤 ..

1. 원리사전 세팅: 정렬되지 않은 1차원 배열이 주어졌고, 해당 배열을 오름차순으로 정렬함을 전제로 한다.배열의 첫 원소를 조회한다.다음 원소와 대소관계를 비교하고, 그에 따라 적절한 조치를 한다.조회중인 원소 > 다음 원소: 둘의 자리를 바꾼다.조회 중인 원소 다음 원소: 아무 조치 없이 지나간다.2번 과정을 배열 끝까지 반복한다. 이러면 정렬되지 않은 영역 최우단에 정렬되지 않은 값 중 최대값이 위치하게 된다.(즉 3번 과정 1번 당 하나의 원소가 정렬된다.)3번 과정을 배열 내의 모든 원소가 정렬될 때까지 반복한다.2. 예시위 사진과 같이 주어졌을 때, 5가 1보다 큼으로 둘의 자리를 바꾼다. 5가 3보다 큼으로 둘이 자리를 바꾼다. 5는 7보다 작음으로 자리를 바꾸지 않는다. 7이 2보다 큼으로..

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

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