Computer Science/Algorithm :: 알고리즘
알고리즘 1강 :: 모든 자료구조 구현은 배열과 연결리스트
HJPlumtree
2022. 2. 22. 11:34
알고리즘 1강을 보며 배운내용
알고리즘 준비
- 자료구조
- 프로그래밍 언어 능력
- 수학적 능력
이 있으면 잘 할 수 있다
컴퓨터 과학
컴퓨터로 문제를 해결하기 위한 학문
즉 알고리즘은
문제 해결을 위한 효율적인 레시피
컴퓨터로 문제를 풀기위해 알고리즘이 필요하다
자료구조
컴퓨터에서 데이터 사이 논리적 관계 표현, 조직화
자료구조, 알고리즘을 잘 이용하면
좋은 프로그램 만들 수 있다
기본 자료구조
- 선형
한 줄로 줄 세울 수 있는 자료구조
배열, 연결리스트, 스택, 큐 - 비선형
줄 세울 수 없는 자료구조
트리, 그래프
각 자료구조의 구성과, 삽입, 삭제 방법을 알자
트리, 그래프는 익숙치 않다
모든 자료구조는
배열 혹은 연결 리스트로 구현한다
아~ 단순해서 좋다
트리
- 노드의 차수: 각 노드가 가지고 있는 자식 노드
- 트리의 차수: 노드의 차수 중 가장 큰 것
- 리프 노드: 자식 차수가 없는 것
- 비단말 노드: 리프 노드 제외한 노드
- 레벨: 루트 노드(0)부터 거리
- 높이(깊이): 레벨 + 1
- 숲: 루트 노드 자르면 생기는 서브 트리
이진 트리
각 노드 차수가 2이하인 순서 트리
공백도 이진트리
특징과 종류도 알고 있자
그래프
정점과 간선의 집합
방향이 있으면 방향 그래프
(1, 2) === (2, 1)
없으면 무방향 그래프
<1, 2> != <2, 1>
이차원 배열로 구현하면 인접 행렬
연결 리스트로 구현하면 인접 리스트
그래프의 용어, 종류, 구현 방법 알아보자