전체 글(103)
-
알고리즘[Graph]
그래프 소개 그래프는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조이다. -정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말한다. -간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍(u, v)로 표현함. 그래프는 정점들의 집합 V와 간선들의 집합E를 사용하여 (V, E)로 나타냅니다. - G =(V, E) V = {1, 2, 3, 4, 5} E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)} 그래프 용어 -방향성(유향) 간선(Directed edge) 1. 방향을 가진 정점의 쌍(u,v)으로 화살표로 표현하고 단방향을 가리킵니다. 2. 첫번째 정점u는 출발점을 의미하고 두 번째 ..
2022.07.23 -
알고리즘 트리(Tree)
AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다. 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다. AVL트리는 다음과 같은 특징을 가집니다. AVL 트리는 이진 탐색 트리의 속성을 가집니다. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다. 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다. AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다. (트리는 데이터 + 다음 데이터의 주소값을 갖는 형태) 시간 복잡도 트리의 시간..
2022.07.23 -
알고리즘 링크드 리스트(linked list)
알고리즘 링크드 리스트 -연결 리스트는 데이터와 포인트로 구성된 노드 간의 link을 이용해서 리스트를 구현한 자료구조입니다. 연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에 저장 되어 있지 않기 때문에 연결이 필요합니다. 그림을 설명 한다면..... - Head 는 리스트의 처음을 나타냅니다. - 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성돼 있습니다. - 각 노드는 next 포인터를 사용하여 다음 노드와 연결됩니다. - 마지막 노드는 null을 가리켜 리스트의 끝을 나타 냅니다. 시간 복잡도 시작 위치에 대한 삽입/삭제 = O(1) 1.0 마지막 위치에 대한 삽입/삭제 = O(1)-(마지막 요소 위치를 아는경우) 1.1 마지막 위치..
2022.07.23 -
알고리즘 [Sorting]
Bubble- 1개의 값을 가지고 비교하여 연산하는것 [1,5,4,3,2] 배열을 오름차순 으로 정렬할때 1과 5는 비교하고 5가 크기에 진행되지않는다 이후 5와 4가 비교하여 자리를 변경한다.[1, 4, 5, 3, 2] -> [1,4 3, 5, 2] -> [1, 4, 3, 2, 5] 이렇게 진행된다. 그다음으로는 4를 배열안에서 비교하며 돌아간다 그렇게 반복하여 [1,2,3,4,5] 라는 오름차순의 배열이 만들어 진다. 시간[O(n^2)] (좋은 방법은 아닌것같다.) Insertion- 삽입정렬 기준 index 는 1부터 시작한다. 기준 index에 인접한 이전 index부터, 기준 index의 값보다 작은 값을 만날때 까지 swap하다가 작은값을 만나면 종료한다. 한번 스캔이 끝나면, 기준 index..
2022.07.22 -
알고리즘 배열[Array]
배열[Array] 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다 대부분에 프로그램 언어에서 동일 타입의 데이터를 저장합니다. 예를 들어 배열이 "int"타입인 경우 정수 요소만 저장할 수 있으며 double, float, char 등과 같은 다른 타입의 요소는 저장할 수 없습니다. 배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 합니다. -연속된 메모리 공간에 데이터들을 순차적으로 저장된다. -인덱스는 0번 부터 시작됩니다. -배열의 크기는 4이므로 4개의 요소를 저장 할 수 있습니다. 시간복잡도 - 임의의 위치에 있는 원소를 확인/변경 = O(1) - 원소를 배열 끝에 추가 = O(1) - 마지막 원소를 제거 = (..
2022.07.22