반응형 알고리즘7 데이터 구조 및 알고리즘의 시공간 복잡도를 한눈에!!!! 안녕하세요~ 요새 한참 장마철이라 비가 엄청 오네요. 일본에 비오는거 보니까 집이 완전히 고꾸라지는 장면도 뉴스에 나오던데요... 아무쪼록 이번 장마로 큰 피해가 없었으면 하는 바람입니다. 자, 오늘은 여러분들이 알고있는 대부분의 데이터 구조(Data Structures)와 정렬 알고리즘(Array Sorting Algorithm), 그래프연산(Graph Operation) 및 힙 연산(Heap Operation)에 대한 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complecity)를 Big-O 노테이션으로 계산한 값이 얼마나 되는지 한눈에 요약해서 알려드리고자 합니다. 우선 시공간 복잡도를 표시하기 위한 등급을 아래와 같이 색깔별로 나누었습니다. 초록색일 수록 좋은것이고 빨간.. 2016. 7. 2. 병합 정렬 ( Merge Sort ) 이란? 안녕하세요~ 오늘은 두 개의 포스팅을 연달아 합니다~ 앞서서 선택 정렬에 대해서 알아봤는데요, 너무 쉬웠죠? 쉬운만큼 속도가 느린 알고리즘 중에 하나였습니다. 이번에는 더 빠른 알고리즘에 대해서 알아볼 겁니다. 바로 병합 정렬인데요, 이름에서도 알 수 있듯이 병합하면서 정렬하는 알고리즘 입니다. 이 알고리즘은 divide and conquer, 즉, 분할 정복 알고리즘에 기반한 알고리즘입니다. 일단 최소 단위로 잘게 나눈 다음에 병합하면서 정렬을 하는 것이죠. 어느 정도 감이 오시나요? 그럼 이제 그림 예제를 통해서 한 번 자세하게 알아보도록 하죠. 이번에도 역시 아래와 같이 정렬되지 않은 데이터 셋에서 부터 출발해 볼게요. 이제 이 데이터 셋을 반으로 나눕니다. 그리고 그렇게 나뉜 데이터 셋을 또 각각.. 2016. 6. 28. 선택 정렬 ( Selection Sort )이란? 안녕하세요~~ 어제는 너무 피곤해서 포스팅을 못하고 일찍 잠이 들었어요.. 오늘은 어제 충분히 잠을 잤으니 포스팅을 또 이어 가려 합니다. 오늘은 선택 정렬에 대해서 포스팅을 할 건데요, 이 선택 정렬은 앞에서 포스팅 했던 버블 정렬이나 삽입 정렬처럼 쉽고 간단한 정렬 알고리즘입니다. 우선, 간단하게 선택 정렬 알고리즘의 수행 방법에 대해서 얘기하자면, 선택 정렬은 정렬되지 않은 데이터 셋을 처음부터 순차적으로 모든 데이터에 대해서 검사를 하면서 최소 데이터를 찾아냅니다. 그리고 그렇게 찾은 데이터와 첫 번째 인덱스에 있는 데이터를 서로 바꿔줍니다. 이렇게 함으로써 가장 좌측에는 가장 작은 수가 들어가겠죠. 두 번째 이터레이션에서 찾은 (전체 데이터 중에서) 두 번째로 작은 수는 두 번째 인덱스의 데이터.. 2016. 6. 28. 보간 탐색 ( Interpolation Search ) 안녕하세요~~ 황금같은 주말 아침에 벌써 세번째 포스팅인것 같습니다. 이렇게 아침 시간을 이용해서 남들보다 더 부지런하게 뭔가 하다보면 나중엔 달콤한 상이 주어지게죠? ㅎㅎ 요즘 알고리즘을 다시 공부해 봐야 겠다는 생각에 여기저기 인터넷 서치해보면서 국내 및 해외 자료를 읽어보면서 알고리즘 관련 자료를 찾아보고 포스팅을 하고 있는데요, 이번엔 보간 탐색 알고리즘에 대해서 포스팅하려 합니다. 보간 탐색은 사실 제가 학교 다닐때는 못 배웠던 내용이었습니다. 그래서 알고리즘 이름부터가 생소했는데요 알고보니 이 녀석은 이진 탐색 알고리즘의 업그레이드 버전이라고 하더군요. 이진 탐색 알고리즘이 선형 알고리즘에 비해서 평균적으로 훨씬 빠른 시간복잡도를 가지고 있다고 지난 포스팅에서 말씀 드렸었는데요, 여기서 조금 .. 2016. 6. 25. Divide and Conquer ( 분할 정복 알고리즘 ) 분할 정복 알고리즘이랑 어떤 문제를 여러개의 하위 문제들로 나누고 각 하위 문제들의 솔루션을 찾은 뒤 이들을 병합하여 최선의 솔루션으로 만드는 것입니다. 각 하위의 문제들은 모두 개별적으로 문제를 해결하게 되는데, 이렇게 하는 이유는 작은 문제로 나누었을 경우 더 쉽게 해결책을 찾을 수 있기 때문입니다. 문제를 잘게 쪼개어 더 작은 문제로 만들고 이를 반복하다보면 결국 더이상 쪼갤 수 없는 문제가 되고 이렇게 쪼개어진 문제들의 해결책을 찾아서 병합하면 문제들을 나누기 전 최초의 문제에 대한 해결책을 만들 수가 있습니다. 아래 그림처럼 말이죠. 크게 봤을 때 분할 정복 알고리즘은 3 단계를 거치게 됩니다.나누기/쪼개기이 단계는 주어진 문제를 작은 단위의 문제들로 나누는 것입니다. 작게 나누어진 문제는 본래.. 2016. 6. 24. Greedy Algorithm (그리디 알고리즘) 알고리즘이란 주어진 문제에 대한 최적의 해결법을 디자인하는 것이죠. 그 종류도 다양합니다. 그 중에서 그리디 알고리즘은 주어진 도메인 중에서 최선의 것을 선택하는 알고리즘을 말합니다. 그리디 알고리즘은 현재 주어진 문제에 대해서 최선의 해결책을 줄 수 있을지는 모르지만 동일한 문제에서 도메인이 변경된다면 최선의 해결책을 주지 못할 수 도 있습니다. 코인 개수 최소화하기유명한 문제 하나를 그리디 알고리즘을 이용해서 풀어보도록 하겠습니다. 이 문제는 어떤 가격이 주어지고, 현재 내가 가지고 있는 돈의 단위가 정해져있을 때 목표 가격을 맞추기 위해서 최소한의 코인을 사용하는 것입니다. 즉, 18원을 만들어야 하는데 10원, 5원, 2원, 1원짜리 동전이 있다고 합시다. 이때 그리디 알고리즘은 10원짜리 하나... 2016. 6. 24. 알고리즘이란? 시간/공간 복잡도란? 알고리즘이라는 것은 원하는 출력 또는 결과를 얻기 위해서 명령어 셋을 특정 순서에 따라 정의해놓은 것입니다. 간단히 말하면 수학의 공식과도 같은 것이죠.데이터 구조 관점에서 봤을 때 몇가지 중요한 알고리즘 카테고리를 살펴보면 아래와 같습니다 −검색 알고리즘 − 데이터 구조 안에 있는 특정 아이템을 찾기 위한 알고리즘정렬 알고리즘 − 아이템들을 특정 순서에 따라 정렬하기 위한 알고리즘삽입 알고리즘 − 데이터 구조에 아이템을 추가하기 위한 알고리즘수정 알고리즘 − 데이터 구조에 이미 존재하는 아이템을 수정하기 위한 알고리즘삭제 알고리즘 − 데이터 구조에 이미 존재하는 아이템을 삭제하기 위한 알고리즘알고리즘의 특징알고리즘을 다음과 같은 특징을 가지고 있습니다 −명확성 − 알고리즘은 애매모호하지 않고 명확해야 .. 2016. 6. 24. 이전 1 다음 728x90
