선형 검색(Linear Search)은 원하는 값을 찾을 때까지 처음부터 마지막까지 차례대로 검색하는 방법이다.찾고자 하는 값이 발견될 때까지 모든 자료를 순서대로 확인한다. 효율성선형 검색은 정확하지만 효율적이지 못한 방법이다.최악의 경우찾는 값이 맨 마지막에 있거나 없는 경우길이가 n인 배열에서 n번 실행시간 복잡도: O(n)최선의 경우첫 번째 시도에서 값을 찾는 경우시간 복잡도: Ω(1)선형 검색은 자료가 정렬되어 있지 않거나 추가 정보가 없을 때 유용하다. 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적이기 때문이다. 정렬 후 검색하면 더 빠르지만, 정렬 자체에 시간이 오래 걸린다는 문제가 있다. 구현숫자 배열 검색주어진 배열에서 특정 값을 찾는 코드다.#include #include ..

실행 시간프로그램을 실행하면 작업이 완료될 때까지 시간이 소요된다.간단한 프로그램은 실행 시간을 걱정할 필요가 없지만, 데이터가 많고 작업이 복잡해질수록 실행 시간은 매우 중요해진다.알고리즘의 실행 시간을 표기하는 방법을 알아보자.이 그래프는 알고리즘 실행 시간을 표현한 것이다. 문제 크기가 커질수록 각 알고리즘의 실행 시간이 어떻게 증가하는지 보여준다. Big O 표기법이런 그래프를 공식으로 표기한 것이 Big O 표기법이다.O는 "on the order of"의 약자로, "~만큼 커지는" 정도를 나타낸다.O(n):n만큼 커지는 것n이 늘어날수록 선형적으로 증가O(n/2):n이 매우 커지면 1/2은 의미가 없어짐결국 O(n)과 같음 Big O는 알고리즘 실행 시간의 상한(최악의 경우)을 나타낸다.주요 ..

검색 알고리즘메모리 구조, 자료형, 배열과 같은 기본 개념을 활용하여 검색과 정렬 문제를 푸는 알고리즘을 배워보자. 주어진 배열에서 특정 값을 찾는 방법부터 알아보자. 배열은 한 자료형의 여러 값이 메모리상에 모여 있는 구조다. 컴퓨터는 배열의 인덱스를 하나씩 접근한다.어떤 값이 배열 안에 있는지 찾으려면 배열이 정렬되어 있는지에 따라 다른 방법을 사용한다.선형 검색배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 값을 검사한다.For i from 0 to n–1 If i'th element is 50 Return trueReturn false모든 원소를 순서대로 확인하므로 정렬 여부와 관계없이 사용할 수 있다.시간 복잡도: O(n) 이진 검색배열이 정렬되어 있다면..

알고리즘이란컴퓨터는 입력을 받아 처리한 후 출력한다. 입력받은 자료를 출력 형태로 만드는 처리 과정을 알고리즘이라고 한다.알고리즘은 입력값을 출력값으로 바꾸기 위한 명령들의 순서적 나열이다. 같은 결과를 만들더라도 알고리즘에 따라 소요 시간이 달라질 수 있다.정확한 알고리즘전화번호부에서 Mike Smith를 찾는다고 가정해보자.첫 페이지를 펼친다.Mike Smith가 있는지 확인한다.없으면 다음 페이지로 넘긴다.찾을 때까지 또는 끝날 때까지 반복한다.이 알고리즘은 정확하다. Mike Smith가 있다면 언젠가는 찾을 수 있다.하지만 한 페이지씩 넘기는 방식은 매우 비효율적이다. 한 번에 두 페이지를 넘기면? 빨라지지만 원하는 페이지를 건너뛸 수도 있다. 여전히 가장 효율적인 방법은 아니다. 효율적인 알고..