개발자's Life

기수정령의 개념과 원리 _ by.하루코딩,copy RowenJobs 값을 비교하지 않는 특이한 정렬이고 자릿수를 정한 다음 해당 자릿수만 비교한다. 시간 복잡도는 kn 이고 k 는 자릿수 시간복잡도가 가장 짧은 정렬이다. 큐를 만들어 넣는 부분이 좀 어려워질수 있다. 기수정렬은 10개의 큐를 이용 한자릿수에 올 수 있는 자릿수는 0 ~ 9 라 10개의 큐를 이용 일의 자리를 정렬을 하고 ~ N 의 자리까지 큐에 넣어 정렬을 한다. 아래는 강의 예시를 참고해서 확인하면 된다. 첫번째 이미지는 일의 자릿수에 대해 큐에 넣고 순서대로 정렬한 이미지 이고 두번째 이미지는 1차적으로 정렬한 배열의 각 십의자리에 대해 큐에 넣고 그대로 정렬을 한 이미지 이다. 큐는 선입선출의 규칙을 가지고 있어 먼저 들어온 데이터..

병합정렬 장점 안정적이고 시간복잡도도 좋은 알고리즘이고 코딩테스트에서 병합정렬을 이해하고 응용해서 푸는 문제가 많이 나온다. 이 말은 정렬 관련 문제뿐만 아니라 정렬 아이디어를 가지고 푸는 문제도 많이 나온다는 말이다. 핵심은 2개의 그룹을 병합하는 원리는 꼭 숙지 해야한다는 것이다! 투포인터 개념을 사용하여 왼쪽 오른쪽 그룹을 병합하는 것이고 아래 예를 들어 설명을 적어 놓는다. 오름차순으로 정렬! 12 53 27 11 5 23 76 67 병합 정렬은 우선 두개씩 그룹으로 합쳐지며 정렬이 된다.(N번) 4개로 나눠진 그룹을 각각 작은값을 왼쪽 큰 값을 오른쪽으로 정렬이 되고 그룹으로 합쳐지면서 정렬이 일어난다. 12 53 11 27 5 23 67 76 오름차순이기에 작은 값이 앞으로 오게된다. 0번 인..