알고리즘/알고리즘 이론3 [알고리즘 이론] 순열(Permutation) 순열 순열이란 n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말한다. 수학에서 순열은 서로 다른 n개의 원소에서 r개를 뽑아한 줄로 세우는 경우의 수이다. 순열의 개수는 n의 계승 n! 와 같다. 예를 들어 [1, 2, 3] 배열에서 2개의 숫자를 뽑는 순열은 아래와 같다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 1. SWAP을 이용한 순열 배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한 번씩 swap 한다. depth를 기준 인덱스로 하여 depth보다 인덱스가 작은 값들은 그대로 고정하고 depth보다 인덱스가 큰 값들을 다시 swap을 진행한다. ✍ 순열들의 순서가 보장되지 않는다. 코드 arr : r개를 뽑기 위한 n개의 값이 저장된 배열.. 2021. 1. 7. [알고리즘 이론] 그래프 DFS 와 BFS 그래프 기본 그래프 표현 방법 : 인접 행렬, 인접리스트 그래프 탐색 깊이우선탐색 (DFS, Depth First Search) 너비우선탐색 (BFS, Breadth First Search) DFS(깊이우선탐색) - 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법 - 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 package DFS; import java.util.Scanner; public class test01_DFS { static.. 2020. 2. 13. 큐(Queue) 큐(Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 - 선입선출구조(FIFO: First In First Out) : 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(First)된 원소는 가장 먼저 삭제(First Out)된다. 선언 - Queue queue = new LinkedList(); T에는 Wrapper class가 들어간다 - queue.poll() : 큐의 가장 앞에 있는 요소를 꺼낸다 - add() : 큐에 삽입 - peek() : 가장 먼저 큐에 들어간 요소 반환 - remove() : 가장 먼저 큐에 들어간 요소 삭제하면서 반환 - isEmpty() : 큐가 비어있는지 반환 - size() : 큐에 있는 요소의 크기 반환 원형 큐 - 1차원 배열을 사용.. 2020. 2. 3. 이전 1 다음
