SelfStudyBook(2)보충_SW문제 해결 기본(array)

SW문제해결 기본 - Array 1.2 BabyGinGame

그리디 알고리즘 수행과정

Sort란

• 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대의 순서대로 재배열하는 것.

버블 정렬은 생략

카운팅 정렬

카운팅 정렬이란 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

제한사항

• 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능. 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 Array(배열)를 사용하기 떄문임
• 누적합을 구하는 이유가 무엇인가? 누적합을 구해야 각 위치, 즉 정렬한 배열할 인덱스를 찾아갈 수 있으니까.

시간 복잡도 = O(n+k): n은 항목의 개수, k는 정수의 최대값

카운팅 정렬을 시각화한 애니메이션 제공해주는 사이트

---

참고자료

소프트웨어 아카데미 S/W Problem Solving