# Counting Sort

rlwjd31

🍀 H-Index 요새 느끼는 건데 내가 문장 이해력이 부족한가 싶다 ㅜㅜ🤣 하지만, 그래도 이런 저런 시행착오를 겪으면서 문제를 이해하여 풀었다. 내가 여기서 가장 문제를 겪었던 부분은 배열 안에 존재하는 요소 즉, 인용된 횟수가 꼭 H-Index가 아니라는 점이다. 예를 들어 ` citations = [3, 0, 6, 1, 5, 5, 5]일 때 H-Index는 4`가 답이다. H-Index가 4일 때 4회이상 인용된 횟수는 4이며 4이하 인용된 횟수는 3으로 3 를 만족하기 때문이다. > less: H-Index 이하 인용된 횟수, more: H-Index 이상 인용된 횟수라 가정하면 > H

sezznb

문제 해결 방법 시간제한 3초라서 selection sort로 index 비교하며 정렬해주었는데, 시간 초과 뜸.. 그래서 나이 입력조건이 1~200 인것을 확인하고, 내가 싫어하는 Counting sort를 적용하여 해결하였다 ! Counting sort가 뭔데 ? 범위 만큼의 배열을 선언하여 그 값에 해당하는 index를 1씩 증가시키며 저장하고 index의 값만큼 반복하여 출력하는 sorting 기법이다. 메모리를 범위만큼 할당받아야 하기 때문에, 범위가 좁은 경우에만 사용 가능하며, O(n)의 시간 복잡도를 가진다 ~ Input의 개수가 많고 범위가 좁은 곳에 사용하기 적합하다 ! ex) 1억개의 input, 범위는 [-100, 100] 을 정렬해보자 201 크기의

z2236519

1. 버블 정렬 (Bubble Sort) 👉 인접한 두 자료를 비교하며 자리를 교환하는 방식 >### 📌 방법 첫번째 원소와 두번째 원소를 비교 정렬 두번째 원소와 세번째 원소를 비교 정렬 n-1번째 원소와 n번째 원소를 비교 정렬 한번의 정렬 사이클이 끝나면 가장 큰 원소(제일 오른쪽 원소)의 정렬이 끝남 따라서 두번째 정렬 사이클은 n-1번만 시행 ✨ 버블 정렬 코드 🚧 결과 2. 선택 정렬 (Selection Sort) 👉 주어진 자료 중 제일 작은 숫자를 골라서 앞으로 정렬하는 방식 >### 📌 방법 자료 전체를 확인해 제일 작은 값을 찾아, 제일 앞의 원소와 교환한다. 이 과 정이 끝나면 제일 앞의 원소는 정렬이 끝남 이후 정렬되지 않은 원소들을 기준으로 같은 작업을 정렬이 안된 원소가 없 을 때까지 반복 ❗버블 정렬과의 차이점 🔸 버블 정렬은 5번의 비교 중 4번

calis_ws

계수 정렬(Counting sort) 각 자료가 몇 개가 존재하는지 정리한 뒤 그 정보를 활용해 정렬하는 방식 먼저 자료들의 값의 범위 만큼의 공간을 가진 counts 배열을 만든다. (자료가 0 ~ 9 사이라면, int[] counts = new int[10];) 자료의 각 데이터(data)를 확인하여, counts[data] 의 값을 하나 더해준다. 이 과정이 끝나면 counts[data] 에는 data가 몇개인지가 저장된다. 첫번째 원소부터 시작하여 counts 배열의 앞쪽 원소의 값을 뒤에 합해준다. 이후 본래의 자료 데이터(data)를 순회하여, counts 배열에 따라 결과를 정리한다 lotto Controller 6가지의 랜덤한 수를 보여주는 기능

minsang

