1. 알고리즘 2주차(이진탐색&재귀함수)
1) 이진 탐색이란?
범위의 절반을 확인하는 방식을 원하는 타겟이 나올때 까지 반복하면서 탐색을 진행하는 방법
무작위로 정렬되어 있는 배열에서는 이진 탐색을 사용할 수 없다.
- 이진 탐색과 순차 탐색 비교
- 순차 탐색
1부터 16까지 하나씩 탐색하며 원하는 타겟을 탐색한다.
시간복잡도 : O(N) - 이진 탐색
1~16의 중간값, 8~16의 중간값, 13~16의 중간값을 찾는 방식으로 원하는 타겟을 탐색한다.
시간복잡도 : O(logN)
- 순차 탐색
2) 재귀 함수란?
재귀란, 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.
즉, 재귀함수란 자기 자신을 호출하는 함수를 말한다.
재귀함수는 탈출 조건이 있어야 한다.
예시)
60부터 0까지 하나씩 숫자를 프린트 하는 함수이다. 숫자가 0보다 작으면 반복문 탈출!
3) 재귀 함수 활용
-
팩토리얼
1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것
이를 표현하는 함수는 factorial()
-
회문 검사
회문이란 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미
이를 표현하는 함수는 is_palindrome()예시 1 - 재귀함수 없이 코드 작성)
예시 2 - 재귀함수로 코드 작성)
-문자열 슬라이싱(문자열 자르는 방법)
"가나다라마바사"[0:5]=[:5] -> 가나다라마
"가나다라마바사"[0:1] -> 가
"가나다라마바사"[3:4] -> 라
"가나다라마바사"[6:0]=[6:] -> 사
4) 재귀 함수 예제
-
링크드 리스트 끝에서 k번째 값 출력하기
시간복잡도 : O(N) -
배달의 민족 배달 가능 여부
시간복잡도 : O(N) -
더하거나 빼거나
💜 오늘 느끼고 배운 점
오전 오후 : 자료구조와 알고리즘 인터넷 강의 수강
저녁 : 거북이반 실시간 강의 수강
오늘 배운 재귀함수를 이해는 했지만 아직 응용하기는 쉽지 않은 것 같다. 특히 마지막 예제가 아직 잘 이해가 안되어 계속 연구해봐야 할 것 같다.
거북이 반에서는 클래스를 복습하였는데 이제 어느정도 이해가 되는 것 같아 다행이다. 시간 날 때 백준 알고리즘 문제를 풀어봐야겠다.
