C 언어로 쉽게 풀어 쓴 자료구조 1장 자료구조와 알고리즘

자료구조: 일상생활에서의 사물의 조직화

- 데이터를 조직화하고 저장하는 법

-테이터를 효율적으로 저장, 검색, 삽입, 삭제

 

여러 자료구조의 비교

1) 스택: 그릇을 쌓아서 보관하는 것 (후입선출 방식, 맨 마지막에 들어간 자료가 가장 먼저 빠져나옴)

2) 큐: 마트 계산대의 줄 (선입선출 방식, 가장 먼저 들어간 자료가 가장 먼저 빠져나옴)

3) 리스트: 버킷 리스트, 데이터의 묶음

4) 사전: 영어사전, key와 value로 저장

5) 그래프: 지도, node와 edge

6) 트리: 컴퓨터의 디렉토리 구조, 나무를 거꾸로 뒤집어놓은 구조, root가 가장 위에 존재

 

프로그램은 크게 자료구조와 알고리즘으로 구성돼 있다. ; 명령문의 집합

여기서의 자료구조는 일상생활에서의 사물의 조직화를, 알고리즘은 컴퓨터로 문제를 풀기 위한 단계적 절차를 의미한다. 

 

알고리즘의 조건:

1) 입력: 0개 이상의 입력이 존재하여야 한다. -> 입력이 필수적이지는 않다.

2) 출력: 1개 이상의 출력이 존재하여야 한다.

3) 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.-> 컴퓨터가 일을 하기 때문에

4) 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다. 

5) 유효성: 각 명령어들은 실행 가능한 연산이어야 한다.

 

알고리즘의 기술 방법: 

알고리즘은 1. 자연어 2. 흐름도 3. 의사 코드 4. 프로그래밍 언어 등 표현할 수 있는 방법이 여러 가지이지만 각각 장단점을 갖고 있음에 주의하자. 

 

1. 자연어:

인간이 읽기 쉽지만 프로그래밍 할 때 단어를 정확하게 정의하지 않으면 의미 전달이 모호해질 위험이 있다. 

기본적으로 길이가 길고 개발자의 성향에 따라/보는 사람에 따라 다르게 이해될 가능성이 있다.

 

2. 흐름도:

flow chart

 

시각화했기 때문에 이해가 쉬울 수 있음, 간단한 로직이 아닌 이상 조건이 케이스별로 나누어져 있다면 복잡해짐.

 

3. 유사코드/의사코드/pseudo-code

알고리즘 기술에 가장 많이 사용

프로그래밍 언어가 가지는 특징을 최소화하고 알고리즘을 최대한 표현

 

4. C로 표현된 알고리즘

알고리즘의 가장 정확한 기술이 가능

프로그래밍 언어의 특성을 살리느라 읽어내야 할 코드가 더 많게 느껴질 수 있음

 

자료형: 데이터의 집합과 연산의 집합

 

추상 데이터 타입(ADT:Abstract Data Type):

-데이터 타입을 추상적으로 정의한 것 (필요한 정보만 가지고 기술)

-데이터나 연산이 무엇인가는 정의되지만 어떻게 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.

-what을 정의하고 how는 정의하지 않는 기법. 

-객체와 연산:

   객체: 추상 데이터 타입에 속함

   연산: 객체들 사이의 연산, 추상 데이터 타입과 외부를 연결하는 인터페이스(결합규칙) 역할

 

추상화: 어떤 시스템의 간략한 기술 또는 명세 (시스템의 핵심적인 구조나 동작에만 집중)

 

알고리즘의 성능 분석 기법:

1)수행 시간 측정: 실제로 구현, 동일한 하드웨어 사용 (같은 환경)

2)알고리즘의 복잡도 분석: 주요 연산이 수행된 횟수를 책정해서 비교, 직접 구현할 필요는 없음, n의 함수

 

복잡도의 종류에는 시간 복잡도와 공간 복잡도(메모리에 공간을 얼마나 차지할 지)가 있지만 책에서는 시간 복잡도를 다루고 있다.

 

빅오 기법: 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다는 이론에 근거. 기본적으로 상한을 의미한다. 

빅오메가 기법: 함수의 하한을 표시

빅세타 기법: 함수의 상한과 하한을 동시에 표시