본문 바로가기

자료구조6

이전 1 다음

[그래프] 위상 정렬, 최단 경로 위상 정렬 모든 간선에 대해 성질을 만족하는 순서로 작업을 정렬하는 것 위상 정렬은 싸이클이 없는 방향 그래프 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.

[스택] 배열 기반 스택과 연결 리스트 기반 스택 Stack 스택은 후입선출이라는 규칙에 따라 데이터를 저장하고 접근하는 선형 자료구조 사용 예시 : 웹 브라우저의 뒤로 가기 기능, 문자열 역순, 괄호 검사, 실행 취소 기능, 재귀 함수 호출 스택의 개념 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 원칙에 따라 작동하는 자료구조 이 원칙은 가장 마지막에 삽입된 요소가 가장 먼저 제거된다는 것을 의미함 스택 자료구조의 ADT(추상 데이터 타입) Push : 스택의 맨 위에 요소를 추가합니다. Pop : 스택의 맨 위에서 요소를 제거하고, 그 요소를 반환합니다. Peek : 스택의 맨 위 요소를 반환하지만, 제거하지 않습니다. IsEmpty : 스택이 비어 있는지 확인합니다. 배열 기반 스택 (Sta.. 2023. 11. 21.

[리스트] 배열 리스트와 연결 리스트 생활 속 리스트 예시 위시 리스트, 블랙 리스트, 서비스를 기다리는 사람 리스트 리스트 자료구조의 ADT(추상 데이터 타입) 리스트의 기본 정의 줄 세워져 있는 데이터 ADT i번째 자리에 원소 x를 삽입한다. i번째 원소를 삭제한다. 원소 x를 삭제한다. i번째 원소를 알려준다. 원소 x가 몇 번째 원소인지 알려준다. 리스트의 사이즈(원소의 총 수)를 알려준다. 파이썽능 리스트를 기본 자료구조로 제공하며, 위 작업보다 훨씩 더 많은 작업을 지원함 자바는 언어 자체에서 리스트를 java.util 패키지에서 제공함 배열 리스트 ArrayList 1. 구성요소 내부배열 : ArrayList는 내부적으로 배열(Object[])을 사용해 데이터를 저장. 이 배열은 필요에 따라 동적으로 크기가 조정됨. 용량 : .. 2023. 11. 21.

이전 1 다음

티스토리툴바