1주차(1) - 알고리즘과 데이터 구조 개요

데이터 구조 (Data Structure)

Data Structure와 Algorithm의 기본 개념을 이해하고, 이를 활용하여 Software를 개발할 수 있는 능력을 갖추는 것을 목표로 하는 학문

 

Software 개발의 단계

소프트웨어는 일반적으로 다음 4가지의 과정으로 개발된다.

1. 요구사항 분석
2. 설계
3. 구현
4. 검증

1. Requirement Analysis (요구사항 분석)

문제의 요구사항, 입출력의 형식 및 내용들을 정의하고 분석

2. Design (설계)

개념적인 구성요소를 설계하고 이어서 상세한 내용을 설계

3. Coding (구현) (= implementation)

상세 설계된 내용을 프로그래밍 언어를 사용하여 구현

4. Verification(검증)

구현된 결과가 문제의 요구사항을 만족하는 지를 검증

 

알고리즘 (Algorithm)

알고리즘은 아래와 같이 정의할 수 있다.

1. 어떤 문제를 해결하기 위한 일련의 절차, 방법
2. 어떤 일을 수행하기 위한 명령어들의 집합

알고리즘은 일반적으로 아래와 같은 특성을 가진다고 정리할 수 있다.

1. 출력(Output)을 생성
2. 각 수행단계가 명확해야 함
3. 각 수행단계가 반드시 실제로 구현 가능한 내용이어야 함
4. 유한 단계의 수행 후에 반드시 종료되어야 함

1. 출력 (Output)을 생성

알고리즘은 입력에 대한 출력이 있어야 한다.

2. 각 수행단계가 명확해야 함

알고리즘의 각 단계를 기술할 때 모호함이 발생하지 않도록 해석하기 어렵거나 여러가지 의미로 해석될 수 있는 표현의 사용을 피해야 한다.

3. 각 수행단계가 반드시 실제로 구현 가능한 내용이어야 함

결국 알고리즘을 구성하는 목적은 이를 구현하여 컴퓨터에서 실행하기 위함이기 때문에 알고리즘의 각 수행단계는 컴퓨터에서 구현할 수 있어야 한다.

4. 유한 단계의 수행 후에 반드시 종료되어야 함

어떤 알고리즘을 기술할 때 결국은 종료됨을 보장하지 못하는 경우는 존재해서는 안됨

 

 

알고리즘의 표현 방법

알고리즘은 일반적으로 다음 4가지 방식을 사용하여 표현한다.

1. 자연어 (Natural Language)

영어, 한글 등을 사용하여 알고리즘의 각 단계를 설명하는 방식

알고리즘을 특별한 제약없이 자유롭게 기술할 수 있다는 장점이 존재한다. 하지만 자연어에서 발생할 수 있는 중의적 표현과 같은 모호함 때문에 알고리즘의 명확성을 떨어뜨릴 수 있다는 단점이 존재한다. 따라서, 자연어를 사용하여 알고리즘을 기술할 때에는 최대한 간단명료하게 기술할 수 있도록 노력해야할 필요가 있다.

2. 순서도 (Flow Chart)

알고리즘의 실행 순서를 다이어그램(diagram)으로 표현하는 방식

3. Pseudo Code

자연어에 가까운 기호적 약속으로 알고리즘을 표현하는 방식

Pseudo Code는 사람이 알고리즘을 쉽게 이해할 수 있도록 사용하는 가상의 언어이며 실제로 컴파일러에서 돌아가는 언어는 아니다.

4. Programming Language

특정 프로그래밍 언어를 사용하여 알고리즘을 표현하는 방식

알고리즘을 모호함 없이 정확하고 명확하게 기술할 수 있다는 장점이 있지만, 특정 프로그래밍 언어에 종속되어 표현되기 때문에 해당 언어가 가진 특징이나 지원하는 라이브러리 등에 의해서 기술되는 내용이 달라질 수 있다. 즉, 특정 프로그래밍 언어에 종속되어 표현된다는 단점이 존재한다.

 

 

좋은 프로그램 이란?

일반적으로 좋은 프로그램은 아래의 7가지 특성을 가진다.

1. 요구조건을 정확하게 수행
2. 메모리 사용량을 최소화
3. 응답 시간 및 처리 시간을 최소화
4. 가독성(Readability)
5. 유지보수(Maintenance)가 용이함
6. 좋은 확장성을 가짐
7. 높은 신뢰성을 가짐

1. 요구조건을 정확하게 수행

주어진 문제의 제약조건을 정확하게 만족하고 문제에서 정의된 모든 입력에 대해서 타당한 결과를 낼 수 있어야 한다. 이를 만족하지 못하는 경우 문제를 해결한 프로그램이라고 볼 수 없다.

2. 메모리 사용량을 최소화

메모리 사용량을 최소화 한다는 것은 동일한 문제라도 적은 양의 하드웨어 리소스를 사용하여 문제를 해결한다는 의미이므로 경제성과 연결되는 중요한 요소이다.

3. 응답 시간 및 처리 시간을 최소화

만약 알고리즘이 유효한 시간 내에 결과를 내지 못한다면 해당 알고리즘을 문제 상황에 적용할 수 없게 되고, 또한 프로그램의 실행시간이 빠를 수록 문제를 빠른 시간 내에 해결할 수 있기 때문에 시간을 절약할 수 있게 된다.

4. 가독성

알고리즘을 구현한 소스코드의 가독성이 좋아야 협업 상황에서 타인도 코드를 쉽게 이해할 수 있기 때문에 코드의 가독성은 대단히 중요한 요소 중 하나이다.

5. 유지보수가 용이함

완성된 프로그램이 기능의 변화되거나 추가될 때 이를 위한 작업을 쉽게할 수 있도록 코드를 작성해야함을 의미한다. 코드의 유지보수성이 좋지 못하면 장기적인 관점에서 봤을 때 해당 프로그램에 대한 유지비용이 지속적으로 상승하게 되기 때문에 바람직하지 못하다.

6. 좋은 확장성을 가짐

특정 프로그램이 다양한 프로그램들과 함께 사용될 때 다른 프로그램들과의 관계에서 발생하는 변수들에 크게 영향을 받지 않을수록 바람직하다.

7. 높은 신뢰성을 가짐

어떤 환경변수나 많은 조건이 달라지더라도 알고리즘이 안정적으로 타당한 결과를 낼 수 있어야 함을 의미한다. 프로그램이 높은 신뢰성을 가지지 못한다면 해당 프로그램은 실제 문제해결에 사용될 수 없다.