helloahram

1920 수 찾기 문제를 풀다가 이분 탐색이 분류에 있길래 정리해본다 이분 탐색 Binary Search 정렬되어 있는 리스트 또는 배열에서 탐색 범위를 절반씩 좁혀가며원하는 값 Target 의 존재 위치/ 존재 여부를 찾는 알고리즘  이분 탐색 특징 단계마다 탐색 범위를 반으로 나누기 때문에 시간 복잡도는 O(logN) 이다 단, 배열이 정렬되어 있어야만 사용 가능하다는 단점이 있다  Quick Sort 와 유사한 접근 방법을 사용해서, Pivot 대신 mid 값을 계산하여left 로 탐색 범위의 왼쪽 경계, right 로 탐색 범위의 오른쪽 경계를 설정하고찾는 대상과 mid 값을 비교하여 left, right, mid 값을 변경하며 범위를 줄인다 * Quick Sort 공부 자료 이분 탐색 코드백준 ..

09/10 TUE 퀴즈를 대비한 퀵 정렬 추가 공부  퀵 정렬 Quick Sort분할 정복 알고리즘의 대표 예시  Pivot 값을 중심으로 작은 값/ 큰 값을 계속 나누기 때문에 재귀 함수임 방식1) 르모토 - 월 같은 걸 추가한다 (이건 나중에 추가 공부하고 해주신대)2) 호어 Hoare - Pivot 으로 판단한다 (Left + Right) // 2 를 Pivot 으로 설정하고, Pivot 기준으로 왼쪽은 작은 값, 오른쪽 큰 값 비교하여 서로 반대인 경우 Swap 첫번째 비교가 완료되면 Pivot 기준 왼쪽/ 오른쪽으로 또 쪼개서 Pivot 만들어정렬을 완료한다 + Pivot 을 arr[0] 에 줘도 되고, 어디에 주던 본인 마음임+ while 문 안에서 Pivot 의 위치는 바뀔 수 있지만 Piv..

분할 정복 Divide and Conquer큰 문제를 작은 문제들로 나누어 각 작은 문제를 해결한 후, 그 해를 결합하여 원래 문제를 해결하는 방법  기본적으로, 크고 복잡한 문제를 더 풀기 쉬운 작은 문제들로 나누고각각을 해결한 후 다시 합쳐서 문제를 해결하는 개념에서 출발한다 1. 분할 Divide 큰 문제를 더 작은 하위 문제로 나눈다2. 정복 Conquer 각 하위 문제를 재귀적으로 해결한다, 하위 문제가 충분히 작아지면 직접 해결    (하위 문제의 크기가 더 이상 나눌 수 없는 단위에 이르면 재귀 호출을 멈추고 해결)3. 결합 Combine 해결된 하위 문제들을 결합하여 원래 문제에 대한 해답을 구한다 * Divide 를 설계하면 Conquer 과정이 자동으로 쉬워지기 때문에 문제를 어떻게 나..