재귀2 이분 탐색 정리 이분 탐색 이분 탐색이란? 정렬되어 있는 배열에서 탐색을 할 때, 탐색 범위를 반씩 나누어 탐색하는 방법 장단점 장점 : 하나하나 살펴보는 기존 탐색에 비해 훨씬 빠르다. 단점 : 정렬이 된 상태에서만 사용할 수 있어 사용하기 까다롭다. 이분 탐색 방법 데이터 배열을 정렬해준다. 정렬된 배열에서 왼쪽 끝 인덱스 : left, 오른쪽 끝 인덱스 : right를 이용해 중앙값 : mid를 찾는다. mid와 배열에서 찾고자 하는 값(target)을 비교한다. target이 나올 때까지 아래와 같은 탐색 과정을 반복한다 mid target : right를 mid-1로 이동시켜 왼쪽 구간 탐색 (left.. 2021. 11. 26. 재귀 알고리즘 내용 정리 재귀 재귀란? 재귀의 사전적 정의는 다음과 같다. 재귀(recursion)란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 재귀 호출 따라서 재귀 호출이란 함수 내부에서 함수가 자기 자신을 다시 호출하는 행위를 의미한다. 재귀 호출의 주의점은 자기 자신을 계속해서 호출하므로, 함수 내에서 호출을 일정 조건을 만족하면 중단할 수 있도록 조건이 변경될 명령문을 반드시 포함해야 한다. 재귀 호출과 반복문 비교 반복문 메모리 : 메모리 힙을 사용한다. 속도 : 빠름 무한 루프는 CPU 사이클을 반복적으로 사용한다. 코드 길이가 길어지고 변수 사용이 많아진다. (가독성이 떨어짐) 재귀 호출 메모리 : 스택 메모리를 사용한다. 속도 : 느림 무한 재귀는 스택 오버플로우를 일으킴 코드의 길이도 짧고 변수.. 2021. 9. 6. 이전 1 다음