1절  자료구조와 알고리즘

<!--[if !supportLists]-->1.     <!--[endif]-->자료구조

<!--[if !supportLists]-->1)    <!--[endif]-->자료와 정보

<!--[if !supportLists]-->u  <!--[endif]-->자료를 얼마나 효율적으로 표현하고 관리할 것인가!

<!--[if !supportLists]-->u  <!--[endif]-->자료 : 단순한 관찰이나 측정을 통해 수집된 사실이나 어떤 값

<!--[if !supportLists]-->u  <!--[endif]-->정보 : 자료들을 특정 목적을 위하여 가공 및 처리하여 실제 문제에 도움이 되는 유용한 형태로 변환한 것

 

<!--[if !supportLists]-->2)    <!--[endif]-->자료구조

<!--[if !supportLists]-->u  <!--[endif]-->정의 : 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업

<!--[if !supportLists]-->u  <!--[endif]-->데이터를 효율적으로 표현하고 저장하기 위해 구조화 하는 것

<!--[if !supportLists]-->u  <!--[endif]-->자료의 사용 방법이나 성격에 따라 효율적으로 사용하기 위해 자료를 조직하고 저장하는 방법

<!--[if !supportLists]-->u  <!--[endif]-->알고리즘을 구성하는 부품(component)

<!--[if !supportLists]-->u  <!--[endif]-->기억 장치에 자료를 보관할 때 처리할 작업의 종류에 따라 적절한 자료 보관 방법인 자료구조를 선택

<!--[if !supportLists]-->u  <!--[endif]-->알고리즘 : 자료들을 처리하기 위한 일련의 절차와 방법. 자료 처리 절차 모임

<!--[if !supportLists]-->u  <!--[endif]-->프로그램 = 자료구조 + 알고리즘

 

<!--[if !supportLists]-->3)    <!--[endif]-->자료의 형태에 따른 분류

<!--[if !supportLists]-->u  <!--[endif]-->단순구조 : 정수, 실수, 문자, ,문자열

<!--[if !supportLists]-->u  <!--[endif]-->선형구조 : 리스트, 연결 리스트, 스택, 큐, 데크

<!--[if !supportLists]-->u  <!--[endif]-->비선형구조 : 트리, 그래프

<!--[if !supportLists]-->u  <!--[endif]-->파일구조 : 순차 파일, 색인 파일, 직접 파일

<!--[if !supportLists]-->u  <!--[endif]-->자료구조 선택 시 고려 요소

<!--[if !supportLists]-->o  <!--[endif]-->포함된 데이터의 양

<!--[if !supportLists]-->o  <!--[endif]-->데이터를 사용하는 방법과 횟수

<!--[if !supportLists]-->o  <!--[endif]-->데이터의 정적 혹은 동적인 특성

<!--[if !supportLists]-->o  <!--[endif]-->자료구조에 의해 요구되는 기억 장치의 양

<!--[if !supportLists]-->o  <!--[endif]-->하나의 데이터를 수정하는데 걸리는 시간

<!--[if !supportLists]-->o  <!--[endif]-->프로그래밍의 복잡도

 

<!--[if !supportLists]-->4)    <!--[endif]-->자료의 단위와 종류

<!--[if !supportLists]-->u  <!--[endif]-->전기적 펄스에 의해 수의 처리 이루어짐!

<!--[if !supportLists]-->(1)   <!--[endif]-->비트 (bit)

<!--[if !supportLists]-->o  <!--[endif]-->최소 단위. 2진수 0 또는 1

<!--[if !supportLists]-->o  <!--[endif]-->on, off / 참 거짓 등

<!--[if !supportLists]-->(2)   <!--[endif]-->니블 (nibble)

<!--[if !supportLists]-->o  <!--[endif]-->4bit , 16개 정보 저장 (<!--[if !msEquation]--> <!--[endif]-->)

<!--[if !supportLists]-->(3)   <!--[endif]-->바이트 (byte)

<!--[if !supportLists]-->o  <!--[endif]-->8bit , 256개 정보 저장 (<!--[if !msEquation]--> <!--[endif]-->)

