본문 바로가기

프로그래밍기초/자료구조16

#03 순차 탐색 알고리즘, 이진 탐색 알고리즘, 이진 탐색 재귀 순차 탐색(Linear Search)맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘이기에 순차 탐색이라는 이름이 붙어있다.순차 탐색 알고리즘을 구현해보자. 배열 arr1237912212327idx0idx1idx2idx3idx4idx5idx6idx7idx8 위 배열에서 3을 찾아본다면 * 첫번째 시도1. idx0번이 3인지 확인↓ 1237912212327idx0idx1idx2idx3idx4idx5idx6idx7idx8 * 두번째 시도1. idx1번이 3인지 확인 ↓ 1237912212327idx0idx1idx2idx3idx4idx5idx6idx7idx8 * 세번째 시도1. idx2번이 3인지 확인 ↓ 1237912212327idx0idx1idx2idx3idx4idx5idx.. 2024. 3. 25.

#02-1 빅-오에 대한 수학적 접근 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n >= K에 대하여 f(n) * f(n) = 5n^2 + 100* g(n) = n^2 이 상황에서 f(n) = 12 꼭 12가 아니여도 된다 적당한수를 정하였다.) 위 가정을 대입해보면f(n) 5n^2 + 100 빅-오의 정의에 해당하는 C와 K가 3500, 12로 각각 존재하니 5*n^2 + 100의 빅-오는 n^2이다.f(n) = 5 * n^2 + 100 => O(n^2) 지금까지 전개한 내용을 빅-오의 정의와 연결시켜 보면 "두 개의 함수 f(n)과 g(n)이 주어졌을 때"=> 두 개의 함수 f(n) = 5 * n^2 + 100, g(n) = n^2이 주어졌을 때"모든 n >= K에 대하여"=> 모든 n >= 12 에 대하여,.. 2024. 3. 24.

#02 알고리즘의 성능분석 방법 복잡도(Complexity)란? 복잡도라고 말하면 이름 그대로 정말 복잡해 보이지만 그냥 어떤 알고리즘이 효율적인지를 판단하는 척도 알고리즘의 성능과 효율성을 나타내는 기준. 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다. 알고리즘에 주어진 입력T(n)을 기준으로 수행시간 혹은 메모리 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다. 복잡도를 나타내는 방법으로는 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다. 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity) 시간 복잡도(Time Complexity): 수행시간 분석결과 공.. 2024. 3. 23.

#01 자료구조(Data Structure) 와 알고리즘(algorithm) 자료구조란? 데이터를 표현하고 저장하는 방법. 프로그래밍에서 자료구조(Data Structure)는 데이터를 조직화하고 저장하는 방법이나 메모리 내에서 데이터에 효율적으로 액세스하는 방법을 제공하는 데 사용되는 방법론이다. 자료구조는 데이터를 저장, 조작, 검색 및 정렬하는 데 필요한 알고리즘을 구현하는 데 중요한 역할을 한다. 자료구조는 다양한 형태로 나타날 수 있으며, 각각의 형태는 특정한 작업이나 문제를 해결하는 데 더 나은 성능을 제공할 수 있다. 일반적으로 사용되는 자료구조에는 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등이 있다. 각각의 자료구조는 다양한 연산을 지원하며, 이러한 연산은 데이터를 삽입, 삭제, 검색, 정렬하는 등의 작업을 포함할 수 있다. 효율적인 자료구조의 선택은 프로그.. 2024. 3. 23.

이전 1 2 3 4 다음

티스토리툴바