본문 바로가기

CS/Datastructure & Algorithm30

트리 순회(Tree Traversal)란? 트리 순회 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한 번만 중복없이 방문해야 하는데, 노드를 방문하는 순서에 따라 세 가지로 나뉩니다. 전위순회(preorder) 중위순회(inorder) 후위순회(postorder) 전위 순회 [Preorder] 루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이 우선 순회(depth-first-traversal) 이라고도 합니다. 위 예시 트리에 전위 순회 방식을 적용하면, 1 - 2 - 4 - 5 - 3 이 됩니다. 중위 순회 [Inorder] 루트 노드에서 시작해서 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭 순회(symmet.. 2022. 4. 22.
우선순위 큐 (Priority Queue) 란? 우선순위 큐란? 각 요소가 우선순위를 갖고 있는 자료구조를 말합니다. 일반적인 큐와는 다르게, 입력된 순서와 상관없이 우선순위가 가장 높은 데이터를 가장 먼저 출력하게 됩니다. 우선순위 큐는 Heap을 이용하여, 구현된 자료구조입니다. 우선순위는 배열과 연결리스트로도 구현할 수도 있지만, 최악의 경우에 우선순위 찾기 위해 인덱스의 끝까지 탐색할 수 있기 때문입니다. Heap을 사용한다면, 새 데이터 삽입 시, O(log2N) 그리고 데이터 삭제 시, O(log2N) 입니다. 👇 배열, 연결리스트, 힙 시간 복잡도 비교 더보기 배열 : 우선순위가 높은 순서대로 배열의 가장 앞 부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것(삭제)은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지는 않습니다. 시간 .. 2022. 4. 22.
HashMap & HashTable Hash Algorithm 데이터를 다루는 기법 중에 하나로, 검색과 저장이 아주 빠르게 진행되는 자료구조입니다. 해쉬는 데이터를 검색할 때, 사용할 key 와 value(실제 데이터)가 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도는 O(1)에 수렴하게 됩니다. 해시가 왜 생겼을까요? 가장 기본적인 자료구조인 배열의 경우, 내부 인덱스를 이용하여 자료의 검색이 한 번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈 자리를 채우기 위해 이동해야 하므로 많은 시간이 소요됩니다. 또한, 연결리스트는 삽입, 삭제 시 인근 노드들의 참조 값만 수정해줌으로 써 빠른 처리가 가능했지만? 처음노드와 마지막 노.. 2022. 4. 18.
이분 그래프(Bipartite Graph)란? 이분 그래프 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다. 다시 말해서, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 합니다. 위 그림을 보면 빨간색, 파란색의 정점이 서로 인접하고 있으며, 같은 색끼리는 인접하지 않습니다. 그리고, 간선이 아예 없고 정점만 있는 경우도 이분 그래프가 됩니다. 이분 그래프는 현실에서도 굉장히 많이 사용하게 됩니다. 몇 가지 예시를 들자면, 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는 지를 관계로 나타낼 수 있습니다. 영화 예약 사이트 회원 - 좋아하는 장르 : 각각의 회원들이 어떤 장르의 영화를 선호하는 지를 나타낼 수 있습니다. 구직자 -.. 2022. 4. 15.
그래프, 인접행렬과 인접리스트 그래프 (Graph) 수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다. 쉽게 설명하면? 사물이나 추상적인 개념 간의 연결 관계를 표현한 것이라고 할 수 있습니다. 도시를 연결하는 도로망이나 사람들 간의 관계, 웹 사이트 링크 관계 등이 이에 해당하는 예시입니다. 그래프의 구성 요소 정점 (Vertex / Node) : 그래프에서 위치를 나타냅니다. 간선 (Edge / Link / Branch) : 그래프에서 위치 간의 관계를 나타냅니다. 즉, 각 정점(노드)를 연결하는 선(line)을 의미합니다. 인접 정점 (Adjacent Vertex) : 간선(Edge)에 의해 직접 연결된 정점을 의미합니다. G(V, E) : 그래프는 정점과 간선의 집합이므로 이건, 그래.. 2022. 4. 13.
그래프와 트리의 차이는? [ 그래프 (Graph) ] 2개 이상의 경로가 가능하다. 노드들 사이에 무방향 / 방향 에서 양방향 경로를 가질 수 있다. Self-Loop 뿐 아니라, Loop / Circuit 모두 가능하다. 루트 노드라는 개념이 없다. 부모-자식 관계라는 개념이 없다. 그래프 순회는 DFS나 BFS로 이루어진다. 그래프는 Cyclic 혹은 Acyclic 이다. 간선의 유무는 그래프에 따라 다르다. 그래프는 네트워크 모델이다. [ 트리 (tree) ] 트리는 그래프의 특별한 케이스이며, "최소 연결 트리" 라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. Loop 나 Circuit이 없다. 당연히 Self-Loop 도 없다 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드만.. 2022. 4. 4.
백트래킹(Backtracking) 이란? 백트래킹이란? 재귀적으로 문제를 하나씩 풀어가되, 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 (유망[promising]하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다. 백 트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면? 현재에서 더이상 나아기자 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사합니다. 여기서 더 이상 탐색할 필요 없는 상태(노드)를 제외하는 것을 가지치기(pruning) 이라고 합니다. 백트래킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있습니다. DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤, 다시 돌아와 그 .. 2022. 4. 1.
점화식 이란? 알고리즘을 공부하다가 점화식이라는 키워드가 나와서 알아본 정보입니다. 점화식이란 ? 수열의 각 항 간에 관계를 (단순 나열이 아닌 규칙으로) 표현한 관계식을 의미합니다. 좀 더 쉽게 이야기하면? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것입니다. 다시 말해 재귀함수의 구조를 갖는 알고리즘만 점화식으로 표현할 수 있습니다. - 수열의 N 번째 항(일반항) 을, - 그 앞의 항들에 의해 규칙적(종속적)으로 표현한 관계식을 말합니다. 어떤 점화식 표현이있을까 ? 점화식 특징은 ? 등식 또는 관계식 형태를 갖고있습니다. (단, 문제 제시 때는 초기값 또는 경계값이 반드시 필요합니다) 점화식 자체는, 간접적이고 부분적인 정보만 주어, 따라서 일반항을 구할 필요 있습니다. 점화식의 점근.. 2022. 3. 16.

티스토리툴바