1. 자료구조와 알고리즘

본 카테고리에 게시되는 글은 제가 편입을 준비하며 정리한 자료들입니다.

참조한 서적은 다음과 같습니다.

1. C언어로 쉽게 풀어 쓴 자료구조. 천인국·공용해·하상호. 생능출판사

2. 윤성우의 열혈 자료구조. 윤성우. 오렌지미디어

학부 편입 면접을 위해 준비한 자료이기 때문에 지나치게 긴 코드 또는 너무 깊은 내용은 배제했습니다.

---

1. 자료구조와 알고리즘

(1) 자료구조와 알고리즘의 개념

- 자료(data)

- 자료구조 : 데이터를 표현하고 저장하는 방식 ex) 그래프

- 알고리즘 : 주어진 문제를 처리하는 단계적인 절차 ex) DFS알고리즘(그래프 탐색 알고리즘)

※ 자료구조와 알고리즘은 밀접한 관계가 있다. 즉, 원하는 작업을 효율적으로 수행하기 위해서는 적절한 알고리즘을 선택해야 하며, 그에 적합한 자료구조를 선택하는 것이 중요하다.

(2) 알고리즘의 조건

1) 0개 이상의 입력이 존재해야 한다.

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

3) 명백성 : 각 명령어는 의미가 명확해야 한다.

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

5) 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다. ex) 0으로 나누는 연산X

(3) 알고리즘 기술 방법

1) 자연어 ⇒ 자연어는 다의성이 높으므로 명백성이 떨어질 수 있다. 각각의 단어의 정의가 명확해야 한다.

2) 흐름도(flowchart) ⇒ 알고리즘이 복잡해지면 기술이 힘들 수 있다.

3) 유사 코드(pseudo-code) ⇒ 자연어와 프로그래밍 언어의 중간 형태이다.

프로그래밍 언어의 명백성과 자연어의 가독성을 적절히 취한 방식으로,

알고리즘 기술에 매우 적합한 표기법이다.

4) 프로그래밍 언어 ⇒ C언어 등의 프로그래밍 언어를 이용해 기술하는 방법이다.

명백성이 높지만 유사 코드에 비해 가독성이 떨어진다.

※유사 코드 예시 ArrMax(A,n)   tmp ← A[0] // 유사 코드에서 ‘할당/대입’은 =가 아닌 ‘←’이다. for i ← i to n-1 do // for A to B do : A에서 B까지 반복하라 if tmp < A[i] then // if A then B : 만약 A면 B를 수행하라 (영어 if~then구문이랑 똑같다) tmp ← A[i]; return tmp;

(3) 알고리즘 ADT(추상 데이터 타입)

1) 데이터 타입 : 데이터의 집합(객체(object)들의 집합) + 연산의 집합(operation의 집합)

   ex) int : 데이터 집합 {…, -2, -1, 0, 1, 2 …}

            연산의 집합 {+,-,/,*,%}

   ex2) 트리의 Node 데이터 타입 : 데이터 집합 {struct Node형 데이터1, struct Node형 데이터 2 등등..}

                                      연산 집합 {MakeTreeNode, GetLeftSubTree 등등..}

- 데이터 타입은 ‘정의’ + ‘구현’으로 완성됨.

   ex) 트리 구성을 위한 노드 구조체와 함수들의 기능 정의 + 실제 C 언어로 구현

2) 추상 데이터 타입 : 데이터 타입의 ‘구현’은 제외하고, ‘데이터 타입의 정의’만 분리해낸 것. 즉, 객체와 연산이 무엇(what)인지만 정의함. 어떻게(How) 컴퓨터에 구현하는지는 정의하지 않음.

tip) 비유하자면 ADT는 전자제품의 사용설명서 같은 것이다. 전자레인지를 사용하기 위해 그걸 만드는 방법까지 알 필요는 없다. 사용자는 ‘이 공간은 음식물을 넣는 공간이다’, ‘데우기 버튼을 누르면 작동이 시작된다’만 알고 있으면 된다.

- ADT는 구현과 별개로 기술된다. 즉, ADT상에 같은 연산이라도 다르게 구현할 수 있다.

- ADT객체 정의(object정의) + ADT연산 정의(operation정의)로 이루어진다.

- 객체 지향 언어에 큰 영향을 주었다. (클래스 개념이 ADT를 나타낸다.)

   ADT의 객체 : ‘클래스의 멤버 변수’로 구현

   ADT의 연산 : ‘클래스의 멤버 함수’로 구현

   (C에서는 구조체를 이용해 완벽하지는 않지만 구현할 수는 있다.)

- 객체 지향 언어에서는 private나 protected키워드를 이용해 ADT내부 데이터로의 접근을 제한할 수 있다. 즉, 필요한 정보만을 추려서 제공하는 기능뿐만 아니라, 캡슐화를 통해 내부 데이터를 은닉하는 기능도 수행할 수 있다.