Programming/Alogrithm3 이진 검색 이진 검색 이진 검색(Binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 오름차순으로 정렬된 데이터에서 66을 검색하는 과정이다. 66은 중앙 요소 40보다 큰 값이다. 그러므로 대상을 뒤쪽의 요소들로 좁힐 수 있다. 예제 코드 /* 이진 검색 */ #include #include int bin_search(const int a[], int n, int key) { int pl = 0; int pr = n - 1; int pc; do { pc = (pl + pr) / 2; if(a[pc] == key) /* 검색 성공 */ return pc; else if(a[pc] < key) pl = pc + 1; else pr = pc - 1; } while(pl 2021. 6. 26. 선형 검색 선형 검색 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘이다. 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search) 알고리즘이라 한다. 1. 검색할 값과 같은 요소를 찾는 경우 배열의 요소를 맨 앞부터 순서대로 검색한다. key 값을 맨 앞부터 찾고 값이 있다면 검색 종료. 2. 검색할 값을 발견하지 못하고 배열의 끝까지 간 경우 key값인 99를 맨 앞에서 부터 찾는다면 배열의 순차적으로 검색해도 없기 때문에 실패하게 된다. 배열 검색의 종료조건 1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 2. 검색할 값과 같은 요소.. 2021. 6. 26. BAEKJOON 2309 - 일곱 난쟁이 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 출력 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을.. 2021. 3. 15. 이전 1 다음
