알고리즘

[이것이 코딩 테스트다 with Python] 이진탐색

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 7 이진 탐색 실전문제 7-1 이진 탐색 189 문제 주어진 입력값에 대해서 이진탐색 진행해 인덱스를 출력하자 입력 조건 숫자의 갯수와 찾아야 할 숫자를 입력받고 다음줄에서 숫자 배열을 입력받는다 출력 조건 찾은 곳은 인덱스를 출력하고 없다면 원소가 존재하지 않는다는 문구를 출력한다 입력 예시 1 10 7 1 3 5 7 9 11 13 15 17 19 출력 예시 1 4 입력 예시 2 10 7 1 3 5 6 9 11 13 15 17 19 출력 예시 2 원소가 존재하지 않습니다. ✔ Solution - 재귀함수 def binary_search(array, target, start, end): if start > end: return None # 중간..

이진 탐색 알고리즘

이진 탐색(Binary Search) 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 시간 복잡도는 $O(logn)$을 가진다. ✔ 이진 탐색 과정 1. 데이터 집합(배열)의 중앙 요소를 선택합니다. 중간값 : 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 여기서 target = 9 로 한다. 2. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다. 중앙값의 7과 비교하여 9가 더 크기 때문에 왼쪽을 지우고 오른쪽에서 중앙값을 구한다. 다시 구한 중앙값은 10이다. 3. 위의 2번을..

[이것이 코딩 테스트다 with Python] 위에서 아래로

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 6 정렬 실전문제 6-2 위에서 아래로 178p 문제 하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다. 입력 조건 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1

[이것이 코딩 테스트다 with Python] 성적이 낮은 순서로 학생 출력하기

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 6 정렬 실전문제 6-2 위에서 아래로 180p 문제 N명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다. 입력 조건 첫 번째 줄에 학생의 수 N이 입력된다. (1