개발새발 개발자/자료 구조 (37) 썸네일형 리스트형 [자료구조] 3-2. 배열의 검색 배열의 첫번째 연산인 검색 연산에 대해 알아보자. 검색 연산이 성공하는 경우는 내가 찾는 key element가 배열에 존재하는 경우이다. 예를 들어, 배열에서 9를 찾기를 원하는데 9가 존재하므로 인덱스 2를 리턴한다. 실패하는 검색은 내가 찾는 key element가 배열에 있지 않은 경우다. 만약 2를 찾고 싶은데 존재하지 않으면 실패했다는 값을 보내야 한다. 이때, 다른 인덱스와 혼동할 수 있으므로 절대 인덱스가 될 수 없는 수인 음수 -1을 리턴한다. null을 리턴하는 것도 방법이다. 배열에는 선형 검색과 이진 검색이 있다. 1. 선형 검색 = 완전 검색, 순차 검색첫번째 원소부터 차례로 찾아보면서 동일한 원소가 있는지 확인한다. 따라서 정렬되지 않은 배열에도 사용할 수 있다. 2. 이진 검색.. [자료구조] 3-1. 리스트와 배열 카페에서 6명의 직원을 관리해야 한다면 보통은 오른쪽 처럼 표를 만들어서 출근 유무를 표시하게 될 것이다. 번호를 붙여서 관리를 하면 더 편리하다. 대부분의 어플리케이션은 내용이 한 줄로 나열되어 있다. 이런 자료들은 대부분 리스트로 관리된다. 리스트는 가장 오랫동안, 널리 사용된 자료 구조이다. 정확히 얘기하자면, 리스트는 유한한 원소들의 나열이라고 볼 수 있다. 리스트의 가장 중요한 성질은 각 원소들에 index를 부여한다는 것이다. 각 원소들은 0, 1, 2...번째로 인덱스를 갖는다. n개의 원소가 있다면 index는 0부터 n-1까지 부여된다. 어쨌거나 중요한 것은 리스트는 인덱스와 원소의 쌍이라는 것이다. 예를 들어, 11이라는 원소는 a4니까 5번째 원소가 되고, 5번째 원소를 부르면 11을.. [자료구조] 2-3. Big–O 표기법의 예 실제 Big-O 표기법은 매우 다양한 함수들로 표현된다. 이번엔 어떤 함수가 있는지 공부해보자. 'f(n)은 Big-O의 g(n)이다.'는 f(n)의 최악의 경우가 g(n)이다. 즉, ‘f(n)은 항상 g(n)보다는 좋다.’ 는 뜻이라고 공부해왔다. 이제 g(n)에 다양한 함수를 대입해 f(n)의 성능을 알아보자. 첫째, 가장 단순한 경우는 g(n)이 1인 경우다. 상수 시간 복잡도라고 부르며 f(n)=O(1)로 표기한다. 입력의 크기가 증가해도 항상 동일한 양의 메모리를 요구할 때 사용한다. 이걸 시간으로 가져오면 입력의 크기가 증가해도 항상 일정한 시간이 요구되는 시간 복잡도이다. 그래프를 보면 항상 1로 일정함을 알 수 있다. 가장 이상적인 성능이기도 하다. code 1을 보면 n이 몇이든 hell.. [자료구조] 2-2. Big-O 표기법 이 그래프를 보면 'g(n)은 f(n)의 최악의 경우다.' 라고 읽는다. 즉, f(n)은 g(n)보다 작거나 같다. 저번에 배운 점근적 분석법은 작은 입력이 아니라 큰 입력을 고려하는 것이다. n0보다 작은 범위에서는 f(n)과 g(n)의 우열을 따지는 게 의미가 없다고 생각하고, n이 n0보다 큰 영역에서만 성능을 따지기로 한다. 정리하자면, 1번과 같은 식이 성립하려면 n이 n0보다 큰 것에 대해서만 다뤄야 한다. 이것이 Big-O 포기법을 만들기 위한 두 번째 조건이다. 세 번째 조건은 조금 직관적으로 이해하기 힘들다. 이런 경우를 생각해보자. g(n)이 5n이면 n에 비례해서 5배 만큼 커질 것이다. g(n)이 10n이라면 n에 비례해서 10배 만큼 커질 것이다. 비록 5와 10이라고 하는 숫자의.. [자료구조] 2-1. 성능과 점근적 분석법 같은 소프트웨어를 써도 결과에 차이가 있다. 이것을 성능이라고 한다. 성능은 결과를 비용으로 나눈 값이다. 성능 또는 효율이라는 말은 일을 성공적으로 완수할 뿐만 아니라 소요된 시간이 적어야 적용할 수 있다. 두 가지의 전화번호 검색 앱이 있다고 하자. 이 앱들은 일단 정답을 출력해주어야 한다. 그리고 성능 또는 효율이라는 말이 적용되기 위해 전화번호를 찾는 데 걸리는 시간을 측정해야 한다.A는 0.1초, B는 1초 만에 보여준다면 빠른 시간 내에 출력하는 A가 효율이 좋은 것이다. 성능 또는 효율이란, 동일한 성과(솔루션)을 도출하기 위해 요구되는 자원의 크기를 말한다. 성능에 대한 식은 이렇게 어떠한 솔루션을 자원으로 나눈 것으로 볼 수 있다. 이 세가지 측면의 성능 중에서 어떤 것을 선택해야 할까?.. 이전 1 2 3 4 5 다음
