본문 바로가기

분류 전체보기

(317)
# 미사용 그림으로 알아보는 버킷 정렬 (bucket sort) 버킷 정렬 해싱과 매우 비슷합니다. 적당한 기준으로 나누고 각 부분들을 또 다른 알고리즘으로 정렬한 뒤 순서에 맞게 합칩니다. 시간 복잡도 혼자서는 사용되지 않고 다른 알고리즘과 함께 사용되기 때문에, 같이 사용되는 다른 알고리즘에 의하여 시간 복잡도가 결정됩니다. Worst Case는 모든 데이터가 하나의 버킷에 들어가는 것이고, Best Case는 모두 균등하게 분배되는 것입니다. 정렬 예제 [99, 57, 14, 23, 55, 77]을 정렬해보겠습니다. 먼저 적당히 여러개의 버킷으로 나누고 적당히 버킷의 룰을 결정합니다. 룰은 정말로 적당히 정하는데 해싱으로 나눌수도 있고 범위일수도 있습니다. 여기서는 범위를 기반으로 3개의 버킷으로 나눠서 [14, 23], [57, 55], [99, 77]로 분배..

2018. 10. 1. 02:15

# 미사용 그림으로 알아보는 기수 정렬 (radix sort) 기수 정렬각 자리수에 대해 정렬하여 전체의 정렬결과를 얻어오는 정렬방식. 정렬할 요소가 정수인 경우에만 사용할 수 있다. 각 기수에 대하여 정렬하는 과정은 보통 큐를 이용하여 구현한다.배열을 순차적으로 탐색하면서 알맞은 큐에 집어넣고, 모든 요소를 다 집어넣었으면 작은 큐부터 순서대로 빼낸다. 기수정렬을 내림차순으로 하고싶은 경우에는,큰 큐부터 꺼내면 된다. 시간 복잡도각 기수에 대하여 같은 작업을 반복하기 때문에,MAX 값의 자리수가 크면 클수록 소요되는 시간이 증가한다. STEP의 개수 : 최대값의 기수 값. (d)순차적으로 큐에 넣는 작업 : 배열의 사이즈. (n) 즉, 시간 복잡도는 O(d*n).d는 가장 큰 수의 자리수 값. 코드

2018. 10. 1. 01:40

# 미사용 그림으로 알아보는 카운팅 정렬 (counting sort) 카운팅 정렬 (=계수 정렬)카운팅 정렬이란 중복허용 배열에서 각 요소의 개수를 바탕으로정렬된 배열을 계산하는 방법을 의미한다. 정렬된 배열을 계산하기 때문에,요소끼리 비교하는 과정이 없다. 시간 복잡도카운팅 정렬은 도메인의 범위가 시간, 공간에 직접적인 영향을 준다.도메인의 범위가 for의 순회횟수와 카운팅 배열의 크기에 연관되어 있기 때문이다. 배열의 크기가 n 이고, 도메인의 크기가 k이라고 하면.여기서 카운팅 정렬의 시간 복잡도는 O(n+k)이다. 바꿔말하면, 도메인이 작을수록 그 효과는 극적이다.O(n)에 가까운 비용으로 정렬할 수 있다! 음수를 포함하는 배열의 카운팅 정렬카운팅 정렬을 이용하여 음수를 정렬해야 한다면, 간단한 트릭을 사용하면 된다. 가장 작은 음수가 0이 되도록 적당하게 W를 더..

2018. 9. 30. 22:58

