디노문경

배열은 자료 구조의 하나로, 데이터를 1열로 나열한 것입니다. 앞 절의 리스트와는 대조적으로 데이터에 접근하기는 쉽지만 추가나 삭제에 시간이 걸립니다. 이것은 '[자료 구조] 자료 구조란?'에서 설정한 가나다순의 전화번호부와 비슷한 구조입니다. - 책 알고리즘 도감 배열에서 데이터는 연속된 메모리 영역에 순서대로 저장됩니다. 연속된 영역에 저장돼 있기 때문에 인덱스를 사용해서 메모리의 주소를 계산할 수 있습니다. 따라서 각 데이터에 바로 접근할 수 있습니다. 이것을 '임의 접근(random access)'이라고 합니다. 예를 들어, 'Red'에 접근하고 싶다고 합시다. 이 때 리스트의 경우는 앞에서부터 포인터를 따라 가야 합니다. 하지만 배열의 경우는 a[2]라고 지정하기만 하면 직접 'Red'에 접근할..

리스트(list)는 자료 구조의 하나로, 데이터를 일직선으로 나열한 형태를 가지고 있습니다. 데이터 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸립니다. - 책 알고리즘 도감 리스트에서는 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며, 일반적으로 떨어진 영역에 흩어져서 저장됩니다. 또한, 각 데이터에는 '포인터(pointer)'가 있으며, 다음 데이터의 메모리 위치를 가리킵니다. 흩어져 저장돼 있으므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있습니다.(이것을 순차 접근 또는 시퀀셜 엑세스(sequential access)라고 합니다.) 예를 들어, 'Red'에 접근하고 싶은 경우는 먼저 'Blue'에 접근한 다음 포인터를 따라 'Yellow'에 가야만..

데이터의 순서나 위치 관계를 정한다. 컴퓨터 안에서 데이터는 메모리에 저장되고, 메모리는 아래 그림과 같이 상자가 일렬로 나열된 형태를 하고 있습니다. 그리고 하나의 상자 안에 하나의 데이터를 저장합니다. 이때, 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계 등을 정하는 것이 '자료 구조'입니다. 전화번호부의 자료 구조 이해하기 쉽게 전화번호부에 대해 생각해봅시다. 그리고 우리가 직접 종이에 적으면서 전화번호부를 관리한다고 해봅시다. 첫 번째 방법으로는 단순하게 아래에 이어서 추가하는 방법이 있을 것입니다. 하지만, 만약 '김짱구'라는 사람을 찾아 전화하고 싶을 때, 짱구를 찾으려면 시간이 오래 걸릴 것입니다.(전화번호부에 사람이 많이 있을수록 오래 걸리겠죠?) 두 번째 방법으로는 가나다순으로 ..

삽입 정렬(insertion sort)은 수열의 왼쪽부터 순서대로 정렬하는 방식입니다. 작업하다 보면 좌측에는 정렬이 끝난 숫자가 오게 되고 우측에는 아직 확인하지 않은 숫자가 남게 됩니다. 우측의 미탐색 영역에서 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식입니다. -책 알고리즘 도감 위의 막대기들을 삽입 정렬을 사용해 오름차순으로 정렬해보겠습니다. 1. 처음에는 왼쪽 끝의 숫자(20)를 정렬이 끝났다고 간주합니다. 2. 아직 정렬되지 않은 숫자 중에서 왼쪽 끝에 있는 숫자(10)을 꺼내서 왼쪽에 정렬된 숫자와 비교해서 꺼낸 숫자가 더 작으면 자리를 바꿉니다. 20 > 10 이므로 20과 자리를 바꿉니다. 이제 숫자 10과 20은 정렬이 된 것으로 간주합니다. 따라서 정렬되지..

선택 정렬(selection sort)에서는 '수열 중에서 최소값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복합니다. 수열 중에서 최소값을 찾을 때는 선형 탐색을 사용합니다. -책 알고리즘 도감 위와 같이 서있는 막대기들을 선택 정렬을 사용해 오름차순으로 정렬해보겠습니다. 1. 선형 탐색을해서 최소값을 찾습니다.(여기서는 10) 그리고 왼쪽 끝에 있는 20과 자리를 바꿉니다. (만약, 최소값이 이미 왼쪽끝에 있다면 그대로 둡니다.) 그리고 이제 제일 왼쪽에 있는 10은 신경쓰지 않습니다. 2. 이제 남은 4개의 숫자중에서 최소값을 찾아서 20과 자리를 바꿉니다. 여기서는 4개의 숫자중 최소값이 20이므로 그대로 둡니다. 그리고 이제 정렬된 20도 신경쓰지 않습니다. 3. 이제 남은 3개의 숫자..

버블 정렬(bubble sort)은 '오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복합니다.' 오른쪽부터 왼쪽으로 숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해서 버블이라고 합니다. -책 알고리즘 도감 위의 그림처럼 생긴 막대기들을 버블 정렬을 이용해 오름차순으로 정렬한다고 해봅시다. 오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복한다고 했죠? 오른쪽부터 좌우 숫자를 비교해서 오른쪽 숫자가 작으면 위치를 바꿔줍니다. 1. 40과 50을 비교한다. 40이 더 작으므로 50과 위치를 변경한다. 2. 30과 40을 비교한다. 30이 더 작으므로 위치를 변경하지 않는다. 3. 10과 30을 비교한다. 10이 더 작으므로 위치를 ..