<!--[if !supportLists]-->o  <!--[endif]-->하나의 문자를 표현하는 기본 단위

<!--[if !supportLists]-->o  <!--[endif]-->정보의 기본 단위

<!--[if !supportLists]-->(4)   <!--[endif]-->문자 (character)

<!--[if !supportLists]-->o  <!--[endif]-->단어 구성 요소

<!--[if !supportLists]-->o  <!--[endif]-->7bit ~ 8bit정도

<!--[if !supportLists]-->(5)   <!--[endif]-->단어 (word)

<!--[if !supportLists]-->o  <!--[endif]-->바이트의 모임 (보통 2byte)

<!--[if !supportLists]-->o  <!--[endif]-->컴퓨터 내부의 명령 처리 단위

<!--[if !supportLists]-->o  <!--[endif]-->컴퓨터 주기억 장치와 기타 장치 사이에 전송되는 비트의 모임

<!--[if !supportLists]-->(6)   <!--[endif]-->필드 (field)

<!--[if !supportLists]-->o  <!--[endif]-->파일을 구성하는 최소 단위. 항목!(item)

<!--[if !supportLists]-->o  <!--[endif]-->레코드를 구성하는 논리적 자료 단위

<!--[if !supportLists]-->o  <!--[endif]-->보다 의미 있는 정보를 구성하는 최소 단위

<!--[if !supportLists]-->(7)   <!--[endif]-->레코드 (record)

<!--[if !supportLists]-->o  <!--[endif]-->하나 이상의 필드들이 모여서 구성된 자료 처리 단위

<!--[if !supportLists]-->o  <!--[endif]-->서로 관련 있는 필드들이 모여서 레코드 구성

<!--[if !supportLists]-->(8)   <!--[endif]-->파일 (file)

<!--[if !supportLists]-->o  <!--[endif]-->여러 개의 레코드가 모여 구성

<!--[if !supportLists]-->o  <!--[endif]-->디스크 저장 단위

<!--[if !supportLists]-->o  <!--[endif]-->프로그램 구성의 기본 단위

<!--[if !supportLists]-->u  <!--[endif]-->자료

<!--[if !supportLists]-->o  <!--[endif]-->수치 자료 : 사칙 연산의 대상이 되는 자료

<!--[if !supportLists]-->o  <!--[endif]-->비수치 자료 : 문자 데이터(ASCII 7bit, EBCDIC 8bit), 논리 자료

<!--[if !supportLists]-->o  <!--[endif]-->기억장치에는 바이트, 비트 단위로 주소가 할당

<!--[if !supportLists]-->o  <!--[endif]-->주소를 가지고 자료를 읽고 쓰는 등 처리 함

 

<!--[if !supportLists]-->2.     <!--[endif]-->알고리즘

<!--[if !supportLists]-->1)    <!--[endif]-->알고리즘의 개요

<!--[if !supportLists]-->u  <!--[endif]-->주어진 문제를 해결하기 위한 문제 해결 과정을 묘사하는 것

<!--[if !supportLists]-->u  <!--[endif]-->절차와 방법, 명령 등을 명확하게 기술해 놓은 것

<!--[if !supportLists]-->u  <!--[endif]-->프로그램이 만들어진 목적대로 작업을 수행하도록 하는 것

<!--[if !supportLists]-->u  <!--[endif]-->문제를 해결할 수 있는 잘 정의된 유한 시간 내에 종료되는 체계적인 절차

<!--[if !supportLists]-->o  <!--[endif]-->잘 정의된 : 알고리즘 읽었을 때 누구나 동일한 내용으로 이해 가능하도록 기술

<!--[if !supportLists]-->o  <!--[endif]-->유한 시간 내 종료 : 알고리즘 적용해 유한 시간 내 문제를 해결해 결과를 구함

<!--[if !supportLists]-->o  <!--[endif]-->즉, 출력 결과를 얻는 과정!

<!--[if !supportLists]-->u  <!--[endif]-->알고리즘의 요구조건

<!--[if !supportLists]-->o  <!--[endif]-->입력 : 외부에서 제공되는 0개 이상의 입력 데이터가 존재

