반응형 전체186 삽입 정렬(Insertion Sort)이 뭔가요? 버블 정렬과의 차이점 안녕하세요~ 화창한 주일 잘들 보내셨나요? 이제 조금 있으면 개콘이 할 시간이군요. 개콘이 할 시간이라는 건 내일이 월요일이라는 슬픈 사실을 내포하고 있죠 ㅜㅜ 그래도 우리는 꾸준히 배워야 합니다. 그래야 남들보다 더 나은 삶을 살 수 있을테니까요 ㅋㅋ 자, 이번엔 삽입 정렬에 대해서 포스팅을 하려 합니다. 삽입 정렬이란 이름을 보면 뭔가를 삽입하면서 정렬을 한다라고 추측을 해볼 수 있을 것 같아요. 그쵸? 네, 바로 그 개념을 이용한것이 삽입 정렬입니다. 삽입 정렬은 데이터 셋을 두개로 나누어 생각합니다. 하나는 정렬된 셋이고 하나는 정렬되지 않은 셋입니다. 정렬된 셋은 항상 좌측에 위치하게되고 우측에는 앞으로 정렬해야 할 (정렬되지 않은) 남은 데이터 셋이 있습니다. 어떤 요소가 정렬이 되려면 정렬된.. 2016. 6. 26. 버블 정렬(Bubble Sort)아 넌 누구니? 안녕하세요~ 주말 하루 종일 집보러 다닌다고 엄청 걸었네요. 요즘 집값이 왜이리 비싼지 도대체 집을 살 수가 없어요 ㅜㅜ 언제쯤 이 집 값 버블이 좀 가라 앉을까요? 이 집 값 버블처럼 버블 정렬의 시간 복잡도 역시 Ο(n2) 로 최악입니다. 왜 이렇게 높을까요? 버블 정렬은 도대체 어떤 알고리즘 이길래 서울 집 값처럼 높은 시간 복잡도를 갖고 있는 걸까요?? 간단히 설명하자면 버블 정렬은 순차적으로 두개의 값을 비교하면서 정렬을 하는데, 정렬할 것이 없을때 까지 무한 반복하면서 정렬을 하게됩니다. 그림을 보면서 이해해 볼까요? 자, 다음과 같은 데이터 셋이 있다고 가정해 봅시다. 다섯 개의 숫자들이 정렬되지 않은 채로 들어있음을 확인 하실 수 있을겁니다. 이제 이 숫자들을 버블 정렬을 이용해서 작은 숫.. 2016. 6. 26. 보간 탐색 ( Interpolation Search ) 안녕하세요~~ 황금같은 주말 아침에 벌써 세번째 포스팅인것 같습니다. 이렇게 아침 시간을 이용해서 남들보다 더 부지런하게 뭔가 하다보면 나중엔 달콤한 상이 주어지게죠? ㅎㅎ 요즘 알고리즘을 다시 공부해 봐야 겠다는 생각에 여기저기 인터넷 서치해보면서 국내 및 해외 자료를 읽어보면서 알고리즘 관련 자료를 찾아보고 포스팅을 하고 있는데요, 이번엔 보간 탐색 알고리즘에 대해서 포스팅하려 합니다. 보간 탐색은 사실 제가 학교 다닐때는 못 배웠던 내용이었습니다. 그래서 알고리즘 이름부터가 생소했는데요 알고보니 이 녀석은 이진 탐색 알고리즘의 업그레이드 버전이라고 하더군요. 이진 탐색 알고리즘이 선형 알고리즘에 비해서 평균적으로 훨씬 빠른 시간복잡도를 가지고 있다고 지난 포스팅에서 말씀 드렸었는데요, 여기서 조금 .. 2016. 6. 25. 이진 탐색 알고리즘 ( Binary Search Algorithm ) 선행 학습 : 분할 정복 알고리즘, 선형(순차) 탐색 알고리즘 안녕하세요~ 주말 아침부터 포스팅하네요. 아침부터 날씨가 좋네요 햇빛도 좋고~ 근데 오후에 자외선이 너무 강하다 그래서 그게 좀 걸리네요. 썬크림 범벅하고 나가야 겠어요 ㅋㅋㅋ 자, 본론으로 들어가서 오늘은 이진 탐색 알고리즘에 대해서 알아볼 겁니다. 이진 탐색 알고리즘이란 이름에서 "이진"이라는 것은 학교 일진, 이진 이런게 아니구요 ㅡㅡㅋ binary 라는 겁니다. 0 또는 1 로 숫자를 표현 할 때 이진수라고 하잖아요? 그 이진을 말하는 겁니다. 왜 이진 탐색이라는 알고리즘이 붙었을 까요? 그 이유는 알고리즘이 어떻게 동작하는지 그 원리를 알면 쉽게 이해가 됩니다. 자, 예제를 보면서 설명을 해볼게요. 아래 그림은 여러 숫자들이 작은 수.. 2016. 6. 25. 선형(순차) 탐색 알고리즘 안녕하세요~ 오늘은 순차 탐색 또는 선형 탐색이라고도 불리는 "Linear Search (Sequential Search)" 알고리즘에 대해 알아보도록 하겠습니다. 이 알고리즘은 탐색 알고리즘 중에서 가장 기본이 되는 알고리즘 입니다. 공대를 나오지 않은 분들도 "순차"라는 단어를 봤을 때 느낌이 오셨을 겁니다. 네 맞습니다. 이 알고리즘은 그냥 다수의 아이템을 순차적으로 하나씩 조회 하면서 내가 찾고자 하는 아이템이 있는지를 탐색하는 것입니다. 찾고자 하는 아이템을 찾을 때까지 모든 아이템을 검사하게되며 특정 아이템을 찾았을 경우에는 해당 아이템을 반환하고 알고리즘은 거기서 종료됩니다. 간단히 말하면 10개의 아이템 중에서 첫 번째로 검색한 아이템이 내가 원한 아이템이면 나머지 9개는 조회할 필요없이 .. 2016. 6. 25. Divide and Conquer ( 분할 정복 알고리즘 ) 분할 정복 알고리즘이랑 어떤 문제를 여러개의 하위 문제들로 나누고 각 하위 문제들의 솔루션을 찾은 뒤 이들을 병합하여 최선의 솔루션으로 만드는 것입니다. 각 하위의 문제들은 모두 개별적으로 문제를 해결하게 되는데, 이렇게 하는 이유는 작은 문제로 나누었을 경우 더 쉽게 해결책을 찾을 수 있기 때문입니다. 문제를 잘게 쪼개어 더 작은 문제로 만들고 이를 반복하다보면 결국 더이상 쪼갤 수 없는 문제가 되고 이렇게 쪼개어진 문제들의 해결책을 찾아서 병합하면 문제들을 나누기 전 최초의 문제에 대한 해결책을 만들 수가 있습니다. 아래 그림처럼 말이죠. 크게 봤을 때 분할 정복 알고리즘은 3 단계를 거치게 됩니다.나누기/쪼개기이 단계는 주어진 문제를 작은 단위의 문제들로 나누는 것입니다. 작게 나누어진 문제는 본래.. 2016. 6. 24. Greedy Algorithm (그리디 알고리즘) 알고리즘이란 주어진 문제에 대한 최적의 해결법을 디자인하는 것이죠. 그 종류도 다양합니다. 그 중에서 그리디 알고리즘은 주어진 도메인 중에서 최선의 것을 선택하는 알고리즘을 말합니다. 그리디 알고리즘은 현재 주어진 문제에 대해서 최선의 해결책을 줄 수 있을지는 모르지만 동일한 문제에서 도메인이 변경된다면 최선의 해결책을 주지 못할 수 도 있습니다. 코인 개수 최소화하기유명한 문제 하나를 그리디 알고리즘을 이용해서 풀어보도록 하겠습니다. 이 문제는 어떤 가격이 주어지고, 현재 내가 가지고 있는 돈의 단위가 정해져있을 때 목표 가격을 맞추기 위해서 최소한의 코인을 사용하는 것입니다. 즉, 18원을 만들어야 하는데 10원, 5원, 2원, 1원짜리 동전이 있다고 합시다. 이때 그리디 알고리즘은 10원짜리 하나... 2016. 6. 24. 알고리즘이란? 시간/공간 복잡도란? 알고리즘이라는 것은 원하는 출력 또는 결과를 얻기 위해서 명령어 셋을 특정 순서에 따라 정의해놓은 것입니다. 간단히 말하면 수학의 공식과도 같은 것이죠.데이터 구조 관점에서 봤을 때 몇가지 중요한 알고리즘 카테고리를 살펴보면 아래와 같습니다 −검색 알고리즘 − 데이터 구조 안에 있는 특정 아이템을 찾기 위한 알고리즘정렬 알고리즘 − 아이템들을 특정 순서에 따라 정렬하기 위한 알고리즘삽입 알고리즘 − 데이터 구조에 아이템을 추가하기 위한 알고리즘수정 알고리즘 − 데이터 구조에 이미 존재하는 아이템을 수정하기 위한 알고리즘삭제 알고리즘 − 데이터 구조에 이미 존재하는 아이템을 삭제하기 위한 알고리즘알고리즘의 특징알고리즘을 다음과 같은 특징을 가지고 있습니다 −명확성 − 알고리즘은 애매모호하지 않고 명확해야 .. 2016. 6. 24. 더 얇고 가벼워진 아마존 킨들 2016 기본 모델 아마존이 업그레이드 된 흰색 킨들을 내놓았습니다. 이 새 기본 모델은 2년동안 가장 많은 사랑은 받아온 모델의 첫번째 업데이트 입니다. 이 모델은 2010년도의 킨들 키보드 이후로 처음으로 화이트 색상이 있는 모델입니다. $119.99 짜리 Kindle Paperwhite도 역시 흰색 모델이 새롭게 출시가 되었습니다.새 킨들의 가격은 $79.99 정도이지만 더 빠른 네비게이션을 제공하기 위해 기존 모델에 비해 두배 많은 메모리 용량을 가지고 있습니다. 뿐만아니라 더 가볍고 얇아졌으며 좀 더 둥그스름한 디자인으로 한손으로 잡기 쉽도록 제작되었습니다. 그리고 블루투스 오디오를 지원한다고 합니다. 2014년도 모델처럼 이 새 모델 역시 터치스크린 디스플레이를 가지고 있습니다만 킨들 페이퍼화이트 처럼 300 p.. 2016. 6. 22. 이전 1 ··· 17 18 19 20 21 다음 728x90
