컴퓨터/알고리즘:자료구조8 [알고리즘] 분할정복 알고리즘 정리/분할정복을 알아보자/(코드 및 시간복잡도) 분할정복 분할 정복 알고리즘이란 분할하고 정복하는 것이다! 이게 무슨 소리냐? 분할 정복은 아래의 단계를 따른다. 단계 1. 문제를 더 작은 문제로 쪼갠다. 단계 2. 쪼갠 문제 각각을 해결한다. 단계 3. 해결한 작은 문제들을 병합하여 큰 문제를 해결한다. 이를 탑 다운 방식이라고 한다. Top-down방식은 큰 문제를 작은 문제로 분할하고, 작은 문제를 해결한 결과를 이용해 큰 문제를 해결하는 방식이다. (위에서 설명한 그대로이다.) 탑 다운 방식은 재귀 함수를 이용하여 구현할 수 있다. 참고로 재귀함수로 구현 가능한 것은 대부분(아마 전부?) 스택 + 반복문으로 구현이 가능하다. 분할정복 알고리즘 장점 분할 정복 알고리즘의 장점으로, 어려운 문제를 다소 쉽게 해결 할 수 있다는 점이 있다. 또한 작.. 2023. 4. 14. [자료구조] 그래프 자료구조 정리 및 구현/BFS, DFS 구현 코드 및 설명 그래프 자료구조 그래프란 노드와 노드 사이를 연결하는 간선으로 구성된 자료구조이다. 보통 수학에서 말하는 그래프와는 다른데, 수학의 그것은 차트라고 일컬어진다. 그래프는 아래와 같은 특징을 가진다. 그래프는 어떤 자료들의 관계를 표현하는 가장 일반적인 자료구조라고 할 수 있다. 그래프를 사용하는 예제 수도관 건설 교통망 구성 감염경로 먹이사슬 도로망 건설 그 외 그래프를 사용하는 현실의 예제는 아래의 사이트에 잘 정돈되어있다. http://snap.stanford.edu/data/ 그래프 자료구조의 특징 그래프의 특징은 아래와 같다. - 그래프는 정점(vertext, 혹은 노드)와 점점을 연결하는 변(Edge)로 구성된다. - 그래프는 순환구조 혹은 비순환 구조를 가진다. - 그래프는 방향이 있는 유향 .. 2022. 12. 10. [자료구조] C++트리 설명 및 구현(이진트리)/이진트리 구현 트리란? 트리란 확장된 반순서의 구조를 가지는 자료구조이다. 구조적으로 그래프와 선형 자료구조들 (벡터와 같은 것들) 사이에 있다고 볼 수 있다. 즉 트리는 1:N 비선형 계층형 자료구조이다. 트리에서 사용되는 용어는 아래와 같다. - node : 트리를 구성하고 있는 기본 요소(위 그림의 1, 2, 3 ...) - edge(간선) : 노드를 연결하는 선 - root node(루트 노드) : 부모가 없는 노드, 트리 구조는 단 하나의 루트 노드만을 가진다.(위 그림의 1) - leaf node(단말 노드) : 자식이 없는 노드(위 그림의 8, 9, 10, 11, 13, 14) - internal node(내부 노드) : leaf node가 아닌 노드, 즉 자식 노드를 하나 이상 가지는 노드 - subtr.. 2022. 11. 28. [자료구조] C++ list자료구조 정리/list 함수/list예시 C++ 리스트(list) C++의 List는 양방향 Container 자료구조이다. 리스트는 비슷한 정보를 논리적으로 연결시켜놓은 구조이다. 논리적으로 연결되어 있다는 말은, 물리적이지 않다는 것, 즉 내부의 자료들이 물리적으로 인접하지 않는다는 것이다. 물리적으로 연속된 자료구조의 예로 메모리 공간에 순차적으로 정렬하는 배열이 있다. 반면 List는 인접한 값들을 주소의 형태로 저장하여 가지고 있다. 즉, 서로 다른 위치에 존재하는 원소들이 pointer정보를 이용해 논리적으로 연결되어 있다. 리스트 선언, 생성 헤더: #include list listName; list listName(개수); //‘개수’의 크기를 가지는 리스트 생성, int형의 디폴트 값은 0, char은 ‘ ’ ...etc lis.. 2022. 11. 3. 이전 1 2 다음