<!--[if !supportLists]-->o  <!--[endif]-->출력 : 입력 값으로부터 적어도 하나 이상의 결과가 출력되어야 함

<!--[if !supportLists]-->o  <!--[endif]-->명확성 : 기술된 명령들이 모호하지 않고 명확해야 함

<!--[if !supportLists]-->o  <!--[endif]-->유한성 : 제한된 수의 명령 단계를 거친 후에는 반드시 종료해야 됨

<!--[if !supportLists]-->o  <!--[endif]-->유효성 : 모든 명령은 실행 가능해야 함

 

<!--[if !supportLists]-->2)    <!--[endif]-->알고리즘 기술 방법

<!--[if !supportLists]-->(1)   <!--[endif]-->자연어

<!--[if !supportLists]-->o  <!--[endif]-->사람이 사용하는 문장으로 설명

<!--[if !supportLists]-->o  <!--[endif]-->쉽고 편리 / 길어질 수 있고 의미 애매할 수 있음

<!--[if !supportLists]-->o  <!--[endif]-->복잡한 알고리즘 기술 시 부적절

<!--[if !supportLists]-->(2)   <!--[endif]-->순서도

<!--[if !supportLists]-->o  <!--[endif]-->명령의 종류와 기능에 따라 도표를 만들고 명령들의 순서대로 도표를 나열해 표현

<!--[if !supportLists]-->o  <!--[endif]-->작업의 연관 관계와 선후 관계를 시각적으로 보여줌

<!--[if !supportLists]-->o  <!--[endif]-->프로그램 작성의 직접적인 자료가 됨

<!--[if !supportLists]-->o  <!--[endif]-->이해 용이, 전달 용이

<!--[if !supportLists]-->o  <!--[endif]-->프로그램 정확성 여부 판단하는 자료

<!--[if !supportLists]-->o  <!--[endif]-->오류 발생 시 수정 간편

<!--[if !supportLists]-->(3)   <!--[endif]-->의사코드

<!--[if !supportLists]-->o  <!--[endif]-->프로그램 코드와 유사한 형식을 갖는 코드

<!--[if !supportLists]-->o  <!--[endif]-->특정 프로그래밍 언어의 문법에 따라 쓰이지 않고 일반적 언어로 코드를 흉내 낸 것

<!--[if !supportLists]-->o  <!--[endif]-->가장 선호되는 표기법

<!--[if !supportLists]-->o  <!--[endif]-->일반적으로 C언어 형식으로 작성

<!--[if !supportLists]-->(4)   <!--[endif]-->프로그래밍 언어

<!--[if !supportLists]-->o  <!--[endif]-->알고리즘 가장 정확히 표현하는 방법

<!--[if !supportLists]-->o  <!--[endif]-->구현 위해 구체적인 사항이 많아 알고리즘 전체 내용 파악에 어려울 수 있음

 

<!--[if !supportLists]-->2절  <!--[endif]-->자료 추상화

<!--[if !supportLists]-->l  <!--[endif]-->추상화

<!--[if !supportLists]-->n  <!--[endif]-->불필요한 부분을 삭제하거나 중요한 특징을 찾아낸 후 간단하게 표현.

<!--[if !supportLists]-->n  <!--[endif]-->필수적이고 중요한 속성만을 골라서 일반화 시키는 과정

<!--[if !supportLists]-->n  <!--[endif]-->여러 문제를 하나로 통합해 가는 과정

<!--[if !supportLists]-->n  <!--[endif]-->정보 은닉의 개발 : 사용자에게 중요한 정보 강조, 세부 사항은 제거

 

<!--[if !supportLists]-->l  <!--[endif]-->추상 자료형

<!--[if !supportLists]-->n  <!--[endif]-->정의 : 자료형의 일반화. 추상적으로 정의된 자료형

<!--[if !supportLists]-->n  <!--[endif]-->의의 : 구현으로부터 명세의 분리

<!--[if !supportLists]-->n  <!--[endif]-->데이터가 무엇이고 무슨 기능을 수행하는가 만을 정의

