정보 & 소식/자료구조, 알고리즘 (11) 썸네일형 리스트형 그래프(Graph) 그래프(Graph) 그래프는 노드(또는 정점) 사이에 연결(간선)을 이루어 만들어지는 자료구조이다. 관련이 있는 사물 또는 개념을 서로 묶은 것이 바로 그래프이다. 그래프의 구성요소 및 용어 그래프는 2개의 집합으로 구성 된다. 바로 정점과 간선이다. 정점 == 꼭지점 == 노드 == Vertex 그래프를 구성하는 요소로, 연결점 에 해당한다. 간선 == 선분 == 변 == 연결선 == 가지 == (Arc, Edge, Link) 두 정점을 이어주는 선분, 간선에 의해 이어진 두 정점은 서로 인접한다. 용어 경로 하나의 정점에서 다른 정점까지의 일련의 간선들 두 개의 정점 사이를 잇는 간선들을 순서대로 나열함 단순 경로 경로 상에서 시작과 끝을 제외한 중복되는 정점을 지나지 않는 경로 사이클(순환) 정점 .. 2020. 9. 14. 20:48 탐색 알고리즘 탐색 알고리즘 우리가 자료구조를 사용하는 이유는 근본적으로는 효율적으로 데이터(정보)를 저장하기 위함이지만, 결국 저장한 정보를 다시 탐색해서 찾아 쓰기 위함이다. 따라서 자료구조의 설계 또는 선택에는 저장 효율도 중요하지만, 이에 못지않게 탐색 효율도 고려해야 한다. 키 와 레코드 자료구조가 저장하는 데이터 하나의 단위를 레코드라고 한다면, 키는 레코드의 서브필드에 해당한다. 키는 자료구조의 내부 레코드들 간의 정렬, 또는 탐색에 활용되는 정보이다. cf) 서브필드(subfield) - 개념이 정해진 정보 단위를 수록하는 필드의 부분. 이진탐색 (Binary Search) 이진탐색은 이미 정렬되어있는 데이터를 기반으로 한다. 한 번의 탐색이 가해질 때 마다 문제의 크기를 반으로 줄임으로 써, 탐색의 범.. 2020. 8. 27. 11:58 우선순위 큐와 자료구조 힙 우선순위 큐 우선순위 큐는 들어온 순서에 상관없이 우선순위에 초점을 두어 처리하는 큐이다. 일반적인 큐나 스택은 이 우선순위 큐에 대해서서, 데이터가 입력 된 시간에 초점을 둔 경우라 볼 수 있다. 우선순위 큐 에서는 입력된 데이터에 Tag 값이 필요하다. 이것은 각 데이터 간에 우선순위를 결정하기 위해서 비교 되는 수치이다. 따라서 이러한 Tag 값은 곧 우선순위 값(Priority Value) 에 해당하며, 이 값을 큐의 키 값으로 한다. 배열에 의한 구현 데이터를 삽입 시에, 이진탐색을 통해서 위치를 정하게 되면, 매번 정렬된 결과를 낳는다. 데이터가 정렬이 되어있기 때문에 가장 마지막에 있는 값이 바로 우선순위가 가장 큰 값이므로 가장 마지막 데이터를 항상 꺼내주면 된다. 삽입 시의 효율로 자리를.. 2020. 8. 19. 21:20 알고리즘 과 빅오 표기법 알고리즘이란?알고리즘 이란 요리에 비유하자면 조리법에 해당함.즉 문제를 해결하기 위한 방법이며, 이것을 구체적으로 표현한 것이 프로그램이다. 알고리즘이 추상적 이라면, 프로그램은 구체적이다.알고리즘은 구현과 무관하게 추상적으로 기술되는 반면에, 프로그램은 구현 환경과 연관되어 기술된다. 알고리즘의 정확성알고리즘은 기본적으로 정확성을 지녀야 한다. 알고리즘 오류문법적 오류 단순히 구문상의 오류. C 문법에서 ;(세미콜론)을 붙이지 않았다던가... 의미상의 오류 구현하고자 하는 의미를 잘못 해석한 경우. 또는 문법에 대한 잘못된 이해로 작성된 알고리즘 논리적 오류 프로그램의 정확성을 해치는 가장 심각한 오류 프로그램의 정확성 증명샘플 테스트 프로그램에 오류가 있음을 증명할 수는 있으나, 프로그램에 오류가 없.. 2017. 3. 6. 16:39 레드블랙트리 - 삭제 레드블랙트리 삭제 레드블랙트리의 삭제는 기본적으로 이진탐색트리의 삭제에 기반 한다. 이렇게 노드를 삭제하고 나면, 무너진 레드블랙트리의 규칙을 복원하는 것에 초점을 둔다. 첫째로 삭제된 노드가 RED 인 경우 어떠한 추가 작업도 필요하지 않다. 왜냐면 규칙이 무너지는 경우는 RED 노드가 연속적으로 부모 자식 관계인 경우인데 RED 가 삭제되는 걸로는 해당 규칙을 벗어나지 않기 때문이다. 하지만 검은색 노드를 삭제하는 경우가 문제가 된다. 이때는 상황에 따라서 문제를 해결해 주어야 한다. Default 케이스 Default 케이스는 삭제가 일어나면 무조건 실행되는 케이스이다. 삭제된 노드가 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다. 삭제하려는 노드가 75 인 경우 그 자릴 대체할노드는.. 2017. 2. 2. 19:33 레드블랙트리(자가균형 이진탐색트리) 레드블랙트리 이진탐색트리의 불균형한 성장은 검색효율을 심각하게 떨어뜨린다. 이러한 불균형을 해결하기위한 방법은 스스로 균형을 복원하는 것이다. 레드블랙트리는 이러한 불균형을 스스로 복원하는 자가 균형 이진탐색트리이다. 레드블랙트리의 균형 복원 규칙 1. 모든 노드는 빨간색 아니면 검은색 2. 루트노드는 검은색 3. 리프노드는 검은색 4. 빨간 노드의 자식들은 모두 검은색. 하지만 검은색 노드의 자식은 빨간색일 필요 없음 5. 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일(약한 규칙) NIL 노드는 아무데이터도 가지고 있지 않지만 검은색으로 취급되는 더미노드(Dummy Node)이다. 새로 삽입되는 노드는 리프노드가 되는데, 이때 이 노드의 양쪽 자식으로 NIL 노드를 연결한다. 새로.. 2017. 2. 1. 13:21 자료구조 - 이진탐색트리 이진탐색트리이진트리의 노드는 왼쪽과 오른쪽으로 자식을 가집니다. 이러한 이진트리 중에서 탐색을 위해 고안 된 트리가 바로 이진탐색트리입니다. ● 이진탐색트리의 조건이진 탐색트리는 다음과 같은 조건을 가집니다. 1. 임의의 노드 N에 대하여, 왼쪽 하위에 있는 노드는 N 보다 값이 작고, 오른쪽 하위 노드는 N 보다 값이 커야 한다.2. 임의의 노드 N 의 왼쪽 하위 트리와 오른쪽 하위 트리 모두 이진 탐색트리여야 한다. 이진탐색트리의 모양 예시 이러한 이진 탐색트리를 중위순회 하게 될 경우 데이터가 정렬된 결과를 보입니다.트리의 순회에 대해선 저번 글을 참조해주세요~ ● 이진 탐색트리의 탐색 앞에서 설명한 대로, 이진 탐색 트리의 목적은 바로 탐색에 있습니다. 탐색하고자 하는 값을 찾을 때, 루트부터 시.. 2016. 8. 29. 23:30 자료구조 - 트리의 구현 트리의 구현● 배열에 의한 이진트리 구현일반적으로 이진트리는 배열로 구성하지 않습니다.배열로 구현하려면, 왼쪽 자식의 인덱스를, 그리고 오른쪽 자식은 어디인지 그 인덱스를 기록해두고,만약 자식이 없다면 인덱스 값을 -1로 두는 방식으로 자식이 없음을 표시합니다. 하지만 이렇게 배열로 구현을 하게 되면, 노드를 삭제 한 경우, 부모 노드에서 해당 삭제 한 노드를 가리키는 인덱스 값을 -1 로 수정해야 하고, 이 과정에서 어떤 노드가 부모였는지 탐색하는 과정이 발생하여 효율이 떨어지게 됩니다. 따라서 포인터 방식으로 구현을 선호하며, 배열 방식은 완전이진트리의 경우에만 사용합니다. ● 포인터에 의한 이진트리 구현 하나의 노드에, 자기 자신을 가리킬 수 있는 노드 포인터 타입을 2개 가지게 합니다.그리고 하나.. 2016. 8. 24. 23:44 다음
어소트락게임아카데미
