Computer Science & Engnieering/Algorithm18 빠른 정렬(Quick Sort) 빠른 정렬(Quick Sort)빠른 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 기법을 기반으로 하는 정렬 알고리즘입니다. 빠른 정렬은 합병 정렬과 비슷하지만 빠른 정렬은 배열을 분할하는 방식이 다릅니다. 입력 배열에서 하나의 기준값(pivot)을 선택하고 기준값보다 작으면 왼쪽 배열, 크면 오른쪽 배열로 분할한 뒤 재귀적으로 정렬합니다. 빠른 정렬의 동작 원리기준값(Pivot) 선택 : 배열에서 원소 하나를 기준값으로 선택합니다. 일반적으로 배열의 첫 번째, 중간, 마지막 원소 값을 선택합니다.분할(Divide) : 기준값보다 작은 값은 왼쪽 배열, 큰 값은 오른쪽 배열에 배치합니다.정복(Conquer) : 왼쪽과 오른쪽 배열을 재귀적으로 정렬합니다.빠른 정렬의 특징시간 .. 2024. 10. 22. 합병 정렬(Merge Sort) 합병 정렬(Merge Sort)합병정렬(Merge Sort)은 분할정복(Divide and Conquer) 알고리즘을 기반으로 동작하는 정렬 알고리즘입니다. 합병(Merge)을 이용하면 임의의 배열을 정렬할 수 있습니다. 예를 들어 원소가 n개인 배열을 정렬한다고 가정하면 계속해서 반으로 분할하는 과정을 거치면 언젠가 원소가 하나인 배열이 됩니다. 하나짜리 배열은 정렬된 배열이니 합치면 정렬된 배열이 됩니다. 이런 절차를 합병정렬이라 합니다. 합병 정렬의 동작 원리분할(Divide) : 원소가 1개 남을 때까지 배열을 반으로 나누는 과정을 반복합니다.정복(Conquer) : 나뉜 배열을 각각 따로 정렬합니다. 병합(Combine) : 정렬한 두 배열을 합병하여 더 큰 정렬된 배열을 만듭니다. 합병 정렬의.. 2024. 10. 21. 이분 검색(Binary Search)-재귀(Recursion) 이분 검색(Binary Search)-재귀(Recursion) 2024.10.16 - [Computer Science & Engnieering/Algorithm] - 이분 검색 알고리즘(Binary Search) 이분 검색 알고리즘(Binary Search)이분 검색 알고리즘(Binary Search)이분 검색 알고리즘(Binary Search)란 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 검색 범위를 반복적으로 절반으로 나누어 목표 값을 찾기 때문에 시간 복잡hosunghyun.tistory.com재귀 함수의 재귀 호출은 분할정복의 하향식 문제풀이 방식과 원리가 같습니다. 그래서 반복(Iteration)을 이용한 이분검색 알고리즘을 재귀 호출 방식으로 만들고자 합니다. 이분 검색 설계하기[분할].. 2024. 10. 20. 분할정복(Divide-and-Conquer) 분할정복(Divide-and-Conquer)분할정복(Divide and Conquer)이란?분할정복은 프랑스 나폴레옹이 실제로 시도한 전략에서 따온 것으로 오스트리아-러시아 연합군을 상대할 때 중앙으로 돌격하여 병력을 둘로 나누어 나뉜 병력을 각개격파한 것에서 따왔습니다. 분할정복은 문제를 작은 하위 문제로 나누고 하위 문제들을 각각 해결한 후 결과를 합쳐서 원래 문제를 해결하는 알고리즘 설계 기법입니다. 이를 통해 복잡한 문제를 단순하고 효율적으로 해결할 수 있습니다. 분할한 입력사례를 바로 답을 구하지 못할 경우 다시 분할하여 답을 구할 수 있을 만큼 충분히 작아질 때까지 입력사례를 분할합니다. 즉 분할정복은 3단계의 절차를 거칩니다. 분할(Divide) => 정복(Conquer) => 결합(Comb.. 2024. 10. 19. 알고리즘의 분석 알고리즘의 분석알고리즘의 분석이란 알고리즘의 성능을 평가하는 과정입니다. 설계된 알고리즘이 얼마나 효율적으로 주어진 문제를 해결하는지 알고리즘의 효율성을 정량적으로 측정하고 비교하기위해 수행됩니다. 분석은 주로 시간과 공간의 관점에서 이루어지며 이를 통해 더 나은 알고리즘을 설계하거나 최적의 알고리즘을 선택할 수 있습니다. 알고리즘 분석의 목적효율성 평가 : 주어진 입력에서 알고리즘이 얼마나 빠르고 효율적으로 실행되는지 평가 하기 위해서 입니다.비교 및 선택 : 여러 알고리즘 중에서 적절한 알고리즘을 선택하기 위해서 입니다.자원 관리 : 제한된 시간과 메모리 용량을 효율적으로 사용하는 알고르즘을 설계 하기 위해서 입니다. 알고리즘 분석의 기준시간 복잡도(Time Complexity) 분석시간 복잡도는 알.. 2024. 10. 18. 피보나치 수열(Fibonacci Sequence) 피보나치 수열(Fibonacci Sequence)피보나치 수열(Fibonacci Sequence)은 각 항이 이전 두 항의 합으로 정의되는 수열입니다. 수열의 초기값은 다음과 같습니다.F(0) = 0, F(1) = 1 그리고 다음 항은 이런식으로 계산됩니다.F(n) = F(n -1) + F(n - 2) (n ≥ 2) 재귀(Recursion) 방식 코드 구현 예제(Java 구현)class FibonacciSequences { public int fibonaccisequence(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } retu.. 2024. 10. 17. 이분 검색 알고리즘(Binary Search) 이분 검색 알고리즘(Binary Search)이분 검색 알고리즘(Binary Search)란 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 검색 범위를 반복적으로 절반으로 나누어 목표 값을 찾기 때문에 시간 복잡도는 O(logn)으로 매우 빠릅니다. 동작 원리이분 검색은 정렬된 배열에서만 동작하기 때문에 배열의 정렬 상태를 확인합니다. 시작 인덱스와 끝 인덱스를 설정해서 검색 범위를 지정합니다. (예 시작값 0, 끝 값 (배열의 크기 - 1) )중간 값을 계산합니다. 중간 인덱스는 (시작값 + 끝값) / 2 를 구합니다.계산한 중간값이 찾는 값이면 종료하고 중간값 > 찾는값찾는 값 이면 왼쪽 절반에서 검색하고 중간값 종료조건은 시작값이 끝값보다 커지면 검색 범위가 없으므로 목표 값이 배열에 없어 종료합.. 2024. 10. 16. 순차검색(Sequence Search) 순차검색(Sequence Search)순차검색(Sequence Search)은 리스트나 배열에서 원하는 값을 찾기 위해 처음부터 배열의 끝까지 순차적으로 검사하는 검색 알고리즘입니다. 순차 검색 알고리즘은 정렬되지 않은 배열에서도 사용할 수 있지만 탐색해야 하는 요소의 개수가 많아질수록 속도가 느려지는 단점이 존재합니다. 동작 원리0번 인덱스 즉 첫 번째 요소부터 마지막 요소까지 찾으려는 값을 한 요소씩 순차적으로 확인합니다.확인하는 요소가 값을 찾았다면 해당 위치(인덱스)를 반환하고 찾지 못했을 경우 마지막 요소까지 검사합니다.마지막까지 검색했는데 발견하지 못했으면 -1 같이 사용자가 정의한 값을 반환하여 없음으로 표시합니다. 순차 검색 알고리즘의 시간 복잡도최선의 경우(Best Case) : 찾는 요.. 2024. 10. 13. 알고리즘 알고리즘용어 정리문제(Problem)프로그램 전체 설계가 아닌 특정 과제를 수행하는 개별 모듈에서 특정 과제를 문제라고 합니다. 리스트(List)원소를 특정 순서로 나열해 놓은 것을 리스트라고 합니다. 파라미터(Parameter)문제에서 값이 지정되어 있지 않은 변수를 파라미터라고 합니다. 입력사례(Instance)파라미터에 지정할 값을 입력사례라고 합니다. 해답(Solution)특정 입력사례에 대한 해답이란 파라미터를 입력사례로 지정한 문제의 답입니다. 알고리즘(Algorithm)이란?어떤 입력사례가 주어지더라도 해답을 찾아주는 프로그램을 작성하기 위해서는 해답을 찾아주는 단계별 절차를 명시해야 하는데 단계별 절차를 알고리즘이라고 합니다. 알고리즘의 중요성알고리즘은 컴퓨터 프로그램의 핵심입니다. 동일한.. 2024. 10. 11. 이전 1 2 다음
