'전체 글'에 해당되는 글 4건

알고리즘의 성능분석은 어떻게 하는 것일까?

만약 기존에 있는 알고리즘을 개선해서 어떠한 알고리즘을 새로 만들었고,

알고리즘이 내 PC에서 결과가 나오는데 까지 2초가 걸렸다고 주장한다면, 그 주장을 믿을 수 있는 것일까?

현실적으로 서로 다루는 PC의 사양과 환경, 소프트웨어 등이 전부 다르므로 알고리즘을 정확히 측정하기 힘들다.

이를 공정하게 비교하기 위해서 점근적 표기법을 사용한다.

점근적 표기법은 3가지가 존재한다.

O-notation (빅오 표기)

Ω-notation (오메가 표기)

Θ-notation (세타 표기)

이 3가지 방법에 대해서는 다음 포스팅에서 알아보도록 하자

추상 자료형이 무엇인지에 대해 알아보자!

추상 자료형은 구체적인 기능의 완성 과정은 서술하지 않고 오로지 순수하게 기능이 무엇인지만 나열하는 것을 말한다.

추상 자료형은 다음과 같은 속성을 가지고 있다.

1. Characters - 내부속성

2. Operation - 추상 자료형 연산

계산기를 예를들어 설명하자면,

계산기에 버튼, 플라스틱테두리, 계산기화면, 등은 Character 이다. 

계산기에 연산자인 +, -, *, / 은 Operation 이다.

프로그래밍을 하면서 보통 머릿속에 변수를 만들고 이 변수들을 가지고 어떻게 연산해야할까 상상한다.

이는 ADT 정의를 하는 것이고, 구현은 ADT가 정의 된 이후에 구현 한다. 

'데이터 추상화'란 무엇인가?

앞서 '추상화'의 의미부터 살펴보자.

추상화 (abstraction) 

추상화는 필요한 부분, 중요한 부분을 통합하여 하나로 만드는 것을 말한다.

예를들어 설명하면, 

동그란 원에 숫자가 12개까지 있고 시침과 분침 초침이 있는 걸 무엇이라고 할까?

답은 '아날로그 시계' 이다.

아날로그 시계도 디자인이 재각각이겠지만

추상화는 아주 중요한 부분을 통합하여 그 의미가 무엇을 의미하는지를 알 수있게 해준다.

그렇다면 데이터를 추상화 한다는 것은 무엇일까?

데이터의 물리적인 표현을 의식하지 않고 추상화한 데이터형으로써 이용할 수 가 있는데, 이러한 데이터의 물리적 표현과 그 기본 조작 절차를 묶어 정의해드고 그 형의 데이터는 정의된 절차를 따라서만 이루어지는 수법을 말한다.

추상하를 적절히 시키면 코드의 재사용성과 가독성을 높이고 결국 생산성, 에러의 감소와 같은 요소에 영향을 미치게 된다.

코딩을 하면서 빈번하게 쓰던 반복문을 살펴보자.

가와 나가 별을 100개 찍는다.

가:

printf("******....100개가 될 때까지 반복");

나:

for( i = 0; i < 100; i++ ) { printf("*");}

나에서는 *을 찍는 행동을 추상화 시켰다고 볼 수 있다.
나에서는 *을 한 번 찍는 다는 것 밖에 행동이 없었지만, 반복문을 사용함으로서 추상화 시켰고 반복문이 실행되며 행동이 실체화 되었다.

우리가 자주 쓰던 반복문도 일종의 추상화이다. 이러하듯, 추상화가 마냥 어려운 개념만은 아니다.

* 알고리즘 학습에 앞서 사전에 프로그래밍언어와 자료구조에 대해 공부를 끝 마치면 알고리즘 이해해 도움이 수월하다.

알고리즘은 무엇인가?

알고리즘은 유한시간내에 특정 문제를 해결하기 위한 일련의 순서적인 계산 / 풀이 절차, 실행의 집합이라고 생각할 수 있다.

쉽게 생각하면 우리가 일상생활에서 '라면'을 순서대로 조리하는 것도 알고리즘이라 할 수 있다.

1. 냄비에 물을 넣는다.

2. 냄비에 물을 가스렌지에 올린다.

3. 가스렌지 버너를 돌려 불을 켠다.

4. 라면봉지를 뜯는다.

5. 라면스프를 넣는다.

6. 면을 넣는다.

7. 면이 익으면 불을 끈다.

원하는 결과를 위해 이러한 순서 단계별로 진행한다. 그리고 이는 유용하다. 

이런 것을 알고리즘이라 불린다.

그렇다면 명확히 알고리즘의 조건(특성)은 무엇인가?

알고리즘의 조건(특성)으로는 5가지가 존재한다.

1. 입력: '0개 이상의 외부입력 데이터' 가 존재해야 한다.

2. 출력: '하나 이상의 결과' 가 나와야 한다.

3. 명확성: 모든 명령들은 모호하지 않고 '단순 명확' 해야 한다.

4. 유효성: 모든 명령은 '실행 가능' 해야 한다.

5. 유한성: 한정된 수의 단계 후에 '반드시 종료' 해야 한다.

알고리즘의 구조(요소)로는 3가지가 존재한다.

1. Sequence: 순차적으로 프로그램 코드를 수행 한다.

2. Decision(Selection): 특정 조건에 따라 수행을 달리 한다. 

3. Repetition: 수행을 1회 이상 반복 한다.

알고리즘의 프로세스