<!--[if !supportLists]-->n  <!--[endif]-->데이터 구조 및 연산의 구현 방법은 불포함(프로그램 언어마다 구현 방법이 다름)

<!--[if !supportLists]-->n  <!--[endif]-->객체와 연산을 정의

<!--[if !supportLists]-->n  <!--[endif]-->일반 자료형 이 외에 내가 필요한 자료형을 추상적으로 표현한 것

<!--[if !supportLists]-->n  <!--[endif]-->사물이나 현상을 데이터적 측면과 기능적 측면으로 나누어 표현한 것

<!--[if !supportLists]-->n  <!--[endif]-->구현에 관한 세부사항은 외부에서 모르게 하고 외부에서 간단한 인터페이스만 제공

<!--[if !supportLists]-->n  <!--[endif]-->사용자는 공개된 인터페이스만 사용, 구현 방법은 알 필요 없음 -> 정보 은닉

 

<!--[if !supportLists]-->3절  <!--[endif]-->SPARKS

<!--[if !supportLists]-->l  <!--[endif]-->알고리즘 기술에 사용되는 언어의 일종

<!--[if !supportLists]-->l  <!--[endif]-->PASCAL이나 C언어 등 구조화 된 프로그램 언어로 쉽게 변환

 

<!--[if !supportLists]-->1.     <!--[endif]-->선언문 (비실행문)

<!--[if !supportLists]-->n  <!--[endif]-->프로그램의 일반적인 특성과 그 프로그램을 다루는 데이터의 특성을 지정하는 비실행문

 

<!--[if !supportLists]-->2.     <!--[endif]-->지정문

<!--[if !supportLists]-->n  <!--[endif]-->상수나 변수 또는 연산식의 결과를 변수에 지정하는 문장

<!--[if !supportLists]-->n  <!--[endif]-->변수 ← 값; (← : 대입 연산자)

 

<!--[if !supportLists]-->3.     <!--[endif]-->조건문

<!--[if !supportLists]-->n  <!--[endif]-->if 문

<!--[if !supportLists]-->n  <!--[endif]-->주어진 조건이 참이냐 거짓이냐에 따라 다른 명령 처리하도록 만든 수행문

<!--[if !supportLists]-->n  <!--[endif]-->if (조건식1) – then (A) – else if(조건식2) – then (B) – else (C)

if (조건식1) then

      명령문 1;

else if (조건식2) then // 다중 조건문

      명령문 2;

...

else

      명령문 n;

endif

 

<!--[if !supportLists]-->4.     <!--[endif]-->case문

<!--[if !supportLists]-->n  <!--[endif]-->여러 조건식 중 해당 조건 찾아 그에 대한 명령문 수행

<!--[if !supportLists]-->n  <!--[endif]-->if문보다 가독성이 높음

case {

      조건식 1 : 명령문 1;

      조건식 2 : 명령문 2;

…

      조건식 n : 명령문 n;

      else : 명령문 n+1;

}

 

<!--[if !supportLists]-->5.     <!--[endif]-->반복문

<!--[if !supportLists]-->1)    <!--[endif]-->for 문

<!--[if !supportLists]-->u  <!--[endif]-->반복 횟수를 지정 / 반복 끝내는 종료 조건 제시

<!--[if !supportLists]-->u  <!--[endif]-->반복하는 부분을 제어하기 위해 초기값, 조건식, 증감값 등 세 부분으로 구성

for (초기값; 조건식; 증감값)

            명령문;

 

for (초기값; 조건식; 증감값)

{

    명령문;

}

 

<!--[if !supportLists]-->2)    <!--[endif]-->while 문

<!--[if !supportLists]-->u  <!--[endif]-->조건식이 참인 동안 명령문 반복 수행

<!--[if !supportLists]-->u  <!--[endif]-->처음부터 조건식이 거짓이면 명령문 수행 없이 while문 빠져나옴

while (조건식)

           명령문;

 

<!--[if !supportLists]-->6.     <!--[endif]-->procedure문

<!--[if !supportLists]-->n  <!--[endif]-->처리할 작업 별로 작은 단위 프로그램을 여러 개 구성하는 것

