728x90 알고리즘18 계수 정렬(Counting Sort) 이때까지 배운 O(N log N)의 시간복잡도인 선택, 버블, 삽입 정렬 그리고 O(N^2)의 시간복잡도인 퀵, 병합, 힙 정렬을 배웠습니다. 가장 빨랐던 정렬은 아무래도 퀵정렬이었는데요. 이거보다 빠르게 정렬을 하는 계수 정렬에 대해 알아보겠습니다. 다음의 5 이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 5 2 3 1 3 4 4 3 4 2 3 4 3 1 1 2 4 3 3 1 2 3 4 5 1 3 2 4 정렬할 데이터 개수가 30개입니다. 특징은 모든 데이터가 1부터 5 사이입니다. 계수 정렬은 이처럼 적절한 '범위 조건'이 있어야한다는 전제에서 굉장히 빠른 알고리즘입니다. 그 속도는 O(N) 입니다. ( 저도 처음보는 시간복잡도의 속도입니다.) 계수 정렬(Counting Sort)는 단순하게 '.. 2020. 6. 1. 하루를 시작하기 전 다짐#4 안녕하세요. 옆집 컴공생입니다. 오늘도 연구실에 출근을 했습니다. 첫 이주? 정도 때만 해도 20분 정도 일찍 출근했는데 요새는 그것마저 게을러져버렸는지 딱 맞춰 출근을 하고 있습니다. 다음주엔 새로이 마음을 다 잡아야겠어요! 5월에 마지막 평일입니다. 시간이 참 야속하게만 흘러요. 이번년도에 절반이 지나갔는데 나는 뭐가 변했나 고민했습니다. 나는 지금 이 상태로 괜찮을까? 내가 지금 잘하고 있나. 얻은 해답은 없습니다. 오늘도 열심히 후회없이 살아가야겠죠. 저는 금요일을 좋아합니다. 다음 날이 주말이기도 하고 수업이 없어서 하고싶은 공부를 마음껏 할 수 있거든요. 물론 복습도 철저히 해야겠죠?ㅎㅎ 그럼 오늘도 열심히 살아보겠습니다. 오늘 할일 1. 나동빈님 강의 듣기 2. 알고리즘 문제 풀기 3. 코드.. 2020. 5. 29. 퀵정렬 복습 오늘은 퀵정렬에 대해 배워보았습니다. 말에서 부터 뭔가 굉장히 빠를 거 같은 느낌이 들죠? 선택,삽입,버블 정렬은 다 O(N^2) 복잡도의 알고리즘이었는데요 . 퀵정렬은 무려 O(n log n)의 복잡도를 가지고 있습니다. log n 은 어마어마한 수인데요 생각해보면 n = 1000 log n = 10 정도고 n = 1000000 이면 n은 20 정도 입니다. 실제로 알고리즘을 조금 더 공부하면 log n의 대단함을 더 느낄 수 있다고 하네요. 이런 퀵정렬의 핵심은 "특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까!" 입니다. 이 특정한 값을 보통 기준 pivot 값이라고 칭합니다. 퀵정렬은 큰 문제를 나눠서 해결하는 분할 정복 알고리즘에 기반하기 때문에 더 빠르게 정렬이 가능합니다. -> 특.. 2020. 5. 28. 선택정렬 복습 복습이라고 적은 이유는 이 노트가 컴공들의 선생님 같은 존재인 '나동빈' 선생님의 알고리즘 기초 강의를 보고 작성하는 거기 때문입니다. 선택정렬을 정렬 중에서 가장 기본이고 가장 비효율적인 정렬이라고 할 수 있습니다. 말로 풀어보자면 '가장 작은 수를 선택해서 앞에 수와 바꾼다' 인데요. 일단 가장 작은 수를 선택하기 위해서 배열을 다 돌아야하기 때문에 말로만 들어도 좀 비효율적인 느낌입니다. 그럼 예시를 들어보겠습니다. 다음과 같이 정렬되지 않은 배열이 있습니다. 3 4 1 5 2 배열을 쓱 보고 가장 작은 수를 선택합니다. 1입니다. 그럼 첫번째 수인 3과 교환해줍니다. 1 4 3 5 2 이제 1은 신경쓰지 않아도 됩니다. 2번째 수인 4부터 시작해서 가장 작은 수를 찾아봅니다. 처음부터 봐도 끝까지.. 2020. 5. 26. 이전 1 2 3 4 5 다음 728x90