이코테 복습 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조 Overflow: 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입시 발생 Underflow: 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행시 발생 Stack 선입후출 구조 (First In Last Out) Push(append), Pop(pop) Queue 선입선출 구조 (First In First Out) Push(append), Pop(popleft) 그래프 인접 행렬 (Adjacency Matrix) 인접 리스트 (Adjacency List) 재귀함수 자기 자신을 다시 호출하는 함수(Recursive Function) 종료 조건을 꼭 명시해야 한다 DFS/BFS DFS 깊이 우선 탐색 (Depth First Search) 재귀 함수를 사용 (Stack) BFS 너비 우선 탐색 (Br

guiltycoding

숫자짝궁 풀이 인덱싱을 이용해 풀면 시간초과가 뜨지 않는다. 값의 범위가 0 ~ 9까지 밖에 없으므로 계수 정렬을 사용해도 공간 복잡도가 높지 않다. 각각의, 인덱싱을 담당하는 int 배열을 선언하여 관리하도록 한다. 코드

mathe1303

코딩을 하다보면 데이터를 정렬할 필요가 있는데 정렬 하는 방법도 다양하기에 상황에 따라 적합한 정렬법을 적용해야 정렬한 데이터를 활용 할 때의 시간도 줄어든다. 정렬하는 방법은 다양하지만 이 게시글에서는 다음의 7가지의 정렬 알고리즘을 가볍게 훑고 지날 갈것이다. 7가지 정렬 알고리즘 선택 정렬 버블 정렬 삽입 정렬 퀵 정렬 병합 정렬 힙 정렬 계수 정렬 ✍ 선택 정렬 (Selection Sort) 선택 정렬의 경우 가장 흔한 정렬 중 하나로, 목록에서 최소 요소를 찾아 첫 번째 요소로 교체하는 것으로 시작하는 알고리즘으로 숫자 데이터 타입으로 차 있는 배열을 오름차순으로 정렬하기와 같은 예가 있다. 배열의 길이 만큼 반복을 하기 때문에 `시간 복

junghojune

Counting Sort(계수 정렬/ 카운팅 정렬) 시간 복잡도 : 𝚶(𝑛) 빠르다는 정렬로 퀵 정렬, 힙 정렬, 합병 정렬이 있는데 이들은 평균 시간 복잡도를 𝚶(nlogn)가지고 있는데 이에 비하면 매우 빠른 시간 복잡도를 가지고 있다. 기본 메커니즘 : 데이터가 몇번 나왔는지 세주는 것이다. 말 그대로 counting 하는 것이다. 과정 1 array | index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | value | 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 | array를 한 번 순회하면서 각 값이 나올 때마다 해당 값을 index로 하는 새로운 배열(countin

sun202x

사이트: HackerRank 난이도: 미디움 분류: Sorting 문제 정수와 연관된 문자열 배열이 주어졌을 때 계수정렬(counting sort) 하고 하나의 문자열로 출력하라. 이 때 배열의 전반부에 해당되는 요소들은 -로 대체한다. 위 배열이 주어졌을 때 아래와 같이 출력한다. 1. 나의 풀이 문제 자체에서 계수정렬(counting sort)을 사용하라고 말해줬기 때문에 그다지 어렵지 않은 문제였다. 2. 다른사람의 풀이 바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.

sun202x

알고리즘 문제를 풀다가 계수정렬(counting sort)의 개념을 잘 몰라서 공부할 겸 정리 해 보았다. 계수정렬(counting sort)이란? 계수정렬은 숫자들 간 비교를 하지 않고 정렬을 하는 알고리즘이다. 숫자를 비교하지 않고 각 숫자들의 개수만 세고 정렬을 진행하기 때문에 시간복잡도는 O(n)이 나온다. 계수정렬의 시간복잡도는 가장 빠르지만 정해진 상황에서만 쓸 수 있다. 배열 내 모든 요소는 정수이어야 한다. 배열 내 모든 요소의 범위는 1 ~ k 이어야 한다. k = O(n) 으로 나타낼 수 있어야 한다. 예제풀이 각 요소들의 범위가 1 ~ 5까지의 범위를 갖는 배열 A가 주어졌을 때 정렬한 후 출력하여라. 계수정렬은 요소들끼리 비교하지 않는다고 했다. 정해진 범위가 있으니 배열을 순회하면서 각 요소의 개수를 counting해주면 된다. 위 로직을 실행하여 count 변수를 출력해보면 아래와 같이 나오는걸 확

sun202x

사이트: HackerRank 난이도: 미디움 분류: Sorting 문제 일자에 따라 지출 값의 배열이 주어지고 지정된 일자가 지난 후, 다음날 지출 금액이 지정된 일자동안 지출한 금액의 중앙값 * 2 보다 클 경우 보안 경고 알람을 사용자에게 보낸다. 문제에서는 보안 경고 알람이 몇번 울렸는지 카운팅해서 반환하라고 한다. 위 값을 가지고 중앙값을 산출해 보면 아래와 같다. | |지출 금액 목록|중앙값|지출 금액|알림 기준 금액|알림| |---|---|---|---|---|---| |1일차|[10, 20, 30]|20|40|20 * 2 = 40|전송| |2일차|[20, 30, 40]|30|50|30 * 2 = 60|없음| 따라서 위 예시의 답은 1이다. 1. 나의 풀이 처음 문제를 접했을 때, 주어진 배열 expenditure에서 파생 배열의 min, max만 잘 관리하면 되겠는데? 라는 생각을 했었

nuyh99

문제 > P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. Python Java 해결 과정 문제를 보자마자 Counting Sort가 떠올랐다. 다만 어떤 숫자의 배치된 인덱스를 얻을 때 count[i]로 하면 해당 숫자의 제일 뒷 인덱스를 얻으므로, count[i-1]로 해당 숫자보다 1 작은 수의 인덱스를 얻고 count[i-1]++을 해주면 **오름차순

nuyh99

문제 > #### 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. Python Java 해결 과정 자바로 먼저 풀었는데, H의 수에 대해 H번 이상 인용된 논문의 수를 얻기

p3pwp3p

https://www.acmicpc.net/problem/10989 > ## Idea 처음엔 그냥 젤 빠른 Quick Sort쓰면 되는 거 아님? 하고 제출했는데 메모리 초과 ㅋㅋ 내 코딩 세계에서 제일 효율 좋고 빠르다고 생각되던 Quick Sort 알고리즘이 또 실패했다. c언어에 내장 되어있는 qsort도 써봤지만 똑같이 메모리 초과라는 채점결과가 나왔다. 문제를 딱 처음 봤을 때 입력과 출력에 같은 숫자가 두 번 세 번씩 나온다는 건 대수롭지 않게 넘겼지만 여기서 힌트를 얻었다. 입력은 어쩔 수 없이 10,000,000번 이하로 받아야 하니 최대 10,000,000번 이고 출력할 때 메모리를 아끼면 되지 않을까? 아니나 다를까 여기에 맞는 알고리즘이 있었다. `Counting

yeahxne

🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다. 계수 정렬 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 데이터의 개수가 $N$, 데이터(양수) 중 최댓값이 $K$일 때 최악의 경우에도 수행시간 $O(N+K)$를 보장한다. 계수 정렬 동작 예시 [Step 0] 가장 작은 데이터로부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다. ![](https://velog.velcdn.com/images/yeahxne/post/9e3349ce-6550-41db-8d94-c7d2e3053d2

xpmxf4

문제 백준 2751 배경 해당 문제를 Arrays.sort() 를 사용해서 풀어보려고 했다가 수 많은 런타임 에러를 맞이하게 되었다. 찾아본 해결 방법 List 안에 주어진 자료들을 넣고, Collections.sort() 를 사용 카운팅 정렬을 사용해서 해결. --> 카운팅 정렬은 실제로 많이 사용하게 된다고 해서 이 글에선 이에 대해 알아볼 것이다. 카운팅 정렬이란? 카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 𝚶(𝑛) 을 가진 알고리즘이다. 이게 가능한 이유는 카운팅 정렬은 직접적으로 값 들을 비교하지 않기 때문이다. 값 들을 직접 비교하는

scantykneesocks

Counting Sort는 특정 숫자의 범위에서만 숫자의 갯수를 세는 알고리즘입니다. 따라서 데이터는 한번만 접근하면 됩니다. Counting Sort는 전체 데이터를 한번씩 훑고 지나가면서 갯수만 세어주면 되기 때문에 big-oh는 O(N)입니다. Counting Sort Code 이미지 출처 자료 출처

nuyh99

문제 >수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 코드 해결 과정 우선 산술평균을 구하기 위해서 최초의 배열을 입력 받을 때 sum에 모두 더해줬다. 어쨌든 정렬을 해야 하기 때문에 어떤 정렬을 사용할까 고민하다가 수의 범위가 -4000 ~ 4000 인 것을 보고 어차피 최빈값도 구해야 하기 때문에 Counting Sort를 사용했다. 같은

nuyh99

문제 >N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 코드 해결 과정 최대 1000만 개의 수가 주어지지만 수의 범위가 1~10000 으로 매우 작아서 Counting Sort로 정렬했다. 😁

kihyun

O(n)의 등장 이때까지 봐온 모든 정렬 알고리즘들은 입력된 숫자들을 비교해가며 정렬을 하였다. 하지만 비교하며 정렬하는 모든 알고리즘은 O(n log n)이라는 명확한 한계를 가지고 있다. 그렇다면 어떻게하면 정렬 알고리즘을 더욱 빠르게 작동시킬 수 있을까? 바로 비교를 하지 않으면 된다. O(n) 시간에 실행되는 정렬 알고리즘들은 비교를 하지 않고 정렬을 한다는 특징을 가지고 있다. 계수 정렬 계수 정렬은 말 그대로 x에 대해서 x보다 같거나 작은 원소의 개수를 센다. 이렇게 센 값은 나중에 x를 어디에 배치할 것인가를 결정할 때에 사용된다. 예를 들어 [2, 1, 3, 4, 8, 7, 9] 라는 배열이 있다고 가정해보자 이때 x에 대해서 같거나 작은 원소의 개수를 센다면 0 = 0 1 = 1 2 = 2 3 = 3 4 = 4 7 = 5 8 = 6 9 = 7 이 된다. 이제 다른 배열을 하나 더 만들어서 오른쪽에 있는 값을 인덱스로 하여 왼쪽에 있는 값을 넣어주면