본문 바로가기

🖋️ 자료구조와 알고리즘/알고리즘,자료구조15

이전 1 2 3 다음

[그래프] 위상 정렬, 최단 경로 위상 정렬 모든 간선에 대해 성질을 만족하는 순서로 작업을 정렬하는 것 위상 정렬은 싸이클이 없는 방향 그래프 G=(V,E) 에서 V의 모든 정덤을 정렬하되, '간선 (i->j)가 존재하면 정렬 결과에서 정점 i는 정점 j 보다 앞에 위치한다.' 라는 성질을 만족해야함 위상 정렬은 스케줄링이나, 가중치를 갖고 싸이클이 없는 방향 그래프의 최단 경로 찾기에도 쓰임 컴파일러에서 작업을 순차적으로 처리하기 위해서 사용되기도 함 최단 경로 모든 가능한 경로 중 최단 경로를 찾는 알고리즘 다익스트라 알고리즘 모든 간선 가중치가 양의 가중치인 싸이클 벨만-포드 알고리즘 음의 가중치를 허용하지만, 가중치 합이 양인 싸이클 다익스트라 알고리즘과 벨만-포드 알고리즘은 하나의 시작 정점으로부터 다른 모든 정점에 이르는 최.. 2023. 12. 8.

[그래프] 최소 신장 트리 (프림/크루스칼/유니온 파인) 연결 그래프 간선의 방향이 없는 그래프에서 모든 정점들 간에 간선을 따라 서로 다다를 수 있는 그래프 그래프 이론에서 '트리'란 "싸이클이 없는 연결된 그래프"로 정의됨 트리 최소한의 간선을 사용하면서 연결된 그래프 신장 트리 비용 그래프의 간선에 가중치가 있다면, 신장 트리를 구성하는 간선의 가중치를 다 더한 것 최소 신장 트리 가중치가 있는 무향 그래프로부터 만들 수 있는 모든 신장 트리 중, 비용이 가장 낮은 트리 프림 알고리즘 하나의 정점 집합을 점점 키워나가는 방식 크루스칼 알고리즘 여러 정점 집합으로 시작해서 집합들을 합쳐나가는 방식 프림 알고리즘 최소 신장 트리를 찾는다는 것은 궁극적으로 |V|-1개의 간선을 찾는 과정 프림 알고리즘은 아무 간선도 없는 상태에서 간선을 하나씩 더하는 작업을 .. 2023. 12. 8.

[그래프] 너비우선탐색 BFS & 깊이우선탐색 DFS 모든 정점을 방문하는 방법 : 너비우선탐색 BFS, 깊이우선탐색 DFS 너비우선탐색 BFS 먼저 루트의 자식을 차례로 방문함 다음으로 루트 자식의 자식, 루트에서 2개의 간선을 거쳐서 도달할 수 있는 정점 방문 루트로부터 3개의 간선을 거쳐서 도다랗는 정점들 4개, 5개... 순으로 방문함 깊이우선탐색 DFS 루트 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려감 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려감 BFS는 옆으로 쭉 훑어 나가고, DFS는 아래로(깊이) 갈 수 있는 데까지 갔다가 막히면 되돌아와서 다시 내려감 DFS에 기반한 탐색 방법을 백트래킹 이라고 부르기도 함 BFS 수행 순서 시작 정점으로 정해진 정점을 방문(1로 표시) 정점 1에 .. 2023. 12. 8.

[그래프] 그래프 표현방법 그래프 현상이나 사물을 정점과 간선으로 표현한 것 정점 대상이나 개체를 나타냄 간선 정점간의 관계를 나타냄 가중치를 주어 정도를 표현할 수 있음 그래프의 표현 전통적인 그래프 표현법에는 행렬을 이용하는 방법과 리스트를 이용하는 방법이 있음 인접 행렬 행렬 표현법은 이해하기 쉽고 간선의 존재 여부를 즉각 알 수 있음 n*n 행렬이 필요하므로 n^2에 비례하는 공간이 필요하고, 행렬 준비 과정에서 행렬의 모든 원소를 채우는 데만 n^2에 비례하는 시간이 든다 표현방법 정점 i 와 정점 j 사이에 간선이 있으면 행렬 (i,j) (j,i) 원소의 값을 1로 할당함 방향이 있는 경우 i->j 를 (i,j)로 표현 가중치가 있는 경우 원소의 값에 할당함 나머지 자리에는 0을 할당함 인접 리스트 각 정점에 인접한 정.. 2023. 12. 8.

[해시 테이블] 충돌 해결 충돌 어떤 키가 이미 자리잡고 있는 상태에서 다른 키가 삽입을 시도하는 것 동일한 주소에 2개 이상의 키가 해싱되는 상황 충돌 해결 방법 체이닝 개방 주소 방법 체이닝 같은 주소로 해싱되는 키를 모두 하나의 연결 리스트에 매달아서 관리함 해시테이블의 크기가 m이면 최대 m개의 연결 리스트가 존재할 수 있음 같은 주소로 들어온 키들은 해당 헤더 다음에 연결리스트로 매달려 있음 체이닝은 임의의 키를 삽입할 때 해시값이 가리키는 연결리스트에 삽입함 리스트의 맨 앞에 삽입하는 것이 좋음 키를 검색할 때 해당 연결 리스트의 키들을 차례로 지나가면서 찾음 적재율이 1을 넘어도 사용할 수있음 개방 주소 방법 체이닝과 달리 추가 공간을 사용하지 않음. 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결함 모든 키.. 2023. 12. 8.

[해시 테이블] 해시 테이블, 해시 함수 해시 테이블은 자료를 검색, 삽입, 삭제하는 데 평균시간이 가능하게 하여 극단적 효율에 다다른 자료구조 키 자신의 값에 따라 자리가 결정됨 해시 테이블은 키가 저장될 자리를 키의 '값'으로 결정하는 자료구조 해시 함수는 임의의 킷값을 입력으로 받아 주소 중 한 값을 리턴함(리턴값=해당 키를 저장하는 자리) 해시 함수 나누기의 방법 곱하기 방법 충돌 어떤 키가 이미 자리 잡고 있는 상태에서 다른 키가 삽입을 시도하는 것 동일한 주소에 2개 이상의 키가 해싱되는 상황 충돌 해결방법 체이닝 : 충돌을 일으킨 키들을 연결 리스트로 관리하는 방법 개방 주소 방법 : 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 것 검색 시간 체이닝, 개방 주소 방법으로 검색할 때의 기대시간 적재율 해시 테이블에 원.. 2023. 11. 30.

[트리] 균형 검색 트리 (AVL트리, 레드-블랙트리, B-트리) 균형 이진 검색 트리 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지해서 작업들이 항상 O(logn)시간을 보장함 AVL 트리 자가 균형, 높이 균형 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리 회전 연산 균형이 깨진 서브 트리 중 가장 낮은 곳에 있는 것부터 수선을 시작함 단일회전, 이중회전 AVL트리 운영 삽입과 삭제 새로운 노드를 삽입하거나 노드를 삭제할 때, AVL 트리는 불균형도를 체크하고 필요에 따라 회전을 수행하여 균형을 재조정 불균형도 체크 각 노드는 자신의 왼쪽과 오른쪽 자식 트리의 높이를 기반으로 불균형도를 계산. 불균형도가 1을 초과하면 균형이 깨진 것으로 간주 회전 유형 균형이 깨진 경우, LL, RR, LR, RL 네 가.. 2023. 11. 27.

이전 1 2 3 다음

티스토리툴바