C/자료구조와 알고리듬16 Chapter 04. 배열(Array) 0. 배열의 특징 - 배열은 사용할 메모리 크기를 고정해서 선언해야 함. 선언 후에는 절대 변경 불가능함. 즉, 추가/축소가 불가능함. - 선언된 메모리는 연속적으로 할당됨. 1. 기본 코드 - 앞으로 연재될 모든 자료구조는 Clang C89 기준의 코드들로 이루어짐. 따라서, C가 가능하다면 모든 곳에서 될듯. - C 스타일의 배열을 그대로 사용하기엔 메모리 스탬프가 걱정됨. - 분할 컴파일을 통해서 배열을 아에 다른 파일에다가 정적으로 선언하고, 메모리 스탬프를 막을 정적 변수를 하나 더 선언 하고자 했음. - 그마저도 한 문제에 여러 개의 배열이 필요할 수 있어서, 그냥 정적 배열이 아닌 구조체를 사용함. 뭔가 아주 살짝의 문법 어필도 가능할듯? #define _CRT_SECURE_NO_WARNIN.. 2021. 11. 1. Chapter 03. 정렬 Chapter 03. Sort Algorithm 3.0 정렬 알고리듬 3.0-0 정렬 알고리듬 - 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리듬 - 정렬하는 이유 좀 더 효율적인 알고리듬을 사용하기 위해서 사람이 읽기 편하도록 등등 - 입력 데이터는 일반적으로 배열 같은 자료 구조에 저장 아무 위치로의 임의 접근이 용이함 cf. 링크드 리스트를 사용하면 처음 혹은 끝부터 차례로 훑어야 함. - 줄 세우는데 흔히 사용하는 순서: 숫자 순서, 사전 순서 정렬 방향: 오름차순, 내림차순 - 다양한 정렬 알고리듬이 있음 시간 복잡도 차이 메모리 사용량 차이 안정성(stability) 차이 직렬 Vs. 병렬 차이(이 과목에서는 직렬 정렬 알고리듬만.) 3.0-1 정렬 알고리듬의 안정성 - 안전성(.. 2021. 6. 18. Chapter 02. 탐색 2.1 선형 탐색 2.1-1 탐색 알고리듬 Def) 탐색 알고리듬(Search Algorithm) 어떤 자료구조 안에 저장되어 있는 자료를 찾아오는 알고리듬. Note) 매우 다양한 알고리듬이 여기 포함됨. ex. 배열에서 제일 큰 값 찾기 데이터 베이스에서 레코드 하나 읽어오기 배낭(knapsack) 문제 등 Note) 대표적인 탐색 알고리듬 1. 선형 탐색 2. 이진 탐색 3. 해시 기반 탐색 2.1-2 선형 탐색 Def) 선형 탐색(Linear Search) 자료구조의 모든 자료를 순서대로 훑어가며 원하는 자료를 찾는 알고리듬. Note) 기초문법 배열편에서 많이 해보았기 때문에, 관련 예제는 생략함. 2.2 이진 탐색 2.2-1 이진 탐색이란, Note) 업-다운 게임을 생각 해 보자. 당연히 우.. 2021. 6. 17. Chapter 01. 자료구조와 알고리듬 1.1 자료구조와 알고리듬 1.1-1 자료구조란, Def) 자료구조(Data Structure) 자료(data)를 저장할 수 있는 공간을 의미함. 각 자료구조마다 특징이 있어서, 때에 따라 잘 골라서 자료를 저장해야 빠르게 접근할 수 있음. Note) 자료구조의 종류 크게 선형 자료구조와 비 선형 자료구조로 나뉨. 선형 자료구조: 배열/가변 배열/스택/큐/해쉬 테이블 비선형 자료구조: 링크드 리스트/트리/그래프/힙 1.1-2 알고리듬이란, Def) 알고리듬(Algorithm) 알고리듬이란, 어떤 문제를 해결하는 명백한 방법 "어떤 문제"란 문제가 특정되어 있다는 것. 임의의 문제를 풀 수 있는 것이 아님. "명백한 방법"이란, 방법이 모호해서는 안된단 것. Note) 알고리듬의 예 - 마치 라면 끓이기와.. 2021. 6. 17. 이전 1 2 3 4 다음
