본문 바로가기

🖋️ 자료구조와 알고리즘26

이전 1 2 3 4 다음

[메서드] Deque 인터페이스 메서드 Deque 인터페이스는 자바의 java.util 패키지에 포함된 인터페이스로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 양방향 큐 이것은 스택과 큐 자료구조의 기능을 모두 통합한 형태로, 유연성을 제공하기 위해 설계되었음 void addFirst(E e): 요소를 데크의 앞쪽에 추가 void addLast(E e): 요소를 데크의 뒤쪽에 추가 boolean offerFirst(E e): 요소를 데크의 앞쪽에 삽입하고, 성공 시 true 반환 boolean offerLast(E e): 요소를 데크의 뒤쪽에 삽입하고, 성공 시 true 반환 E removeFirst(): 데크의 첫 번째 요소를 제거하고 반환 E removeLast(): 데크의 마지막 요소를 제거하고 반환 E pollFirst(): 데크.. 2023. 12. 14.

[메서드] Collections 클래스 주요 메서드 void sort(List list): 자연 순서대로 리스트 정렬 void reverse(List list): 리스트의 요소 순서를 역순으로 변경 Comparator reverseOrder(): 역순 자연 정렬 Comparator 반환 void shuffle(List list): 리스트의 요소를 임의의 순서로 섞음 T min(Collection list, int i, int j): 리스트 내 두 요소의 위치 교환 Collection unmodifiableCollection(Collection c, Object o): 특정 객체가 컬렉션에 나타나는 횟수 계산 int indexOfSubList(List source, List target): 하나의 리스트가 다른 리스트에 처음으로 나타나는 위치의 인덱스 반환.. 2023. 12. 14.

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

이전 1 2 3 4 다음

티스토리툴바