알고리즘 공부 첫 번째

알고리즘

1.     알고리즘 이란

l  주어진 문제를 풀기 위해 논리적인 절차나 방법을 말하며 컴퓨터 프로그램을 기술함에 있어 실행 명령어들의 순서를 의미한다.

(1)   알고리즘의 특성

n  반드시 0개 이상의 입력이 존재해야 하며 1개 이상의 출력이 존재해야 함

n  주어진 입력에 대해 빠른 시간에 답을 주어야 하며, 메모리 공간도 효율적  ( 시간적, 공간적 효율성 )

n  프로그래밍 언어로 표현되어야 한다.

n  일정 시간 내에 반드시 종료되어야 한다.

2.     알고리즘의 표현방법

l  Natural Language(자연어) : 인간 사용하는 일반적인 언어

l  Flow-Chart (순서도) : 논리적인 절차, 흐름, 처리방법 등을 그림으로 표현

순서도의 기능

: 코딩의 기초적인 자료의 오류 / 수정이 용이하다.

: 프로그램의 내용과 논리적인 체계를 쉽게 이해가능

: 프로그램 갱신 및 유지 관리가 용이하다

: 문서화 하는데 있어서 근거가 됨

 

l  Pseudo Code(의사코드) : 코드를 흉내 내어 알고리즘을 써 놓은 코드

: 흉내만 내는 코드, 실제적인 프로그래밍 언어로 작성된 코드처럼 컴퓨터에서 실행할 수 없다.

l  Programming Language(프로그래밍언어) : Java, C등과 같은 언어

3.     변수와 지정문

l  변수 [ Variable ]

: 데이터를 저장할 수 있는 메모리 공간에 붙여진 이름

: 정수(int), 실수(float), 참거짓(Boolean), 문자(char)

: Bool형 : 논리 자료형, 참과 거짓을 표현하는데 사용 [ 참:1, 거짓 0 ]

l  상수 [Constant]

: 수식에서 변하지 않는 값, 변수와 반대

4.     반복문과 조건문

l  For문과 while문

-      For문 : 반복되는 부분을 제어 ex. For(초기값; 조건식; 증감값)

-      While문 : for문과 비슷 ex. While(조건식){ 명령문; }

l  조건문

-      If 문 : 조건 제시 후 참이면 문장 수행, 거짓이면 다음 문장 수행

Ex. If(조건식) 명령문1; else 명령문2;

5.     배열(Array)

l  동일한 자료형의 데이터를 여러 개를 저장하기 위해 한 번에 많은 기억공간을 만들어 놓고 사용하는 가장 기본적인 자료구조

l  행렬에 관한 문제나 탐색, 정열(SORT)등에 사용되며 대부분 많은 변수를 선언해야 하는 프로그램에 사용됨

l  배열은 차례대로 순차적으로 처리되며, 새로운 데이터를 삽입하거나 삭제하는 작업에는 경우에 따라서 전체의 데이터를 움직여야 하므로 시간이 많이 소요됨

6.     연결 리스트 ( Linked List )

l  배열이 시간적 단점을 보완하기위해 사용되는 자료구조이다

l  데이터들을 임의의 공간에 기억시키고 자료의 항목에 따라 노드의 포인터를 사용하여 서로 연결시킨 자료구조

l  노드(Node) : 연결리스트에서 원소가 저장되어 있는 곳

n  노드 = Data Field + Link Field

n  Data Field : 원소의 실제 값

n  Link Field : 다음 원소가 저장되어 있는 주소를 가리키는 Pointer

l  단순 연결 리스트, 이중 연결 리스트, 단순 원형 연결 리스트, 이중 원형 연결 리스트 등

l  장점 :

n  삽입 및 삭제의 용이

n  비연속적

l  단점

n  Access Time의 비효율성

n  추가 공간 필요, 중간 노드의 연결 끊김 시 다음 노드 찾기 X

7.     단순 연결 리스트 ( Singly Linked List )

l  하나의 노드를 데이터 부분과 링크 부분을 구성하여 링크 부분에 다음 노드를 가르키는 포인터를 저장, 마지막 노드의 링크부분에는 NULL링크를 저장

n  Head Node 에는 첫 번째 원소를 가리키는 주소

u  원소의 링크 부분에 의해 순서가 정해짐

u  링크의 값 : 다음 원소의 주소

8.     원형 연결 리스트 ( Circular Linked List )

l  마지막 노드의 링크 값이 Null 이 아닌 리스트의 첫 번째 주소를 가리키도록 하는 구조

9.     이중 연결 리스트 ( Doubly Linked List )

l  양쪽 방향으로 해당 노드를 검색하면 쉽게 찾을 수 있음

l  선행노드(Left Link) + 자료(Data) + 후행노드(Right Link)

l  양방향으로 특정 노드 검색 가능한 구조

10.  큐 ( Queue )

l  먼저 들어간 데이터가 먼저 나오는 FIFO구조로 저장하는 형식

n  FIFO [ 선입선출 ] = FCFS

n  빈 큐에서 데이터 삭제 시 Under Flow Error 발생

n  가득 찬 큐에서 데이터 삽입 시 Over Flow Error 발생

11.  스택 ( Stack )

l  제한적으로 접근할 수 있는 나열 구조이다. 접근 방법은 항상 목록의 마지막 부분에서 일어난다:

l  한 쪽 끝에서만 자료를 넣거나 뺄 수 잇는 선형 구조 ( LIFO )로 되어있다.

l  자료 밀어 넣는 것 ( PUSH ) , 꺼내는 것 ( POP )