<!--[if !supportLists]-->n  <!--[endif]-->하나의 프로그램 안에 기능A가 여러 번 실행하는 구조를 가진 경우 기능 A를 하나의 단위로 만들 수 있음. -> 프로시저로 작성 가능

<!--[if !supportLists]-->n  <!--[endif]-->특정 작업을 수행하기 위한 프로그램의 일부. 필요 시 호출하여 사용

<!--[if !supportLists]-->n  <!--[endif]-->일련의 반복적인 명령을 수행하는 블록을 별도의 블록으로 표현한 것

<!--[if !supportLists]-->n  <!--[endif]-->서브루틴이나 함수가 될 수 있음

<!--[if !supportLists]-->n  <!--[endif]-->procedure NAME (parameter list)

명령문

end

 

<!--[if !supportLists]-->7.     <!--[endif]-->프로시저 간 자료 전달 방법

<!--[if !supportLists]-->n  <!--[endif]-->실 매개변수와 형식 매개변수가 필요

<!--[if !supportLists]-->n  <!--[endif]-->실 매개변수 : 프로시저에 전달되는 실제 값을 저장하고 있는 인자

<!--[if !supportLists]-->n  <!--[endif]-->형식 매개변수 : 프로시저 선언에 사용하는 인자

<!--[if !supportLists]-->1)    <!--[endif]-->call by value

<!--[if !supportLists]-->u  <!--[endif]-->실 매개변수 값 자체를 서브 프로시저의 형식 매개변수에 전달

<!--[if !supportLists]-->u  <!--[endif]-->호출된 프로시저에서 지역변수처럼 취급 -> main 함수에 선언된 변수 값 변경 X

<!--[if !supportLists]-->u  <!--[endif]-->변수 값을 변경시켜 프로시저에 전달 -> 원본 데이터 손상 X

 

<!--[if !supportLists]-->2)    <!--[endif]-->call by reference

<!--[if !supportLists]-->u  <!--[endif]-->실 매개변수 값이 저장된 기억 장소를 가리키는 포인터나 실제 수로를 형식 매개변수에 전달

<!--[if !supportLists]-->u  <!--[endif]-->형식 매개변수가 간접 주소법을 이용하여 실 매개변수 참조

<!--[if !supportLists]-->u  <!--[endif]-->형식 매개변수 값 변경 -> 대응 실 매개변수 값도 변경

 

<!--[if !supportLists]-->3)    <!--[endif]-->call by name

<!--[if !supportLists]-->u  <!--[endif]-->형식 매개변수의 이름이 사용될 때마다 그에 대응되는 실 매개변수의 이름으로 대치됨

<!--[if !supportLists]-->u  <!--[endif]-->형식 매개변수가 사용되는 시점에서 대응되는 실 매개변수의 값이나 기억 장소 위치를 구해 사용

 

<!--[if !supportLists]-->8.     <!--[endif]-->입 ∙ 출력문

<!--[if !supportLists]-->n  <!--[endif]-->read 문 : 데이터 값을 입력 받을 때 사용

<!--[if !supportLists]-->n  <!--[endif]-->print 문 : 변수의 내용이나 계산 결과 출력할 때 사용

<!--[if !supportLists]-->n  <!--[endif]-->read(argument list)

print(argument list)

 

<!--[if !supportLists]-->9.     <!--[endif]-->기타 명령과 규칙

<!--[if !supportLists]-->1)    <!--[endif]-->주석

<!--[if !supportLists]-->u  <!--[endif]-->// 이나 /* */

<!--[if !supportLists]-->2)    <!--[endif]-->stop 문

<!--[if !supportLists]-->u  <!--[endif]-->현재 진행 중인 프로그램을 중단하는 구문

<!--[if !supportLists]-->u  <!--[endif]-->프로시저 안의 어느 곳에서든 stop문 사용 가능

<!--[if !supportLists]-->3)    <!--[endif]-->SPARKS 언어 사용 규칙

<!--[if !supportLists]-->u  <!--[endif]-->변수 의미 알 수 있게 정의