# 미사용 그림으로 알아보는 병합 정렬 (merge sort) 병합 정렬병합정렬이란, 이미 정렬된 두 개의 배열에 대해 합쳐진 정렬된 배열을 얻는 방법이다. 결과가 들어갈 새로운 배열을 선언하고,두 배열의 앞쪽을 비교하면서 결과 배열의 앞쪽부터 채워 넣으면,쉽게 합쳐진 배열을 얻을 수 있다. 정렬되지 않은 상태에서의 병합정렬정렬되지 않은 배열 arr[]에 대하여,arr[]을 균등하게 반으로 나눈 배열을 A[], B[]라고 하자. 여기서 2가지 선택지가 있다.A[], B[]를 다른 알고리즘으로 정렬하고 병합정렬로 합친다.A[], B[]에 다시 위의 작업을 반복한다. 첫 번째) A[], B[]를 퀵 정렬같은 다른 알고리즘으로 정렬하면,두 개의 배열은 정렬된 상태가 되기 때문에,이 두 배열을 병합정렬로 합치면 정렬된 arr[]이 완성된다. 두 번째)다시 A[]와 B[]를..

2018. 9. 30. 18:13

# 미사용 그림으로 알아보는 퀵 정렬 (quick sort) 퀵 정렬퀵 정렬의 원리는 생각보다 간단하다.사람들을 키 순서대로 정렬하려고 해보자. 우선 기준이 되는 한 명을 뽑고,기준보다 작은 사람들은 순서에 상관없이 왼편에, 기준보다 큰 사람들은 순서에 상관없이 오른편에 세운다. 기준이 되는 한 사람을 제외하면 2개의 부분배열로 나누어지게 되는데,만들어진 부분배열에 다시 똑같은 작업을 반복한다. 계속해서 배열을 2부분으로 쪼개다보면,부분배열의 크기가 0 또는 1인 경우가 나오게되는데, 크기가 0 또는 1인 부분배열은 "더 이상 정렬의 필요성이 없는 배열" 이므로,"정렬이 완료된 상태의 배열" 로 해석할 수 있다. 정리하자면,퀵정렬은 2개의 부분배열로 나누고,정렬 필요성이 있는 부분배열에 다시 퀵정렬을 적용하는 과정이다. 퀵 정렬의 시간 복잡도퀵 정렬은 피벗을 기점..

2018. 9. 30. 17:08

# 미사용 안드로이드, 비트 계산기 프로젝트 개요모바일 프로그래밍 2주차 과제.지금까지 배웠던 내용(버튼, 텍스트뷰, 온클릭 이벤트)으로 간단한 계산기 어플을 만드는 것. 교수님께서는 괄호와 사칙연산만 되면 괜찮다고 하셨지만,개인적인 욕심으로 비트연산자 및 함수까지 넣어봤다. 아쉬운 점은,윈도우 계산기처럼 잘못된 수식을 원천방지하는 것을 목표로 했지만,의외의 상황이 많아 80% 정도밖에 구현하지 못했다는 점. 프리뷰 구현 상세MainActivity오로지 버튼과 텍스트뷰, Mapper에 이벤트를 전달하는 함수만 존재한다.버튼을 클릭하면 Mapper에 이벤트를 전달하여 대신 처리하게끔 한다.MapperMainActivity와 Eval 사이를 중계해주는 역할을 한다.이벤트를 파싱하고 해당 결과값으로 MainActivity을 갱신하는 것이 주 역..

2018. 9. 26. 21:36

# 미사용 [백준 11066] 파일 합치기 [백준 11066] 파일 합치기문제소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오. 예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파..

2018. 9. 16. 14:09

# 미사용 대각으로 테이블에 접근하기 우대각으로 테이블에 접근하자.위의 그림처럼 우대각 순서대로 테이블에 접근하는 방법을 생각해보자. 필요한 규칙을 찾아보자.모든 대각은 j==0인 칸에서 시작되며, j==6인 칸에서 끝난다.j가 6에 도달했을 때 다음 대각의 첫 칸으로 옮긴 뒤, 테이블을 벗어난 대각을 만나면 순회를 종료한다. 코드로 직접 구현해보자.while for조금만 더 생각해보면 (i, j)표현은 (대각번호, 요소번호) 표현으로 상호변환될 수 있다. 좌대각으로 테이블에 접근하자.우대각으로 접근하는 for문 코드에서 i와 j를 바꾸면 된다.

2018. 9. 16. 02:50