[자료구조 1장] - 컴퓨터와 프로그램의 이해(2)

컴퓨터와 프로그램의 이해(2)

저번에 작성한 첫 글은 챕터 1의 1-1과 1-2까지의 내용을 정리한 것입니다. 이제부터는 소개말 없이 바로 내용을 작성할 생각입니다.

 

프로그램과 자료구조

프로그램 : 자료구조 + 알고리즘

 

자료와 자료형

기본 자료형 : int, float, double, char 등

포인터 자료 : 다른 변수의 메모리 주소 값을 가지는 기본 자료형

 

자료구조의 분류

선형 구조 : 자료의 전, 후 항목 사이의 관계가 1:1, 자료의 앞과 뒤의 순서가 명확하게 나란히 줄을 선 형태인 리스트 구조

-> 배열, 스택, 큐, 연결리스트 등

비선형 구조 : 자료 항목 사이에 어떤 자료와 관계가 있는 다른 자료가 여러 개인 경우, 즉 1:n 또는 n:m의 관계인 그래프적 특성을 갖는 자료구조

-> 조직의 계층도, 족보, 파일시스템 등, 여기서 살펴볼 비선형 구조는 트리와 그래프로 나뉜다.

 

자료구조의 활용

배열

1차원, 2차원 배열의 사용

ex) 성적 처리 프로그램

---

 

프로그램과 알고리즘

알고리즘의 사전적 의미 : 어떤 문제를 해결해 나가는 특별한 방법 또는 문제의 해결을 위해 컴퓨터가 수행할 수 있는 단계적 절차의 논리적 기술

 

알고리즘의 5가지 조건

1. 입력(input) : 알고리즘 수행을 위해 필요한 자료가 외부에서 입력되어야 한다.

2.출력(output) : 적어도 하나 이상의 결과를 출력해야 한다.

3.명확성(definiteness) : 각 명령은 애매모호하지 않고 명확해야 한다.

4.유한성(finiteness) : 정해진 명령의 실행 단계 후에는 반드시 종료되어야 한다.

5.유효성(effectiveness) : 모든 명령어는 기본적이며 실행 가능한 것이어야 한다.

 

알고리즘의 표현

자연어, 순서도, NS 도표 등

-> 개선된 방법 : 의사 코드 기술 방법

 

의사코드 : 컴파일러가 존재하지 않아 실행할 수는 없으므로 의사코드라 부름

- 쉽게 프로그래밍 가능

- 언어 독립적

- 기계 독립적

 

컴퓨터가 수행할 수 있는 보편적인 명령어 문장 5가지

1. 대입문

2. 조건문

3. 반복문

4. 입/출력문

5. 함수호출문

 

알고리즘의 성능분석

시간복잡도와 공간복잡도

보통 시간복잡도를 주로 고려한다.

시간복잡도 분석을 위해 점근복잡도 개념 사용

 

빅오표기법

O(1)	상수시간
O(log2n)	로그시간
O(n)	선형시간
O(nlog2n)	로그선형시간
O(n^2)	이차시간
O(2^n)	지수시간

 

그래프로 해당 시간복잡도를 비교해보면, n이 증가함에 따라 해당 표에 표기된 순서대로 증가 곡선을 보여주는데,

이 곡선이 완만한 것이 효율적인 시간복잡도를 가진다.

 

시간복잡도 좋은 순

O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(2^n)

ex) n이 1일때, O(n) => O(1), O(2^n) => O(2)

ex) n이 10일때, O(n) => O(10), O(2^n) => O(1024)

※  n이 커질수록 성능차이가 많이 벌어진다