# sorting
LeetCode - 1913. Maximum Product Difference Between Two Pairs
Solution Explanation > 굉장히 간단한 문제였다. sort 메소드를 이용해서 오름차순으로 정렬한 후 마지막 두 요소의 곱에서 처음 두 요소의 곱을 빼면 끝이다. (음수가 포함되지 않는 배열이라서 쉬웠다.)
LeetCode - 2037. Minimum Number of Moves to Seat Everyone
Solution Explanation > 문제의 요구사항이 처음에는 다소 헷갈리고 복잡할 수 있는데 조금 고민해보면 생각보다 간단하단 걸 알 수 있다. 간략하게 표현하면 한 배열(seats나 students)을 다른 한 배열과 일치하도록 만드는 데 최소한 몇 번의 움직임이 필요하냐이다. 즉, 두 배열을 비교하는 문제이다. 최솟값을 구하기 위해서 둘 다 오름차순으로 정렬한다. reduce 메소드를 이용해서 같은 인덱스에서의 움직임(두 배열의 요소의 차)를 계산하고 누적시킨다.
LeetCode - 1859. Sorting the Sentence
Solution Explanation > 뒤죽박죽인 단어들을 올바른 순서로 정렬하는 문제이다. 각 단어에는 올바른 순서가 적혀있다. 정렬을 하기위해서 split 메소드를 사용해서 띄어쓰기를 기준으로 분리한다. sort 메소드를 이용해서 올바른 순서로 정렬한다. 숫자 순서대로 정렬을 해야하기때문에 (a, b) => a - b형태로 compareFunction를 작성해야한다. map과 slice를 이용해서 맨 뒤에 숫자를 제거한다. join 메소드를 사용해서 문자열로 전환한다.
LeetCode - 1859. Sorting the Sentence
Solution Explanation > 뒤죽박죽인 단어들을 정렬해서 올바른 문장으로 만드는 문제이다. 각 단어에는 올바른 순서가 적혀있다. 정렬을 하기위해 split 메소드를 이용해서 띄어쓰기를 기준으로 분리한다. sort 메소드를 사용해서 올바른 순서로 정렬한다. 여기서 숫자 순서대로 정렬을 해야하기 때문에 (a, b) => a - b형태로 compareFunction를 작성한다. map과 slice를 이용해서 맨 뒤 숫자를 제거한다. join을 이용해서 띄어쓰기를 사이에 넣고 문자열로 전환하다.

BoJ 6177 - Statistics [with Python / 문제 한국어로 번역]
📍문제 문제 소들이 초등 통계학과에 입학했습니다. 그리고 그 소들은 지금 통계학 과제를 하면서 어려움을 겪고 있습니다! 여러분들이 도와주세요. $N$(1 <= N <= 500)개의 숫자 집합 $Xi$ (-5,000 <= $Xi$ <= 5,000)이 주어졌을 때, 두 가지 통계치를 계산 해주세요. 평균 (숫자들의 합을 $N$으로 나눈 값) 중간값 ($N$이 홀수일 경우, $N$개의 숫자를 정렬했을 때 중간에 위치한 숫자. 만약 $N$이 짝수일 경우에는, $N$개의 숫자를 정렬했을 때 중간 두 숫자의 평균값을 의미.) 두 통계치 모두 공식 답변과의 차이가 0.002 이내라면 답으로 인정합니다. 입력 총 두 개의 줄에 걸쳐 입력을 받습니다. 첫 번째 줄

LeetCode - 2160. Minimum Sum of Four Digit Number After Splitting Digits
Solution Explanation > 일단 Number 타입인 num의 각 자릿수를 분리하기 위해서 String으로 변환하였다. 그리고 각 자릿수를 요소로 갖는 배열로 전환한 후 map를 이용해 다시 Number 타입으로 변환 후 오름차순으로 정렬하였다. 이 상황에서 문제의 태그로 적혀있는 Greedy 알고리즘이 필요한 것 같다. Greedy Algorithm(탐욕 알고리즘)이란 간단하게 설명하면 >> 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역

LeetCode - 1365. How Many Numbers Are Smaller Than the Current Number
Solution Explanation > 이 문제는 nums[i]보다 작은 요소들의 개수를 카운팅하는 문제이다. 필자의 접근법은 nums를 오름차순으로 정렬한 새로운 배열을 생성한다. 이 경우 정렬된 배열의 인덱스는 해당 인덱스의 요소보다 작은 요소들의 개수가 된다. 예를 들어 위의 예제에서 sorted[3]과 같이 동일한 값은 indexOf 메소드로 처리 가능하다. indexOf 메소드 사용시 검색 범위를 지정해주지않으면 최소 인덱스값을 리턴하기때문이다. nums에 map 메소드를 사용해서 정렬된 배열의 인덱스 값으로 매핑해주면된다.

