본문 바로가기
반응형

sort10

백준 2628 종이자르기 Kotlin (정렬) 문제 출처 : https://www.acmicpc.net/problem/2628 2628번: 종이자르기 아래 과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선 www.acmicpc.net 문제 아래 과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번.. 2022. 9. 29.
백준 13164 행복 유치원 Kotlin (그리디) 문제 출처 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 문제 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장.. 2022. 7. 23.
백준 18870 좌표 압축 Kotlin (정렬) 문제 출처 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N.. 2021. 12. 23.
[Kotlin/Java] Kotlin/java의 sort 동작 방식 (2022.10.18 수정) 환경 : Kotlin Version = 1.5.20, Java version = 14.0.2 JVM, Android Studio Kotlin/Java의 sort 동작 방식 알아보기 0. 결론 글이 길어져서 결론부터 말하자면, 코틀린과 자바에서 Arrays.sort는 Dual-Pivot QuickSort Collections.sort는 TimSort 를 사용한다. 실제로는 Counting Sort, Merge Sort 등등의 정렬을 휴리스틱한 방법으로, 적재적소에 사용한다. Dual-Pivot QuickSort = Quick Sort Best : O(NlogN) average : O(NlogN) worst : O(N^2) TimSort = Insertion Sort + Merge Sort, 시간 복잡도는 .. 2021. 12. 18.
[알고리즘] 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort)이란? 앞(왼쪽)의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 삽입 정렬(Insertion Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중에 난이도가 쉬운 편이다. 3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. 4. 손 안의 카드를 정렬하는 방법과 유사하다. 5. 시간 복잡도는 Best : O(N), Avg : O.. 2021. 7. 18.
[알고리즘] 버블 정렬 (Bubble Sort) 버블 정렬(Bubble Sort)이란? 서로 인접한 두 원소를 검사하여 더 작거나 큰 값을 반복적으로 앞으로 보내는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 버블 정렬(Bubble Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중 구현 방법이 가장 간단하다. 3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. 4. 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(N^2)이며 모든 정렬 중에 가장 비효율적인 정렬 .. 2021. 7. 18.
프로그래머스 실패율 c++ (해시,정렬) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 문제 설명 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라.. 2021. 6. 23.
프로그래머스 베스트앨범 c++ (해시) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 .. 2021. 5. 30.
프로그래머스 H-Index c++ (정렬) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면.. 2021. 5. 13.
반응형

티스토리툴바