어김없이 자료구조에 대해서 오늘도 공부하고왔는데..
점점 넘어야할 산이 왜이렇게 높은건지! 증말 나빠나빠!
오늘은 graph 와 tree 구조 + binary serch tree 까지 공부를 했는데
공부한거 맞지? 알고리즘 문제 풀 때 너무 어려웠다. 진심으로!!
일단 정리한걸 간단하게 정리해보도록 하려고한다.
Graph?
우리가 흔히 알고있는 그래프 말고! 거미줄처럼 여러개의 점들이 선으로 이어져있는 복잡한 네트워크망과 같은 모습을 그래프라고 부른다.
그래프는 여러개의 점들이 서로 복잡하게 연결되어있는 관계를 표현한 자료구조
점-> 정점(vertex)
이어지는 선 -> 간선(edge)
라고 부른다.
무향그래프(undirected graph): 두 정점이 단방향인 간선으로 표현되어있는 것
진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선을 개수로 나타낼 수 있다
인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현 (다른 정점에 들리지않고 바로 자기자신한테 돌아오는것!)
사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현 (정점을 돌고돌고돌아서 출발했던 정점으로 돌아오는 것!)
인접행렬 vs 인접리스트
인접행렬은 서로이어져있으면 1, 이어져있지않다면 0으로 표시하는데 한개의 큰 표 안에 구분을 하고있고, 가장 빠른 경로(shortest path)를 찾고자할 때 상요한다.
인접리스트는 쭉 정점을 이어서 어떤 정점과 인접한지 나열해서 볼 수 있다. 메모리를 효율적으로 사용할 때 주로 사용된다.
Tree?
거꾸로된 나무의 가지에 열매들이 매달려있는 모습을 상상하면 좋을 것 같다.
그래프의 여러 구조중 일방향의 그래프의 구조로 되어있다. 하나의 root로부터 여러개의 node들이 뻗어있는 형태를 보여준다.
데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조라고 정의 할 수 있다.
하나의 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조라고 볼 수 있기 때문에 사이클은 없다.
자식노드가 없다면 리프노드(leaf node)라고 부른다.
이런 트리구조의 데이터는 높이과 길이를 구할 수 있다, 루트로 부터 찾고자하는 노드까지의 거리를 레벨(level)이라고 부르고 특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이(depth)라고 표현한다.
Binary Search Tree
트리구조에서 자식노드가 최대 두개인 노드들로 구성된 트리를 이진 트리라고 부른다.
자주 사용되고 있다고 한다.
완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.(왼쪽는 노드가 무조건있어야함)
정 이진 트리: 각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다. (왼쪽오른쪽 모두 노드가 있는 상태 )
모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 정의한다.
현재 컴공에 대한 기초 지식의 필요성을 더더욱 느끼기 때문에
자료구조에 대해서는 조금 더 공부한 후에 블로그 내용을 추가할 예정!
일단 코플릿 문제풀다가 코피터지는 줄 알았다..
