[Panda] 0. 알고리즘과 자료구조

알고리즘이란?

컴퓨터 프로그래밍

현대 컴퓨터의 작동 순서는 다음과 같다.

1. 메모리에서 읽기
2. 상태 기억 회로(레지스터)에서 상태를 입력받기
3. 규칙표 논리회로(CPU)에서 연산 실행
4. 메모리에 쓸 내용과 상태 기억 회로에서 쓸 내용 출력

이 과정은 튜링 기계 작동 과정과 완전히 동일하다. 그래서 현대의 컴퓨터를 튜링기계라고 할 수 있다.

 

튜링 기계와 컴퓨터

튜링 기계란 앨런 튜링(Alan Turing)이 독일의 수학자 데이비드 힐버트(David Hilbert)제기한 "모든 수학 문제를 풀 수 있는 알고리즘이 있는가?"라는 질문에 답하기 위하여 1936년에 소개한 개념이다.

튜링은 모든 수학 문제는 기계로 형상화할 수 있고 가장 기본적인 동작의 합으로 표현할 수 있다고 생각했다. 입력 값(테이프), 제어 장치, 입출력 헤드 이 3개 장치와 현재 상태, 읽은 기호, 다음 상태, 쓸 기호, 움직일 방향의 5가지 요소로 구성된 기계에 의해 수학문제를 풀 수 있다고 생각했다.

튜링 기계는 컴퓨터와 아무 상관없이 개발된 것이지만 앞에서 언급한 구성 개념 3가지, 즉 입력 값, 제어 장치, 입출력 헤드는 컴퓨터를 구성하는 3대 요소가 되었다.

컴퓨터의 실질적인 회로는 Boolean 대수를 이용한 디지털 논리 회로를 이용해 판정, 선택, 응답, 기억의 4가지 종류 회로고 구성되었다. 트랜지스터는 전체 회로의 모양을 작고, 빠르게 만들었다.

튜링기계를 이용하여 구성된 컴퓨터는 작동하기 위해 분석, 프로그래밍, 코딩의 단계를 거쳐야 한다.

 

프로그래밍, 코딩, 분석

프로그래밍은 프로그램을 기획하거나 작성하는 과정이다.
컴퓨터 프로그래밍이란, 컴퓨터로 수행해야하는 작업을 단위 작업으로 분류하고 처리 순서(알고리즘)을 정하는 과정을 말한다. 프로그래밍이란 단어 자체는 컴퓨터 언어가 아니다.

코딩은 알고리즘을 컴퓨터가 알 수 있는 언어로 바꾸어 작성하는 것이며 컴퓨터에서 코딩은 프로그래밍된 단위작업의 처리 절차를 특정 언어로 변환하는 작업을 말한다.

 

프로그래밍은 주어진 과제를 단위 작업으로 분리하고 이것의 처리 순서를 정하는 과정이다. 여기서 주어진 과제를 단위작업으로 분리하는 것을 분석이라한다.
단위 작업이란 개발자가 프로그래밍을 할 수 있는 최소 단위이다. 더 이상 쪼갤 시 의미가 없어지는 경우가 해당된다. 예를 들어 로그인 작업을 ID를 입력하는 것과 password로 나누는 것은 의미가 없으므로 로그인 과정을 단위 작업이라 할 수 있을 것이다. 데이터 타입 선언, 데이터 입출력, 데이터 조작 등 모두 단위 작업의 예시이다.

 

프로그래밍을 잘 하기 위해서는 주어진 과제를 단위 작업으로 나누고, 나눈 단위 작업의 처리 절차를 효과적으로 기술하는 것이 중요한데 이 과정을 알고리즘이라고 한다.

 

 

 

알고리즘 개념

알고리즘의 정의

알고리즘(Algorithm)은 주어진 문제를 해결하기 위한 절차로서, 정해진 입력에 정해진 출력이 나와야하고 무한히 반복되어서는 안된다.
컴퓨터에서 알고리즘은 주어진 문제를 단위 작업으로 나누고 문제를 해결하기 위한 처리 순서를 정하는 과정으로 이 과정이 무한이 반복되어서는 안된다.

즉 알고리즘은 컴퓨터 프로그램을 설계하는 과정이다

 

알고리즘의 종류

알고리즘은 모든 컴퓨터 프로그램에서 사용된다. 여러 컴퓨터 프로그램에서 공통적으로 사용하는 대표적인 알고리즘을 정리하면 다음과 같다.

