반응형 algorithm7 병합 정렬 ( Merge Sort ) 이란? 안녕하세요~ 오늘은 두 개의 포스팅을 연달아 합니다~ 앞서서 선택 정렬에 대해서 알아봤는데요, 너무 쉬웠죠? 쉬운만큼 속도가 느린 알고리즘 중에 하나였습니다. 이번에는 더 빠른 알고리즘에 대해서 알아볼 겁니다. 바로 병합 정렬인데요, 이름에서도 알 수 있듯이 병합하면서 정렬하는 알고리즘 입니다. 이 알고리즘은 divide and conquer, 즉, 분할 정복 알고리즘에 기반한 알고리즘입니다. 일단 최소 단위로 잘게 나눈 다음에 병합하면서 정렬을 하는 것이죠. 어느 정도 감이 오시나요? 그럼 이제 그림 예제를 통해서 한 번 자세하게 알아보도록 하죠. 이번에도 역시 아래와 같이 정렬되지 않은 데이터 셋에서 부터 출발해 볼게요. 이제 이 데이터 셋을 반으로 나눕니다. 그리고 그렇게 나뉜 데이터 셋을 또 각각.. 2016. 6. 28. 선택 정렬 ( Selection Sort )이란? 안녕하세요~~ 어제는 너무 피곤해서 포스팅을 못하고 일찍 잠이 들었어요.. 오늘은 어제 충분히 잠을 잤으니 포스팅을 또 이어 가려 합니다. 오늘은 선택 정렬에 대해서 포스팅을 할 건데요, 이 선택 정렬은 앞에서 포스팅 했던 버블 정렬이나 삽입 정렬처럼 쉽고 간단한 정렬 알고리즘입니다. 우선, 간단하게 선택 정렬 알고리즘의 수행 방법에 대해서 얘기하자면, 선택 정렬은 정렬되지 않은 데이터 셋을 처음부터 순차적으로 모든 데이터에 대해서 검사를 하면서 최소 데이터를 찾아냅니다. 그리고 그렇게 찾은 데이터와 첫 번째 인덱스에 있는 데이터를 서로 바꿔줍니다. 이렇게 함으로써 가장 좌측에는 가장 작은 수가 들어가겠죠. 두 번째 이터레이션에서 찾은 (전체 데이터 중에서) 두 번째로 작은 수는 두 번째 인덱스의 데이터.. 2016. 6. 28. 삽입 정렬(Insertion Sort)이 뭔가요? 버블 정렬과의 차이점 안녕하세요~ 화창한 주일 잘들 보내셨나요? 이제 조금 있으면 개콘이 할 시간이군요. 개콘이 할 시간이라는 건 내일이 월요일이라는 슬픈 사실을 내포하고 있죠 ㅜㅜ 그래도 우리는 꾸준히 배워야 합니다. 그래야 남들보다 더 나은 삶을 살 수 있을테니까요 ㅋㅋ 자, 이번엔 삽입 정렬에 대해서 포스팅을 하려 합니다. 삽입 정렬이란 이름을 보면 뭔가를 삽입하면서 정렬을 한다라고 추측을 해볼 수 있을 것 같아요. 그쵸? 네, 바로 그 개념을 이용한것이 삽입 정렬입니다. 삽입 정렬은 데이터 셋을 두개로 나누어 생각합니다. 하나는 정렬된 셋이고 하나는 정렬되지 않은 셋입니다. 정렬된 셋은 항상 좌측에 위치하게되고 우측에는 앞으로 정렬해야 할 (정렬되지 않은) 남은 데이터 셋이 있습니다. 어떤 요소가 정렬이 되려면 정렬된.. 2016. 6. 26. 버블 정렬(Bubble Sort)아 넌 누구니? 안녕하세요~ 주말 하루 종일 집보러 다닌다고 엄청 걸었네요. 요즘 집값이 왜이리 비싼지 도대체 집을 살 수가 없어요 ㅜㅜ 언제쯤 이 집 값 버블이 좀 가라 앉을까요? 이 집 값 버블처럼 버블 정렬의 시간 복잡도 역시 Ο(n2) 로 최악입니다. 왜 이렇게 높을까요? 버블 정렬은 도대체 어떤 알고리즘 이길래 서울 집 값처럼 높은 시간 복잡도를 갖고 있는 걸까요?? 간단히 설명하자면 버블 정렬은 순차적으로 두개의 값을 비교하면서 정렬을 하는데, 정렬할 것이 없을때 까지 무한 반복하면서 정렬을 하게됩니다. 그림을 보면서 이해해 볼까요? 자, 다음과 같은 데이터 셋이 있다고 가정해 봅시다. 다섯 개의 숫자들이 정렬되지 않은 채로 들어있음을 확인 하실 수 있을겁니다. 이제 이 숫자들을 버블 정렬을 이용해서 작은 숫.. 2016. 6. 26. 보간 탐색 ( Interpolation Search ) 안녕하세요~~ 황금같은 주말 아침에 벌써 세번째 포스팅인것 같습니다. 이렇게 아침 시간을 이용해서 남들보다 더 부지런하게 뭔가 하다보면 나중엔 달콤한 상이 주어지게죠? ㅎㅎ 요즘 알고리즘을 다시 공부해 봐야 겠다는 생각에 여기저기 인터넷 서치해보면서 국내 및 해외 자료를 읽어보면서 알고리즘 관련 자료를 찾아보고 포스팅을 하고 있는데요, 이번엔 보간 탐색 알고리즘에 대해서 포스팅하려 합니다. 보간 탐색은 사실 제가 학교 다닐때는 못 배웠던 내용이었습니다. 그래서 알고리즘 이름부터가 생소했는데요 알고보니 이 녀석은 이진 탐색 알고리즘의 업그레이드 버전이라고 하더군요. 이진 탐색 알고리즘이 선형 알고리즘에 비해서 평균적으로 훨씬 빠른 시간복잡도를 가지고 있다고 지난 포스팅에서 말씀 드렸었는데요, 여기서 조금 .. 2016. 6. 25. Divide and Conquer ( 분할 정복 알고리즘 ) 분할 정복 알고리즘이랑 어떤 문제를 여러개의 하위 문제들로 나누고 각 하위 문제들의 솔루션을 찾은 뒤 이들을 병합하여 최선의 솔루션으로 만드는 것입니다. 각 하위의 문제들은 모두 개별적으로 문제를 해결하게 되는데, 이렇게 하는 이유는 작은 문제로 나누었을 경우 더 쉽게 해결책을 찾을 수 있기 때문입니다. 문제를 잘게 쪼개어 더 작은 문제로 만들고 이를 반복하다보면 결국 더이상 쪼갤 수 없는 문제가 되고 이렇게 쪼개어진 문제들의 해결책을 찾아서 병합하면 문제들을 나누기 전 최초의 문제에 대한 해결책을 만들 수가 있습니다. 아래 그림처럼 말이죠. 크게 봤을 때 분할 정복 알고리즘은 3 단계를 거치게 됩니다.나누기/쪼개기이 단계는 주어진 문제를 작은 단위의 문제들로 나누는 것입니다. 작게 나누어진 문제는 본래.. 2016. 6. 24. Greedy Algorithm (그리디 알고리즘) 알고리즘이란 주어진 문제에 대한 최적의 해결법을 디자인하는 것이죠. 그 종류도 다양합니다. 그 중에서 그리디 알고리즘은 주어진 도메인 중에서 최선의 것을 선택하는 알고리즘을 말합니다. 그리디 알고리즘은 현재 주어진 문제에 대해서 최선의 해결책을 줄 수 있을지는 모르지만 동일한 문제에서 도메인이 변경된다면 최선의 해결책을 주지 못할 수 도 있습니다. 코인 개수 최소화하기유명한 문제 하나를 그리디 알고리즘을 이용해서 풀어보도록 하겠습니다. 이 문제는 어떤 가격이 주어지고, 현재 내가 가지고 있는 돈의 단위가 정해져있을 때 목표 가격을 맞추기 위해서 최소한의 코인을 사용하는 것입니다. 즉, 18원을 만들어야 하는데 10원, 5원, 2원, 1원짜리 동전이 있다고 합시다. 이때 그리디 알고리즘은 10원짜리 하나... 2016. 6. 24. 이전 1 다음 728x90