<!--[if !supportLists]-->u  <!--[endif]-->프로시저의 입∙출력 변수 명확히 명시

<!--[if !supportLists]-->u  <!--[endif]-->제어흐름 되도록 순차적으로

<!--[if !supportLists]-->u  <!--[endif]-->들여쓰기

<!--[if !supportLists]-->u  <!--[endif]-->주석 짧고 명확하게

<!--[if !supportLists]-->u  <!--[endif]-->함수 적절히 사용

 

<!--[if !supportLists]-->4절  <!--[endif]-->순환 알고리즘

<!--[if !supportLists]-->l  <!--[endif]-->순환(recursion) :

<!--[if !supportLists]-->n  <!--[endif]-->정의하려는 개념 자체를 정의 속에 포함하여 사용하는 방법 (자신의 정의에 자신을 다시 사용)

<!--[if !supportLists]-->n  <!--[endif]-->문제 내에 문제 자체의 작은 형태가 또 존재하는 형태로 자기 자신을 다시 호출하여 문제를 해결하는 기법

<!--[if !supportLists]-->n  <!--[endif]-->어떤 문제에 크기만 다를 뿐 성격이 똑 같은 작은 형태의 문제들이 포함된 것(점근적 접근)

<!--[if !supportLists]-->n  <!--[endif]-->알고리즘이나 함수가 수행 도중 자기 자신을 다시 호출하여 문제를 해결하는 기법

<!--[if !supportLists]-->n  <!--[endif]-->하나의 문제 내에 매개변수만 다른 동일한 문제가 있을 때 사용

<!--[if !supportLists]-->n  <!--[endif]-->프로그램 단순화, 명료. 함수의 정의 단순하게 표현 가능

<!--[if !supportLists]-->n  <!--[endif]-->순환의 정의에서 초기의 조건을 잘 정리해야 함

<!--[if !supportLists]-->l  <!--[endif]-->직접 순환 : 함수가 직접 자신을 호출

<!--[if !supportLists]-->l  <!--[endif]-->간접 순환 : 다른 제 3의 함수를 호출하고 그 함수가 다시 자신을 호출하는 방법

<!--[if !supportLists]-->l  <!--[endif]-->순환 호출을 종료하는 조건을 추가해 줘야 함 -> 무한 호출 방지

<!--[if !supportLists]-->l  <!--[endif]-->반복문으로 바꾸어 작성 가능

 

<!--[if !supportLists]-->5절  <!--[endif]-->성능 분석

<!--[if !supportLists]-->l  <!--[endif]-->자원 : 소요 시간, 메모리, 통신 대역 등

<!--[if !supportLists]-->l  <!--[endif]-->효율적인 알고리즘 : 전체 실행 시간이 짧고 메모리 같은 컴퓨터 자원을 적게 사용하는 알고리즘

<!--[if !supportLists]-->l  <!--[endif]-->알고리즘 복잡도 분석!

<!--[if !supportLists]-->1.     <!--[endif]-->공간 복잡도

<!--[if !supportLists]-->n  <!--[endif]-->알고리즘이 수행될 때 필요한 메모리 공간

<!--[if !supportLists]-->n  <!--[endif]-->알고리즘을 프로그램으로 실행시켜 완료하는 데 까지 소요되는 총 저장 공간

<!--[if !supportLists]-->n  <!--[endif]-->공간 복잡도 = 고정공간 + 가변공간

<!--[if !supportLists]-->u  <!--[endif]-->고정 공간 : 프로그램 크기나 입∙출력 횟수와 관계 없이 고정적으로 필요한 저장 공간

<!--[if !supportLists]-->u  <!--[endif]-->가변 공간 : 실행 과정에서 자료구조와 변수들이 필요로 하는 저장 공간

<!--[if !supportLists]-->n  <!--[endif]-->대용량 컴퓨터가 많아지며 공간 복잡도 중요성 낮아짐

 

<!--[if !supportLists]-->2.     <!--[endif]-->시간 복잡도

<!--[if !supportLists]-->n  <!--[endif]-->알고리즘을 실행시켜 완료하는 데까지 걸리는 시간

