책 정리/윤성우의 열혈 자료구조 (5) 썸네일형 리스트형 Chapter03. 배열을 이용한 리스트 구현 리스트는 크게 두가지로 구분되어 있다. º 순차 리스트 : 배열을 기반으로 구현된 리스트 º 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트 이는 구현 방법을 기준으로 한 구분이다. 따라서 이 두 리스트의 ADT가 동일하다고 해서 문제가 되지는 않는다. 리스트의 특징 º 저장 형태 : 데이터를 나란히(하나의 열로) 저장한다. º 저장 특성 : 중복이 되는 데이터의 저장을 허용한다. 이것이 리스트의 ADT를 정의하는데 있어서 고려해야 할 유일한 내용이다. 이러한 특성을 유지하려고 하다보니 순차, 연결로 나뉘는 것이다. 모든 자료구조는 내부적으로 다양한 정보를 담게 된다. 그저 데이터만 담는 게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다. 배열을 기반으로 한 .. Chapter 03. ADT 첫 번째 자료구조이다. 컴퓨터 공학에서의 추상 자료형(Abstract Data Type) 추상 자료형이란? "구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것" 지갑을 기준으로 우리는 "카드를 넣고/빼고, 지폐를 넣고/빼고, 동전을 넣고/빼고" 이러한 기능을 가졌다고 볼 수 있다. 하지만 "지갑을 열고 동전 칸 지퍼를 열고 동전을 넣고 지퍼를 닫고 지갑을 닫는다"는 이런 일련의 과정들은 생략이 되어서 이야기를 했다. 이것처럼 추상자료형은 "구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것" 으로 볼 수 있다. 추상 자료형 = 자료형 = 기능 자료형은 기능적으로 설명할 수 있지만 데이터적 관점으로 설명하기엔 너무 애매하다. 자료형이라고 하면 그와.. Chapter 02 재귀 재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고, C언어는 이렇듯 중요한 재귀를 지원하는 언어이다. 재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다. 재귀함수는 종료조건을 반드시 넣어줘야 한다. 아니면 무한루프에 빠지게 된다. (열혈 C에서 재귀함수를 설명하였으므로 나머지는 열혈 C를 참고하자.) 더보기 이것은 팩토리얼을 재귀함수로 구현한 것이다. Factorial(int num) { if (n == 0) return 0; else return n * Factorial(num-1); } 복사의 개념으로 생각하자. 실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다. 02 - 2 재귀의 활용 함수를 잘 이해했다는 기준 : 호출관계 + 호출순서 그러.. Chapter 01. 자료구조와 알고리즘의 이해 (이진탐색 알고리즘) 이진 탐색(Binary Search) 알고리즘의 소개 이진 탐색 알고리즘은 순차 탐색보다 훨 씬 좋은 성능을 보이는 알고리즘 이다. 하지만 다음의 조건을 만족하여야 한다. "배열에 저장된 데이터는 정렬되어 있어야 합니다(정렬의 기준 및 방식과는 관계없다)" 아래와 같은 배열이 있다고 가정해보자. arr = {1, 2, 5, 7, 9, 12, 21, 23, 27} 이진 탐색 알고리즘의 첫 번째 시도: 1. 배열 인덱스의 시작과 끝은 각각 0과 8이다. 2. 0과 8을 합하여 그 결과를 2로 나눈다. 3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다. 즉, 배열의 중앙에 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘의 첫 번째 시도이다. ↓ 1 2.. Chapter01. 윤성우의 열혈 자료구조(성능검사, 순차탐색) 자료구조는 수학을 기반으로한 학문이다. 그러므로 자료구조는 이론을 바탕으로 구현을 직접 경험하는 것이 올바른 공부방법이다. 구현을 바탕으로 이론을 공부하면 재대로된 공부방법이 아니므로 다시 한번 보자. 자료구조 학습에 있어서 기억할 것 두 가지 - 자료구조의 모델을 그림으로 우선 이해해야 한다. (글로만 책에서 보여주는것이 전부 라고 생각하지 말고 거기에 없는 다양한 케이스들을 그림으로 그려봐야 한다.) - 구현이 가능해야만 의미가 있는 것은 아니다. (능동적으로 코드 공부를 해라. 책에 나와있는 코드를 가리고 직접 넣던지,, 등등) Chapter 01. 자료구조와 알고리즘의 이해 01-1 자료구조(Data Structure)에 대한 기본적인 이해 이 책은 기본적으로 C언어의 문법을 알고 난 후 보는게 .. 이전 1 다음
