해나의 컴공생존기

앞으로 자주 쓰일 자료구조들을 한번 복습해볼 것이다. 1. Array 동일한 type의 데이터를 연속된 주소에 저장하는 자료구조이다. 갯수를 미리 정해야하고 중간에 용량을 늘리기는 불가하다. 인덱스만 알면 데이터에 접근하기 슂다는 장점을 가지고있다. ex) A[7] = 400 + 7*4 = 428 Search, Delete, Insert 입장에서 효율이 좋지 않다. sorting이 되어있다면 Binary Search O(log N)가능하다. 2. Stack insertO(1) / DeleteO(1)만 제공한다. Search x Last in, First out 수식 계산에 사용 ex (3+7)*2 + (6-3)/5 3. Queue insert O(1) / Delete O(1)만 제공한다. Search x..

1. Binary Search 이진탐색트리 코드이다. l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다. 기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다. 처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다. 탐색은 l과 r이 만나면 종료된다. m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다. 1) n=2 l=0, r=1, m=0 으로 모두 탐색 가능하고 2) n-3 l=0, r=2, m=1 으로 모두 탐색 가능하다 a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다. 왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 ..

Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있다. 사용 : 변화가 없거나 드문 자료 배열에서 가장 흔히 쓰이는 search 방법은 linear search 이다. 이는 하나하나 다 읽어보며 찾는 방법이고 모두 다 읽어봐야해서 크게 효율적이지 않다. 또 다른 방법은 Binary Search 이다. 이 방법은 sorting 되어있는 상태에서만 사용가능하다. 기본적인 로직은 절반을 확인하고 그의 절반..절반.. 을 확인하는 방법이다. 코드로 나타내면 int search(int a[], int ..