<!--[if !supportLists]-->n  <!--[endif]-->알고리즘을 이루고 있는 연산들이 몇 번 실행되는지 숫자로 표시 “연산의 실행 횟수”

<!--[if !supportLists]-->n  <!--[endif]-->시간 복잡도 = 컴파일 시간 + 실행 시간

<!--[if !supportLists]-->u  <!--[endif]-->컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요

<!--[if !supportLists]-->u  <!--[endif]-->실행 시간 : 명령문의 실행 빈도수에 따라 계산

<!--[if !supportLists]-->o  <!--[endif]-->하나의 단위 시간 : 지정문, 조건문, 반복문 내의 제어문과 반환문

<!--[if !supportLists]-->o  <!--[endif]-->실행 시간 좌우 하는 것 : for 루프 횟수, 특정 행이 수행되는 횟수, 함수 호출 횟수

<!--[if !supportLists]-->n  <!--[endif]-->연산 횟수를 시간 복잡도로 계산했을 때 장점

<!--[if !supportLists]-->u  <!--[endif]-->코딩, 실행이 필요하지 않음

<!--[if !supportLists]-->u  <!--[endif]-->하드웨어, 소프트웨어 필요하지 않음 -> 의사코드로 충분히 계산 가능

<!--[if !supportLists]-->u  <!--[endif]-->모든 플랫폼에서 동일한 결과 산출

<!--[if !supportLists]-->n  <!--[endif]-->실제 실행 시간을 시간 복잡도로 계산했을 때 단점

<!--[if !supportLists]-->u  <!--[endif]-->측정을 위한 완성된 프로그램이 필요

<!--[if !supportLists]-->u  <!--[endif]-->모든 플랫폼에서 동일한 결과 산출하지 못함

 

<!--[if !supportLists]-->3.     <!--[endif]-->연산 시간 표기법

<!--[if !supportLists]-->n  <!--[endif]-->점근적 분석법

<!--[if !supportLists]-->u  <!--[endif]-->입력의 크기가 충분히 큰 경우에 대한 분석

<!--[if !supportLists]-->u  <!--[endif]-->데이터의 개수 n이 무한대가 될 떄 수행 시간이 증가하는 증가율을 시간 복잡도로 표현

<!--[if !supportLists]-->u  <!--[endif]-->최고차항의 차수만으로 표시 -> 가장 자주 실행되는 연산 혹은 문장의 실행 횟수 고려

<!--[if !supportLists]-->o  <!--[endif]-->가장 큰 항의 영향이 절대적이고 다른 항은 무시될 정도로 작아짐

<!--[if !supportLists]-->u  <!--[endif]-->어떤 함수의 증가 혹은 감소 양상을 다른 간단한 함수와 비교로 표현하는 방법

 

<!--[if !supportLists]-->1)    <!--[endif]-->빅-오(Big-O) 표기법

<!--[if !supportLists]-->u  <!--[endif]-->실행 시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택하여 계수 생략

<!--[if !supportLists]-->u  <!--[endif]-->O(Big-O)로 표현

<!--[if !supportLists]-->u  <!--[endif]-->입력 데이터가 최악일 때 알고리즘이 보이는 효율 기준

<!--[if !supportLists]-->u  <!--[endif]-->f(n)과 g(n)이 주어졌을 때 모든 <!--[if !msEquation]--> <!--[endif]-->에 대하여 f(n) ≤ cg(n)을 만족하는 상수 c와 <!--[if !msEquation]--> <!--[endif]-->가 존재하면 f(n) = O(g(n))이다.

u  점근적 상한선

<!--[if !supportLists]-->o 를 기준으로 보다 오른쪽에 있는 모든 n값에 대해 

    함수 f(n)은 함수 cg(n)보다 작거나 같다.

<!--[if !supportLists]-->o  <!--[endif]-->아무리 나빠도 비교하는 함수와 같거나 좋다.


<!--[if !supportLists]-->u  <!--[endif]-->주어진 함수의 가장 높은 차수의 항을 사용하고 계수는 1로 함

<!--[if !supportLists]-->u  <!--[endif]-->정보의 손실이 일어날 수 있음 -> 엄밀하지 않음

