computer science/알고리즘17 [알고리즘] 퀵정렬(Quick Sort) 이번 시간에는 면접에서도 자주 나오는 퀵정렬에 대해 알아 보겠습니다. 퀵정렬에서는 pivot이라는 것을 사용합니다. 이 pivot이 중요한데, 그 이유는 정렬의 기준이 되기 때문입니다. 이 말이 무엇이냐 하면~예를 들어서, 2 6 4 12 3 17 11 15 19 8라는 숫자를 정렬한다고 해봅시다. 그렇다면 여기서 pivot은 아무거나 잡습니다. 정말로요 ! 여러분이 pivot이라고 정하고 싶은 숫자를 선택하시면 됩니다. 저는 12라는 숫자를 일단 pivot으로 잡아 보겠습니다. 그렇다면 이제 pivot을 기준으로 pivot보다 작거나 같은 수를 모두 pivot왼쪽으로 넘깁니다. 그러면, 다음과 같은 모양이 되겠네요. 이렇게 pivot왼쪽에는 pivot보다 작거나 같은 수가, pivot오른쪽에는 pivo.. 2019. 5. 25. [알고리즘] 매개변수 탐색(Parametric Search) 이번시간에는 매개변수탐색에 대해서 알아보겠습니다. 매개변수탐색이라는 단어가 좀 낯설 수 있는데, 이 방법은 조건을 만족하는 최대값을 구하는 방법입니다. 저는 이 방법을 조건을 만족하는 가장 큰 값, 마지노선 값이라고 생각하고 있습니다. 일단 무슨말인지 모르겠으니깐, 예를 한번 들어보겠습니다. 높이가 20 15 10 17인 나무들이 있고 영호는 n높이에서 모든 나무를 일직선으로 잘라서, 최소 7m의 나무를 가져가고 싶어합니다. 단, 여기서 영호는 환경을 생각하기 때문에 나무를 필요한 만큼만 가져 갑니다. 13높이 : 7+2+0+4 -> 13m의 나무를 가져갈 수 있습니다. 영호는 환경을 생각하기 때문에 높이를 좀 더 올려보겠습니다. 15높이 : 5+0+0+2 -> 7m의 나무를 가져갈 수 있습니다. 영호는.. 2019. 5. 24. [알고리즘] 이진탐색(binary search) 이번 시간에는 이진탐색에 대해서 알아보겠습니다. 44 6 9 10 21 45 67 100이라는 숫자에서 45라는 숫자가 있는지 없는지, 혹은 몇번째에 있는지 어떻게 찾을 수 있을까요 ? 가장 간단한 방법은 앞에서 부터 하나씩 세어 나가는 것입니다. 44,6,9,10.....이런식으로 가다보면 45가 6번째에 있다는 것을 알 수 있습니다. 만약, 데이터가 10억개 이고 그 중에 한 원소를 찾는다고 했을 때, 정~말 운이 좋다면 첫번째에 찾는 값이 있어서 바로 찾을 수 있습니다. 근데 운이 안좋다면 10억번째에 원하는 값이 있을 수 있겠네요. 이와 같은 방법으로 앞에서부터 하나씩 찾아간다면 시간복잡도는 O(N)이 됩니다. N이 만약 엄청 큰 숫자라면 당연히 연산하는데 굉장히 오랜 시간이 걸리게 될 것입니다... 2019. 5. 24. [알고리즘] 유클리드 호제법 a,b의 최대공약수는 어떻게 구할 수 있을까요 ? 먼저, 최대공약수는 a,b를 나누었을 때 나머지가 0이 되는 공약수 중 가장 큰 값을 의미합니다. 간단히 생각나는 방법은 a,b중에 작은 값을 min이라고 했을 때 2부터 min까지 값을 하나씩 증가하면서 a,b를 나누었을 때 나머지가 0이 되는 수 중에서 가장 큰 값을 구하면 a,b의 최대공약수를 구할 수 있을 것 같습니다. 하지만 min값이 큰 수일때는 그 만큼 반복을 해야 하기 때문에 비효율적입니다. 두 수의 최대공약수를 구하는 방법에는 유클리드 호제법이 있는데, 이번 시간에는 이 알고리즘으로 최대공약수를 구하는 방법을 설명하겠습니다. 여기서 r은 a를 b로 나누었을 때, 나머지 값을 의미합니다. a b r 48 26 22 26 22 4 22 4 2.. 2019. 5. 18. 이전 1 2 3 4 5 다음
