💡 분할정복(Divide-and-Conquer) - 해결하기 쉽도록 문제를 여러개의 작은 부분으로 나누고 나눈 문제를 각각 해결하는 방식(하양식 방식, top-down) 💡 이진검색 - 찾고자 하는 원소 x 와 정렬된 배열에서 배열의 중간에 위치한 항목과 일치한지 비교 - 일치하지 않을 경우, x가 중앙보다 작으면 왼쪽, 크면 오른쪽 반쪽을 선택해 다시 해당 반쪽의 중앙을 선택 (반쪽 배열에서 재귀적으로 이분 검색) //이진검색 알고리즘 ✔ 최악의 경우 시간복잡도 분석 - n이 2의 제곱일 때와 아닐때로 나눌 수 있지만 자세한 설명은 생략하고 W(n) = ⌊logn⌋ +1 *n이 크면 1은 무시 - 귀납적 증명
알고리즘/알고리즘 이론
💡알고리즘 이란? - 주어진 문제를 논리적으로 해결하는 과정 - 분석을 통해 효율성 파악, 효율성을 정량화 - 알고리즘은 프로그래밍 언어에 독립적 (언어에 따라 구현 문법은 좀 다르겠지만 원리는 동일하게 동작) ✔알고리즘의 따라 효율이 달라질 수 있다? 예1) 순차검색 vs 이진검색 - 순차검색은 처음부터 찾고자 하는 원소가 나올 때까지 진행 -> 원소가 가장 마지막에 있으면 시간 오래 걸림 - 이진검색은 중간에 있는 원소부터 시작해 찾고자 하는 원소보다 큰지 작은지에 따라 오,왼으로 이동해 다시 중간 원소와 비교 -> 비교적 시간 단축 예2) 피보나치항 계산의 재귀 vs 반복 - 반복문을 사용해 계산된 항의 개수는 n+1 - 재귀함수를 사용해 계산된 항의 개수는 2^(n/2) (단, n>=2) ex) ..
티스토리 블로그 첫 개장!!! 코딩테스트를 위해 백준 문제 풀이와 알고리즘 개념 공부 한 것들을 업로드할 예정~! 알고리즘은 이 로드맵에 따라 차례차례 공부하며 지워나갈 것이다. 백준은 동기들과 스터디를 만들어서 진행중이다. https://github.com/daeunkwak/Algori-m/tree/main/gangmini/Class2%2B 나에게 티스토리 블로그를 전수해준 분❤ 이분의 블로그 스타일을 그대로 사용했다!! https://daeun-rithm.tistory.com/
