Computer Science
-
[CS] 이진 탐색(Binary Search)Computer Science 2020. 12. 5. 01:44
정렬된 수열에서 특정 수를 찾고자 할 때 사용되는 탐색 알고리즘. 학부 시간에 가장 첫번째로 배우는 탐색 알고리즘이 아닌가 한다. 수행원리상 이 알고리즘을 사용하기 위해선 오름차순으로 배열이 정렬되어 있어야 한다. 일반적으로 배열을 전부 순차적으로 탐색하는 방식보다 훨씬 효율적인 방식이다. 이진 탐색이라는 이름과 같이 배열을 반으로 쪼개어 수행한다. 간결한 코드이지만, 꽤나 훌륭한 성능을 보여준다. 수행 방식은 다음과 같다. 1.배열의 시작을 left, 배열의 마지막을 right으로 정한다. 2.left와 right의 중간 점을 mid로 정한다. 3.mid로 정한 값이 찾으려는 수보다 크다면 right을 mid-1로 정하고, mid로 정한 값이 찾으려는 수보다 작으면 left를 mid+1로 정한다. 4...
-
[CS]계수 정렬(Counting Sort)Computer Science 2020. 12. 5. 01:30
계수 정렬. 이름처럼 숫자를 세어 진행하는 정렬이다. 시간 복잡도는 O(n)으로 퀵 정렬 O(n log n), 합병 정렬(O(n log n)) 보다도 빠르다(!) 어떻게 이렇게 빠른 것일까?? 계수 정렬이 이루어지는 방식은 다음과 같다. 1.정렬하는 배열의 최대 값을 크기로 가지는 배열을 하나 생성. 2.정렬하는 배열을 순회하면서 각 수들이 등장하는 빈도를 각 배열의 인덱스에 저장. 3.각 빈도를 누적한 합을 저장한 배열을 새로 생성한다. 4.다시 정렬해야 하는 배열을 역순으로 순회하면서 어떤 수가 나오면 누적합 배열의 해당 인덱스로 간다. 5.누적합 배열에 저장된 값을 인덱스로 하여 정렬된 값이 들어간 배열에 값을 저장한다. 6.누적합 배열에 저장된 값을 1씩 빼준다. 7.럼 숫자를 세어 진행하는 정렬..
-
[CS] 병합 정렬(Merge Sort)Computer Science 2020. 12. 2. 20:11
컴퓨터의 창시자 폰 노이만이 개발한 정렬 알고리즘. 퀵 정렬과 함께 O(n log n)의 시간복잡도를 가지는 빠른 알고리즘 중의 하나이다. 퀵 정렬과 마찬가지로 분할 정복을 이용하는 알고리즘으로 최악의 경우 n^2의 시간복잡도를 가지는 퀵 정렬과 달리, 병합 정렬은 모든 경우에 n log n의 시간복잡도를 보장한다. 대략적인 절차를 설명하면 다음과 같다. 1.들어온 배열을 우선 반으로 쪼갠다.(홀수인 경우 반올림 또는 반내림한다) 2.나뉘어진 부분 각각을 다시 크기가 1이 될 때까지 재귀적으로 쪼갠다. 3.요소가 하나가 되면, 나뉘어진 부분끼리 비교하여,합치는 동시에 정렬을 진행한다. 4.위 과정을 재귀적으로 되돌아가 나뉘어진 부분을 각각 다시 정렬하며 합친다. 5.전부 합쳐지면 최종적으로 정렬된 배열이..
-
[CS] 퀵 정렬(Quick Sorting)Computer Science 2020. 11. 20. 22:30
찰스 앤서니 리처드 호어라는 사람이 만든 정렬 알고리즘이다.분할 정복(Divide and Conquer) 방식을 기반으로 하며최악의 경우 O(N^2), 평균적인 경우 O(n log n)의 시간 복잡도를 가진다.요소들이 균일하게 섞여있는 경우 가장 빠르며, 내림차순으로 정렬되어 있을 때에 가장 느리다.이름에서도 알 수 있듯, 가장 빠른 정렬 알고리즘들 중 하나에 속한다. 분할 정복방식이란?분할 정복 방식이란 말 그대로 어떤 커다란 문제를 여러 개의 작은 문제로 분할 한 뒤, 각각을 해결하고,해결된 각 부분을 합하여 전체의 문제를 정복하는 문제 해결 방식이다.퀵 정렬도 이러한 방식을 기초로 하고 있다. 퀵 정렬 알고리즘의 수행 과정1.배열의 첫번째 요소를 피벗(Pivot)으로 정한다. 여기서 피벗이란 배열의..
-
애자일 방법론(Agile Method)Computer Science 2020. 11. 3. 23:48
현재까지 가장 애용되어온 소프트웨어 개발 방법론에 대해 설명해보라고 하면 크게 두 가지를 꼽을 수 있을 것이다. 하나는 전통적으로 사용되어온 방법론 중 하나인 폭포수 모델일 것이고, 다른 하나는 최근에 비교적으로 중요성이 대두되는 애자일 방법론이다. 폭포수 모델(Waterfall Model) 적어도 컴퓨터공학을 전공해본 사람이라면 한 번쯤은 들어본 단어일 것이다. 소프트웨어 개발 프로세스의 하나로, 초기부터 완성까지 순차적인 단계를 거치는 모습이 폭포수같다고 하여 폭포수 모델이라고 이름 붙여졌다. 폭포수모델에 따라 소프트웨어를 개발하기 위해서는 각 단계를 순차적으로 거쳐가야 하며, 한 단계를 완료하기 전까지는 다음 단계로 나아갈 수 없다. 개인적으로 팀 단위로 개발 경험이 많지 않았던 때에 ,의도한 적은..