알고리즘 1강 :: 모든 자료구조 구현은 배열과 연결리스트

알고리즘 1강을 보며 배운내용

 

 

알고리즘 준비

• 자료구조
• 프로그래밍 언어 능력
• 수학적 능력

이 있으면 잘 할 수 있다

 

 

컴퓨터 과학

컴퓨터로 문제를 해결하기 위한 학문

 

즉 알고리즘은

문제 해결을 위한 효율적인 레시피

컴퓨터로 문제를 풀기위해 알고리즘이 필요하다

 

 

자료구조

컴퓨터에서 데이터 사이 논리적 관계 표현, 조직화

 

자료구조, 알고리즘을 잘 이용하면

좋은 프로그램 만들 수 있다

 

기본 자료구조

• 선형
  한 줄로 줄 세울 수 있는 자료구조
  배열, 연결리스트, 스택, 큐
• 비선형
  줄 세울 수 없는 자료구조
  트리, 그래프

 

각 자료구조의 구성과, 삽입, 삭제 방법을 알자

트리, 그래프는 익숙치 않다

 

 

모든 자료구조는

배열 혹은 연결 리스트로 구현한다

아~ 단순해서 좋다

 

 

트리

• 노드의 차수: 각 노드가 가지고 있는 자식 노드
• 트리의 차수: 노드의 차수 중 가장 큰 것
• 리프 노드: 자식 차수가 없는 것
• 비단말 노드: 리프 노드 제외한 노드
• 레벨: 루트 노드(0)부터 거리
• 높이(깊이): 레벨 + 1
• 숲: 루트 노드 자르면 생기는 서브 트리

 

이진 트리

각 노드 차수가 2이하인 순서 트리

공백도 이진트리

특징과 종류도 알고 있자

 

 

그래프

정점과 간선의 집합

방향이 있으면 방향 그래프

(1, 2) === (2, 1)

없으면 무방향 그래프

<1, 2> != <2, 1>

 

이차원 배열로 구현하면 인접 행렬

연결 리스트로 구현하면 인접 리스트

 

그래프의 용어, 종류, 구현 방법 알아보자