배열의 원소 접근 시간복잡도

배열의 원소 삽입 시간복잡도

배열의 원소 삭제 시간복잡도

연결리스트 원소접근 시간복잡도

연결리스트 원소 삽입 시간복잡도

연결리스트 원소 삭제 시간복잡도

어떠한 문제를 해결하기위한 여러 동작들의 모임

입력크기에 단위 연산이 몇번수행되는가 계산, 알고리즘의 수행시간을 측정하는 지표

입력 크기에 따라 작업 공간이 얼마나 필요한가 계산, 알고리즘의 필요 메모리를 측정하는 지표

알고리즘의 복잡도는()를 이용하여 나타낸다

어떤 데이터들이 주어졌을때 이를 정해진 순서대로 나열하는 문제

서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식

선택정렬의 시간복잡도

버블정렬의 시간복잡도

()의 경우 이미 정렬되어있는 데이터에 대해서는()의 시간복잡도를 갖고 최악의 경우에는()의 시간복잡도를 갖는다

데이터들이 정렬되어있으면서 그 안에 어떤 값을 찾고자 할때, 데이터의 중간값과 찾고자하는 값을 비교하여 대소관계에 따라 탐색 범위를 절반씩 줄여나가는 기법

이진탐색의 시간복잡도

전체 데이터의 크기를n이라고 할때 ()의 시간복잡도를 갖는다

프로그램이 자료를 저장하는 방식

책을쌓아두는 방식은

일렬로 자료를 저장하는 자료구조

대표적인 선형 자료구조

스택에서 자료가 저장되어있는 가장 마지막 위치

스택이 가득찼을때 원소 추가

스택 비어있을때 원소 꺼내려하는경우

자료가 삽입되는 끝을()라고함

자료가 삭제되는 끝

입의접근이 가능한것은

임의접근 불가능

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조

계층 관계를 갖는 자료들을 표현하기위해서는 ()를 활용할수있다

해군 조직도는 어떤 자료구조인가

트리의 최상위 노드

어떤 노드의 상위레벨에 연결된 노드

어떤 노드의 하위 레벨에 연결된 노드

동일한 부모노드를 갖는 노드

자료가 저장된 노드들이 간선으로 서로 연결되어있는 자료구조

트리에서 한 노드와 그의 자손들을 모두 모으면 그들도 하나의 투리가 된다 이렇게 자손들로 이루어진 트리를()라고한다

재귀적속성때문에 트리를 다루는 코드들은 대개 ()를 이용해 구현

자기 자신을 호출하는 함수

정점들과 정점 사이의 간선들로 구성되어있는 자료구조

그래프의 대표적인 표현방식

그래프에서 모든 정점쌍에 대한 간선의 정보를 저장하는 행렬

그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프 표현

그래프 탐색 알고리즘중 가장 널리사용되고있는 알고리즘

현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다 이과정에서 더이상 갈곳없는 정점에 도달하면 마지막에 따라어ㅏㅆ던 간선을 따라 뒤로 돌아간다

그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법

시작점에서 가까운 정점부터 순서대로 방문하는 탐색알고리즘

이진탐색의 시간복잡도

데이터를 삽입하고 삭제하는 과정이 한쪽 끝에서만 일어나는 형태의 자료구조

한쪽끝에서는 삽입, 한쪽끝에서는 삭제과정만 일어나는 자료구조

계층관계를 갖는 자료들을 표현하기위해 사용되는것