[알고리즘] 카운팅 소트 (Counting Sort) 원리와 구현
👉🏾 원리 🌼 주어진 값들 사이의 범위가 작을수록 빠른 알고리즘이다. 주어진 배열이 있다. 미리 count라는 배열을 생성한다. 그리고 주어진 배열의 길이만큼 for loop를 돌면서 count 배열의 주어진 값 번째 자리를 1 더해준다. 그후 count 배열을 0부터 주어진 배열의 끝 인덱스까지 loop를 돌면서 count 배열의 n번째 자리에 저장된 수만큼 반복해서 출력해주면 된다. 잘 이해가 안간다면 코드로 보자! 👉🏾 문제점 ⚠️ 주어진 값들 사이의 범위가 작을수록 빠른 알고리즘이지만 만약 주어진 값들이 [1,1000000, ...] 이라면 1과 1000000 사이의 의미 없는 999999개의 인덱스들을 전부 탐색해야 하기 때문에 주어진 값 사이의 범위가 클수록 느리다. 👉🏾 구현 💻 import..
알고리즘
2022. 6. 17. 21:33