1. 정렬(Sort): 한 줄로 모여 있는 데이터를 오름차순이나 내림차순으로 배치하는 방법
2. 검색(Search): 데이터 중에 원하는 것을 찾아내는 방법
3. 문자열 패턴 매칭(SPM; String Pattern Matching): 주어진 문자열에서 지정한 문자열과 일치하는 부분을 찾아내는 방법
4. 계산(Calculation): 수학이나 공학의 문제 해결을 위한 방법

 

 

자료구조란?

컴퓨터의 데이터 취급 방법

 

컴퓨터는 0과 1만을 다룰 수 있기 때문에 다룰 수 있는 기본형의 종류는 숫자, 문자 , T/F 이 3가지이다. 숫자는 몇 byte까지 한 개의 숫자로 계산할 것이간에 따라 int, float, short 등으로 구분해 인식하고 문자는 한 byte의 0과 1 조합을 아스키코드 값에 해당하는 문자로 인식하고, T/F는 0과 1로 인식한다. 사용자는 이 세 기본자료형을 여러 개 묶어서 새로운 자료형을 선언할 수 있으며 이 것을 **사용자 정의 자료형**이라 한다.

사용자 정의 자료형의 종류에는 자료형이 동일한 것을 여러 개 모아서 처리하는 뱅려과 다른 데이터 형을 여러 개 모아서 처리하는 구조체, 그리고 구조체에 처리하는 함수를 포함하는 클래스로 나누어 볼 수 있다.
코딩을 하기전에 사용할 자료형을 정의하는 것은 필수적인 과정이다.

 

 

자료구조

자료구조의 정의 및 종류

컴퓨터는 근본적으로 자료를 입력받고, 저장하고 조작하며, 필요시 원하는 형태로 꺼내서 원하는 곳에 보여주는 역할을 하는 기계이다.

자료구조(Data Structure)는 컴퓨터가 다루어야하는 자료가 많은 경우에, 이것을 다루는 방법으로 알고리즘을 구현하는데 사용한다. 자료구조를 물리적으로 구현하는 방법은 리스트와 연결 리스트(Linked List) 두 가지가 있다.

자주 사용되는 자료구조의 종류는 다음과 같다.

• 리스트
• Linked 리스트
• 배열
• 스택
• 큐
• 데크
• 트리와 힙
• 그래프

List는 각 데이터를 연이어 저장하는 기술이고 Linked List는 각 데이터를 임의의 위치에 저장하고 서로 연결하는 기술이다.
스택, 큐, 데크, 트리는 리스트로도 구현할 수 있고, Linked 리스트로도 구현할 수 있다. 큐의 경우 리스트, Linked 리스트 외에도 힙(heap)을 이용해서 구현하기도 한다. 힙(heap)을 사용하면 우선순위 큐(priority queue)라는 자료구조를 구현할 수 있다. 이는 큐의 데이터들이 우선순위에 따라 처리되어야할 때 유용하다.

 

자료구조의 분류

가장 중요한 것은 앞에서도 언급했듯이 각 자료구조의 단위자료는 기본 자료형이 될 수 도 있지만, 클래스, 구조체, 배열과 같은 사용자 정의 자료형이 될 수 도 있다는 것이다.

 

선형 자료구조(Linear Data Structures)
데이터를 선형으로 저장하는 자료구조로 각요소는 이전 요소와 다음 요소의 관계를 가진다.
예시) 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue), 데크(Deque) 등

 

비선형 자료구조(Non-linear Data Structures)
데이터를 계층적으로 조직화하는 자료구조로 각요소는 하나 이상의 자식을 가질 수 있다.
예시) 트리(Tree)와 그 변형인 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), 힙(Heap), 그래프(Graph) 등

 

단순 자료구조(Simple Data Structures)
기본적인 데이터 저장 및 접근 기능만을 제공하는 자료구조로 데이터 추가, 삭제, 검색 등의 기능이 주로 지원된다.
예시) 배열(Array), 연결 리스트(Linked List)

 

복합 자료구조(Composite Data Structures)
여러 단순 자료구조를 조합하여 만들어진 자료구조로 보다 복잡한 데이터 조직화 및 처리가 가능하다.
예시) 트리(Tree), (Graph)

 

파일 자료구조(File Data Structure)
컴퓨터 시스템에서 데이터를 저장하고 조직화하는 방법
주로 파일 시스템에서 사용되면 파일 구조는 파일을 저장하는 방법과 파일 간의 관계를 정의한다.