210623 알고리즘

자료구조란?

컴퓨터에서 어떤 문제를 해결하기 위해 자료의 특성에 따라서 자료를 분류하여 구성하고 저장해 놓은 것

 

자료구조의 형태

• 단순 구조 - 정수, 실수, 문자, 문자열
• 선형 구조 - 순차 리스트, 연결 리스트, 스택, 큐, 덱
• 비선형 구조 - 트리, 그래프
• 파일 구조 - 순차 파일, 색인 파일, 직접 파일

알고리즘이란?

알고리즘은 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술한 명세서

 

알고리즘의 표현 방법

• 자연어를 이용한 서술적 표현방법
• 순서도를 이용한 도식화 표현방법
• 프로그래밍 언어를 이용한 구체화 방법
• 가상코드를 이용한 추상화 방법

알고리즘과 프로그램의 차이는?

알고리즘은 어떤한 문제에 대한 해결 방법, 프로그래밍 언어, 컴파일러, 시스템에 비의존적

프로그램은 알고리즘을 구현하여 문제를 해결함 , 프로그래밍 언어, 컴파일러 시스템에 의존적

 

순차리스트 vs 연결리스트 

논리적 순서, 물리적 순서 같은 구조    메모리에 연속적으로 저장된다. 삭제, 삽입시 물리적 주소를 논리적 주소에 맞추기 위한 오버헤드 발생

각노드에 저장된 다음 노드 주소에 의해 연결된 구조 연속된 주소일 필요 없음 물리적 순서 맞추기 위한 오버헤드 필요없음

 

스택vs 큐

예시 명령어 insert 10, insert 20, insert 30, delete, insert 40, delete 인 경우

LIFO(Last In First Out) : 나중에 들어온 것이 먼저 나간다 맨위 가리키는 top 통해 요소 추가하는 push, 요소 삭제하는 pop 연산함

FIFO(First In First Out) : 먼저 들어온 것이 먼저 나간다 큐의 맨 앞을 의미하는 front에서 삭제, 맨 뒤를 의미하는 Rear에서 삽입 연산함

 

1차원 배열을 이용한 스택인 경우 스택의 변화과정

0123456

예시 명령어 insert 10, insert 20, insert 30, delete, insert 40, delete 인 경우

 

연결 리스트를 이용한 스택인 경우 스택의 변화 과정

012345

예시 명령어 insert 10, insert 20, insert 30, delete, insert 40, delete 인 경우

 

원형큐인 경우, 큐의 변화 과정

012345

예시 명령어 insert 10, insert 20, insert 30, delete, insert 40, delete 인 경우

연결리스트 이용한 큐인 경우, 큐의 변화과정

012345

예시 명령어 insert 10, insert 20, insert 30, delete, insert 40, delete 인 경우

이진트리

50,20,40,60,30,70 순으로 입력시

이진트리는 자식노드가 최대 2개로 구성된 트리

그림에서 동그라미 하나 즉 요소 하나를 노드라고 함, 노드들은 부모 자식 관계 형성

최상단의 (부모없는)노드를 루트노드 라고함, 트리안에 존재하는 트리를 서브트리라고 함

자식없는 노드는 단말노드, 있는 노드는 비단말노드라고 함, 노드가 가지고 있는 자식노드의 개수를 차수라고 함

루트부터 레벨 1로 내려갈수록 레벨 올라감 => 가장 높은 레벨 == 트리의 높이

배열표현식

전위 순회(Preorder Traversal) : 부모노드먼저 찍고 왼쪽 자식노드 방문, 오른쪽 자식노드 방문 

50, 20, 40, 30, 60, 70

중위 순회(Inorder Traversal) : 왼쪽 자식노드 방문 후, 부모노드 찍고 오른쪽 자식노드 방문

20, 30, 40, 50, 60, 70 

후위 순회(Postorder Traversal) : 왼쪽 자식노드 방문, 오른쪽 자식노드 방문후 부모노드 찍음

30, 40, 20, 70, 60, 50

즉 이름의 전, 중, 후 로 구분되는데 전,중,후의 의미를 담는 것이 부모노드 찍는 것

순회하면서 보통 출력하기에 출력 위치라고 생각해도 편함 

ex) preorder인 경우 

printf

preorder(cur->leftchild)

preorder(cur->rightchild) 이런식으로 코드가 나옴 

 

 

 

P.S. 알고리즘 수업의 정리긴한데 시작부분이라 자료구조의 복습이라 사실상 자료구조의 내용이라고 볼 수 있다