본문 바로가기

Algorithm

 (4)
[알고리즘 문제해결 전략] 6장 무식하게 풀기 6.1 도입 Brute - Force : 모든 경우를 나열해서 답을 찾는 방법 ex) 두 점 사이의 최단 경로 1차원 좌표 -7, -3. 1, 9 이 존재 할 때 가장 최단거리를 구해보자 (-7, -3), (-7, 1), (-7, 9), (-3, 1), (-3, 9), (1, 9) 총 6개의 케이스 나온다. 이렇게 모든 케이스를 나열하여서 답을 찾는 것을 완전탐색이라고 함 그리고 열명의 학생을 한줄로 세우려고 한다 서로 사이가 안좋은 학생이 존재하고 두 학생은 서로 붙여서 줄 세울수 없다 이 경우 가장 쉬운방법은 모든 학생들 줄 세우는 방법을 구하고 각 경우 사이가 안좋은 붙어 있는지 확인하여 빼주면 조건에 맞게 줄을 세울수 있는 방법을 구할 수 있다 6.2 재귀 호출과 완전 탐색 재귀호출 재귀함수란 자..
[알고리즘 문제해결 전략] 5장 알고리즘 정당성 증명 이 파트는 추후 다시 정리하여 공부가 필요하여 글쓰기 보류
[알고리즘 문제해결 전략] 4장 알고리즘의 시간 복잡도 분석 4.1 도입 반복문이 시간복잡도를 지배한다. 알고리즘 수행시간은 반복문이 수행되는 횟수로 측정한다. -> 이유 : 입력의 크기가 커짐에 따라 수행 시간도 상승 예제 1 ) 주어진 배열에서 가장 많이 등장하는 수를 찾기 (수행 시간 n^2) int majority1(const vector &A) { int n = A.size(); int majority = -1, majorityCount = 0; for(int i=0; i
[Algorithm] 이분 탐색 (Binary Search) 오늘은 이분 탐색에 대해서 글을 써보려고 합니다. 이분 탐색이란게 뭐냐면 이분은 일단 두개로 분할한다는 의미이고 탐색은 말 그대로 내가 원하는 자료를 찾기 위해 탐색 한다는 의미입니다. 간단한 예시를 통해 이분 탐색의 동작 과정을 살펴 봅시다 아래 그림과 같은 배열의 크기가 9이고 데이터는 다음과 같이 나열되어 있다고 합시다 여기서 우리가 찾아야 할 수는 23(index : 5)입니다. 탐색 방법은 여러가지가 있습니다 가장 쉬운 방법으로는 index 0에서 8까지 순차적으로 탐색하는 방법이 있을 것입니다. 순차 탐색의 경우 하나씩 다 방문할 것이고 결국 5번째에 23이라는 숫자를 찾게 될 것입니다 시간 복잡도 측면에서 바라보면 O(n)의 시간이 나오겠죠 하지만 이분 탐색의 경우 2번만에 찾을 수 있습니다..

티스토리툴바