<!--[if !supportLists]-->u  <!--[endif]-->길어야 이정도 시간이면 된다! -> 가장 근접한 상한 사용

<!--[if !supportLists]-->u  <!--[endif]-->복잡도 순서 : O(1) < O(logn) < O(n) < O(nlogn) < O() < O() < O() < O(n!)

<!--[if !supportLists]-->o  <!--[endif]-->O(1)

상수 시간

<!--[if !supportLists]-->o  <!--[endif]-->O()

제곱 시간

<!--[if !supportLists]-->o  <!--[endif]-->O(logn)

로그 시간

<!--[if !supportLists]-->o  <!--[endif]-->O()

세제곱 시간

<!--[if !supportLists]-->o  <!--[endif]-->O(n)

선형 시간

<!--[if !supportLists]-->o  <!--[endif]-->O()

지수 시간

<!--[if !supportLists]-->o  <!--[endif]-->O(nlogn)

로그 선형 시간

<!--[if !supportLists]-->o  <!--[endif]-->O(n!)

계승 시간


2)    <!--[endif]-->빅-오메가(Big- Ω) 표기법

<!--[if !supportLists]-->u  <!--[endif]-->f(n)과 g(n)이 주어졌을 때 모든 <!--[if !msEquation]--> <!--[endif]-->에 대하여 f(n) ≥ cg(n)을 만족하는 상수 c와 <!--[if !msEquation]--> <!--[endif]-->가 존재하면 f(n) = Ω(g(n))이다.

<!--[if !supportLists]-->u  <!--[endif]-->점근적 하한선

<!--[if !supportLists]-->o  를 기준으로 보다 오른쪽에 있는 모든 n값에 대해 

    함수 f(n)은 함수 cg(n)보다 크거나 같다.

<!--[if !supportLists]-->o  <!--[endif]-->적어도 g(n)의 비율로 증가하는 함수

<!--[if !supportLists]-->o  <!--[endif]-->아무리 좋아도 비교하는 함수와 같거나 나쁘다.

<!--[if !supportLists]-->u  <!--[endif]-->최소한 이만한 시간은 걸린다!

 

<!--[if !supportLists]-->3)    <!--[endif]-->빅-세타(Big- Θ) 표기법

<!--[if !supportLists]-->u  <!--[endif]-->점근적 상한선과 점근적 하한선의 교집합

<!--[if !supportLists]-->u  <!--[endif]-->f(n)과 g(n)이 주어졌을 때 모든 <!--[if !msEquation]--> <!--[endif]-->에 대하여 c1g(n) ≤ f(n) ≤ c2g(n)을 만족하는 상수 c1, c2와 <!--[if !msEquation]--> <!--[endif]-->가 존재하면 f(n) = Θ(g(n))이다

o  를 기준으로 보다 오른쪽에 있는 모든 n값에 대해 

    함수 f(n)은 함수 c1g(n)보다 크거나 같고 c2g(n)보다 작거나 같다.

<!--[if !supportLists]-->o  <!--[endif]-->가장 정밀한 점근적 표기법

 

<!--[if !supportLists]-->4.     <!--[endif]-->실용적인 복잡도

<!--[if !supportLists]-->n  <!--[endif]-->최선의 경우, 평균적인 경우, 최악의 경우로 나누어 평가 가능

<!--[if !supportLists]-->n  <!--[endif]-->최대로 불리한 입력 데이터를 사용하는 최악의 경우의 실행 시간이 가장 중요

<!--[if !supportLists]-->o  <!--[endif]-->완만할수록 효율적

 


저작자표시 비영리 변경금지

'[시험] 독학사 2020 전공기초' 카테고리의 다른 글

[독학사][자료구조] 02 배열  (0) 2020.07.12
독학사 프로그래밍 언어론 합격 후기  (0) 2020.06.24
독학사 컴퓨터시스템구조 합격 후기  (0) 2020.06.24
독학사 자료구조 합격 후기  (0) 2020.06.24
독학사 C프로그래밍 합격 후기  (0) 2020.06.24

+ Recent posts

티스토리툴바