LeetCode - 2824. Count Pairs Whose Sum is Less than Target
Solution Explanation > 이중 for문을 이용해서 해결했다. 0 <= i < j < n nums[i] + nums[j] < target 위의 두 조건을 만족해야한다. 첫 번째 for문을 이용해 요소에 접근한다. 그리고 두 번째 for문의 초기식(let j=i+1)를 통해 첫 번째 조건을 자연스럽게 만족하게된다. 그리고 두 번째 조건이 만족할 경우 count를 1씩 증가시킨다.

BoJ 7530 - stamp [with Python / 문제 한국어로 번역]
📍 문제 문제 레이몬드는 지구상에서 가장 큰 우표 수집가이며, 우표 수집가 파티에서 다른 모든 사람을 놀려대곤 합니다. 그래서 모두가 레이몬드를 좋아하지 않아요. 그러나 우표 수집가인 루시는 모두에게 사랑받고 있습니다. 그리고 그녀는 아래와 같은 한 가지 계획을 가지고 있습니다. 루시는 비밀리에 친구들에게 우표를 빌려 레이몬드보다 더 큰 컬렉션을 보여주어 파티에서 그를 창피하게 만들고자 합니다! 레이몬드는 자신이 제일 많이 우표를 많이 가지고 있다는 것을 확신하기 때문에 항상 얼마나 많은 우표를 보여줄 것인지 다 알려줍니다. 그리고 루시 역시 자신이 어느정도의 우표를 가지고 있는지 알기 때문에 얼마나 더 필요한지도 압니다. 그녀는 또한 친구들 중 몇 명이 우표를 빌려줄 수 있는지와 각각이 얼마나 빌려줄 수 있는지도 알고 있습니다. 그러나 그녀는 가능한 적은 수의 친구로부터 빌리고 싶으며, 너무 많이 필요하면 아예 빌리지 않기를 원합니다. 루시에

BoJ 3211 - kino [with Python / 문제 한국어로 번역]
📍 문제 (원문은 영어여서 어색한... 한국어로 번역했어요222 ) 영잘알들을 위한 원문 문제 미르코는 자신의 생일을 축하하고자, 친구들을 영화관에 초대하고 싶어합니다. 그의 친구들은 모두 큰 규모의 그룹으로 영화관에 가는 것을 좋아합니다. 그래서 그들은 마르코와 자신(친구 본인)을 제외한 특정 수의 미르코 친구들이 함께 영화관으로 함께 가고 싶다며 마르코에게 요청합니다. 하지만, 미르코는 모두를 초대할 돈이 충분하지 않습니다. 그래서 가능한 최소한의 인원을 초대하려고 합니다. 그는 친구들 각각의 요청을 충족할 수 있는 최소한의 그룹 규모를 결정해야 합니다! 이 그룹은 적어도 한 명 이상의 사람으로 구성되어야 합니다. 미르코가 이 그룹의 규모를 결정하는 데 도움을 주세요. 입력 첫 번째 행에는 친구들의 수를 뜻하는 정수 N이 있으며, 그 범위는 2 ≤ N ≤

