본문 바로가기

자료구조 C++

 (11)
위상 정렬 1. 위상정렬이란? 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미. 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 2. 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 3. 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같음. 1. 진입 차수가 0인 모든 노드를 큐에 넣음. 2. 큐가 빌 때까지 다음의 과정을 반복. 2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에..
크루스칼 1. 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미함. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이 됨. 2. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까요? N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 => 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치합니다. 3. 크루스칼 알고리즘 대표적인 최소 신장 트리 알고리즘 그리디 알고리즘으로 분류 구체적인 동작 과정 1. 간선 데이터를 비용에 따라 오름차순으로 정렬 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시..
그리디 알고리즘 1.그리디 알고리즘이란? 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 그리디 해법은 그 정당성 분석이 중요 => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 해야함. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음. 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다. 2. 그리디 알고리즘 문제예시 *거스름돈 : 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거스러 주면 됨 N원을 거슬러 줘..
DFS와 BFS 1. DFS(Depth-First Search)의 개념 DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같음 탐색 시작 노드를 스택에 삽입하고 방문 처리함 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복. 2. DFS 동작 예시 [Step 1] 그래프를 준비 (시작노드 : 1) [Step 2] 시작 노드인 '1'을 스택에 삽입하고 방문 처리 [Step 3] 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 ..
동적 프로그래밍(Dynamic Programming) - DP 1. 동적 계획법 (Dynamic Programming)이란? 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 하나의 문제는 단 한번만 풀도록 하는 알고리즘 2. 분할 정복과 차이점 * 분할 정복 - 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법 - 작은 문제에서 반복이 일어나는 부분이 없음 * 동적 프로그래밍 - 작은 부분 문제들이 반복되는것을 이용해 풀어나감 3. Dynamic Programming 방법 - 모든 작은 문제들을 한번만 풀어야 한다. - 푼 작은 문제의 정답을 어딘가에 메모해 놓음 - 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용 * 조건 작은 문제가 반복이 일어나는 경우 같은 문제는 구할 때마다 정답이 같음..
9. 우선 순위 큐 (Heap) 1. 우선 순위 큐 (Priority queue) 가장 우선 순위가 높은 원소가 가장 먼저 제거되는 큐 ex) 병원 응급실 * 우선 순위 큐의 연산 - 추가 (Push) 큐에 새로운 원소를 삽입함 새로운 원소의 위치는 그 중요도(priority)에 따라서 결정됨 - 제거 (Pop) 큐에서 가장 우선 순위가 높은 원소를 삭제함 - 탑 (Top) 큐에서 가장 우선 순위가 높은 원소를 찾음(삭제하지는 않음) * 정렬된 리스트를 이용한 우선 순위 큐의 구현의 성능 추가 (Push) : O(n) 제거 (Pop) : O(n) 탑 (Top) : O(1) * 추가와 제거의 성능을 향상시킬 수 있는 방법은? 이진 트리를 이용!! (heap) 2. 정의 * Heap 이진 트리를 기반으로 구현된 우선 순위 큐 완전 이진 트..
8. 이진 탐색 트리 (binary search tree) 1. 이진 탐색 (binary search) 복습 - 배열의 중앙값을 찾아서 배열을 반으로 분할하는 과정을 재귀적으로 반복하면서 key 값을 검색 *이진 트리와의 유사성 배열이 2개의 부분 배열로 재귀적으로 분할 분할 구조 - 배열 : (왼쪽 부분 배열) + 중앙 + (오른쪽 부분 배열) - 이진 트리 : (왼쪽 부분 트리) + 부모 노드 + (오른쪽 부분 트리) 재귀적인 구조 - 각 부분 배열이 또 분할됨 , 각 부분 트리가 또 분할됨 2. 이진 탐색 트리 정의 * 이진 탐색 과정에서 분할되는 배열을 이진 트리에 대응시킨 구조 이진 트리 모든 노드는 서로 다른 하나의 값(key)을 저장 왼쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 작음 오른쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 큼..
7. 트리(tree) 1. 개요 *배열 , 연결 리스트 , 스택, 큐의 공통점? 리스트형 자료구조 선형 자료구조 모든 원소는 인덱스에 대응 2개 이상의 관계를 표현하는데 한계 존재 - ex) 족보 , 파일 구조 , 의사 결정 => 계층 구조 * 계층 구조의 공통점? 하나의 근원(root)으로부터 파생됨 한 노드가 여러 개의 노드로 전파됨 순환하는 경로가 없음 2. 트리의 정의 루트(root)라는 특별한 노드가 하나 있음 모든 노드는 부모 자식 관계라는 1:1관계에 재귀적으로 연결되어 있음 3. 용어 Root node : 트리의 최상위 노드 , 부모 노드가 없는 노드 Leaf node : 자식 노드가 없는 노드 Internal node : Leaf node가 아닌 모든 노드 Parent node : 연결된 한 쌍의 노드들 중에..

티스토리툴바