LeetCode - 215. Kth Largest Element in an Array
Problem 정수 배열 nums와 정수 k가 주어질때, k번째로 큰 요소를 리턴하라. k번째로 큰 요소이다. k번째 요소가 아니다. Example 1 Example 2 Solution Explanation > 일단 nums배열을 sort메소드를 사용해서 내림차순으로 정렬하였다. 그리고 k번째로 큰 수 이기 때문에 인덱스는 k-1이다. k-1로 접근해야한다. sort메소드를 사용하지 않고 해결하는 방법은 여러 정렬 알고리즘을 공부해본 후 시도해봐야겠다. 아직 정렬 알고리즘 학습이 많이 부족하다.
[BOJ-#1141] 접두사
문제 문제 링크 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다. 단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오. 입력 첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다. 출력 첫째 줄에 문제의 정답을 출력한다. Code [Github 링크](https://github.com/sinji21
[BOJ-#1092] 배
문제 문제 링크 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의

[BOJ-#10989] 수 정렬하기 3
진짜 짜증... 누가 이거 브론즈1이라고 했냐? 솔직히 이 정도는 내 자존감을 위해서 실버 주자... 문제 문제 링크 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. Code [Github 링크](https://github.com/sinji2102/boj-python/tree/main/%EB%B0%B1%
[Java] 백준 10814번 : 나이순 정렬
문제 해결 방법 시간제한 3초라서 selection sort로 index 비교하며 정렬해주었는데, 시간 초과 뜸.. 그래서 나이 입력조건이 1~200 인것을 확인하고, 내가 싫어하는 Counting sort를 적용하여 해결하였다 ! Counting sort가 뭔데 ? 범위 만큼의 배열을 선언하여 그 값에 해당하는 index를 1씩 증가시키며 저장하고 index의 값만큼 반복하여 출력하는 sorting 기법이다. 메모리를 범위만큼 할당받아야 하기 때문에, 범위가 좁은 경우에만 사용 가능하며, O(n)의 시간 복잡도를 가진다 ~ Input의 개수가 많고 범위가 좁은 곳에 사용하기 적합하다 ! ex) 1억개의 input, 범위는 [-100, 100] 을 정렬해보자 201 크기의

[Spring] 페이징 및 정렬
Spring Data JPA에서 페이징 및 정렬 기능을 제공하기 때문에 손쉽게 페이징, 정렬을 구현할 수 있다. Sort: 정렬 인터페이스 Pageable: 손쉽게 페이징, 정렬 처리를 하기위해 제공되는 인터페이스(Sort 포함) PageRequest: Pageable 인터페이스의 구현체 Page: count 쿼리 결과 포함 Client에 전달해야할 데이터인 totalPages, totalElements등의 데이터를 함께 포함 PageRequest.of(page, size, sort) page : 현재 페이지(0부터 시작) size : 데이터 노출 개수 sort : 정렬 방법(ASC/DESC) Pageable 구현체인 PageRequest 반환 productRepository.findAllByUser(user, pageable) Spring Data JPA의 Query Met

Techit 8th 4th
Sorting Bubble Sort Bubble Sort는 인접한 두 자료를 비교하며 자리를 교환하는 방식이다. 첫 번째 원소와 두 번째 원소를 비교해 첫 번째 원소가 두 번째 원소보다 크다면, 둘의 자리를 교환한다. 두 번째 원소와 세 번째 원소도 동일하게 비교하고 교환한다. 이를 마지막 두 원소까지 반복하는 것이다. 위 과정이 한 번 진행되면, 제일 큰 원소가 정렬이 끝난다. 이후 위 과정을 정렬이 안 된 원소가 없을 때까지 반복하는 것이다. 즉, 가장 큰 원소가 거품처럼 밀려오는 방식이다. | 36 | 12 | 18 | 15 | 41 | 19 | | --- | --- | --- | --- | --- | --- | | 12 | 36 | 18 | 15 | 41 | 19 | | --- | --- | --- | --- | --- | --- | | 12 | 18 | 36 | 15 | 41 | 19 | | --- | --- | --- | --- | --- |
카운팅 정렬(Counting Sort)
개요 정수 정렬 알고리즘 : 정수 key에 따라 객체를 수집하는 것 정수의 개수를 세는 방식으로 동작 특징 시간복잡도 : $O(n + k)$ ($k$ is the range of non-neg key values) 공간복잡도 : $O(n + k)$ 정수의 범위가 제한적일 때 가장 효율적으로 작동한다. 구현

선택 정렬(Selection Sort)
앞에서부터 범위를 줄여가며(i:0 ~ len-1, j:i+1 ~ len) 최소값과 자리를 바꿔가는 정렬 알고리즘 제자리 정렬(충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘) 설명 주어진 리스트 중 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 시간복잡도 : $O(n^2)$, 공간복잡도 : $O(1)$ 예시 [6, 1, 9, 2, 4, 7, 3]을 오름차순으로 sorting하려고 한다. >i = 0, 인덱스 1부터 arr.length - 1까지의 범위에서 최솟값을 찾는다. i = 0, minIdx = 1, 인덱스 0와 1를 swapping한다. → arr : [1, 6, 9, 2,

버블 정렬(Bubble Sorting)
원소의 이동이 거품이 수면으로 올라오는 듯한 모습 알고리즘 기본적으로 배열의 두 수를 선택한 뒤, 1-1. 그 수가 정렬되었다면 pass 1-2. 그렇지 않다면 두 수를 바꾸는 방식 시간복잡도 : $O(n^2)$ 설명 다음과 같은 배열을 오름차순으로 배열하려고 한다. int[] arr = {6, 1, 9, 2, 4, 7, 3}; 처음부터 맨 끝까지를 범위로 잡고, 앞에서부터 두 원소씩 비교해가며 위치를 옮긴다. 처음부터 맨 끝에서 두번째 까지를 범위로 잡고, 앞에서부터 두 원소씩 비교해가며 위치를 옮긴다. 이를 반복한다. > I. i = 6 j = 0, 1 > 6이므로 두 수를 바꾼다. → [1, 6, 9, 2, 4, 7,