Algorithm & Data Structure17 [자료구조] 그래프 표현 3가지 방법 (인접 행렬, 인접 리스트, 간선 리스트) 그래프는 정점(또는 노드)와 간선(또는 링크)들로 이루러진 자료구조를 말한다. 그래프의 표현 방법에는 3가지가 있다. 1. 인접 행렬(Adjacency matrix) 2. 인접 리스트(Adjacency list) 3. 간선 리스트(Edge list) 위 3가지 방법에 대해 정리하고자 한다. 인접 행렬(Adjacency matrix) 노드를 중심으로 그래프 표현하며, 2차원 배열을 자료 구조로 이용한다. 노드의 수가 n이라면 nxn 형태의 2차원 배열이 인접 행렬로 사용된다. 인접 행렬에서 행, 열은 노드를 의미하고, 값은 에지를 의미한다. 가중치 없는 그래프에서는 에지가 있다면 1을 보통 저장한다. 가중치 있는 그래프에서는 에지가 있을 때, 가중치를 저장한다. (이때, 가중치가 0인 것과 에지가 없는 경.. 2023. 3. 20. [알고리즘] 유클리드 호제법 - JAVA(자바) 유클리드 호제법 - 호제법: 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻어내는 방법 두 수의 최대 공약수(GCD: greatest common divisor)를 구하는 알고리즘 (두 수 a, b가 있을 때, (단, a>b) a%b=n에서 a와 b의 최대공약수와 b와 n의 최대공약수가 같다는 점을 활용) 두 수 a, b가 있을 때, (단, a>b) MOD 연산을 한다. (MOD 연산: 두 값을 나눈 나머지를 구하는 연산) 나머지가 0이 아니라면 두 수 중 작은 수인 b%(이전 연산의 나머지)를 한다. 이 과정을 반복하며 나머지가 0이 되면 그때 b자리에 있는 수가 최대공약수이다. 시간복잡도는 O(logN)이다. 두 수를 소인수분해 해서 공통된 소수를 찾는 방법은 O(N)이 걸리는데, 유클리드 호.. 2023. 3. 9. [알고리즘] 에라토스테네스의 체 - JAVA(자바) 에라토스테네스의 체(Sieve of Eratosthenes) 고대 그리스의 수학자 에라토스테네스가 만들어 낸 방법으로 체처럼 걸러낸다고 해서 붙여진 이름이다. 많은 수 중 소수를 판별해야 할 때, 사용하는 대표적인 알고리즘이다. 먼저 소수를 판별해야 하는 범위만큼의 크기를 가진 배열을 생성한다. 소수가 아닌 1은 제외한다. 가장 작은 소수인 2부터 시작해서 2를 제외한 2의 배수들을 제외한다. 다음 큰 소수인 3도 3을 제외하고 3의 배수들도 마찬가지로 제외한다. 이 과정을 반복한 후, 배열에 남아있는 수는 소수이다. 많은 수의 소수를 한번에 판별하고자 할때 유용하다. 많은 수의 소수를 반복문으로 구하게 되면 수행시간이 지나치게 길어질 수 있는데(시간복잡도 O(N²)), 에라토스테네스의 체는 반복하다보면.. 2023. 3. 1. [알고리즘] 그리디 알고리즘(Greedy Algorithm) - JAVA(자바) 그리디 알고리즘(Greedy Algorithm) 현재 상태에서 볼 때, 가장 최선인 선택지만을 고르는 방법이다. (그 선택지에서 전체에서 볼때도 가장 좋다고 가정) 먼저 그리디 알고리즘으로 해결이 가능한지 정당성 분석이 필요하다. (도출된 해가 최적의 해가 아닐 수도 있기 때문) 그리디 알고리즘으로 해결이 가능하다면 선택할 때마다 현재 상태에서 가장 최선인 선택지를 고른다. 탐욕법, 욕심쟁이 알고리즘이라고도 부른다. 매번 그 선택지가 전체 선택지에서 최선이 맞는지 검사할 필요가 없기 때문에 동적 프로그래밍 (DP)보다 훨씬 빠른 편이다. 그리디 알고리즘이 정당성을 만족하기 위한 조건 탐욕적 선택 속성(Greedy Choice Property): 이전의 선택이 현재 선택에 영향을 끼치지 않는다. 최적 부분.. 2023. 2. 21. [알고리즘] 이진 탐색(Binary Search) - JAVA(자바) 이진 탐색(Binary Search) 정렬된 배열에서 찾는 값과 중간값을 비교, 중간값보다 작다면 처음~중간값이전, 크다면 중간값이후~마지막으로 범위를 좁히고 탐색하다가 중간값이 찾는값이 될 때를 찾는 방법이다. 탐색할 배열을 정렬한다. 중간값 인덱스(mid) 값보다 찾는 값이 작다면 start(처음)~mid-1까지를 탐색범위로 하고 탐색한다. mid 값보다 찾는 값이 크다면 mid+1~end(마지막)까지를 탐색범위로 하고 탐색한다. 탐색 범위의 mid 값과 일치할 때까지 반복한다. 반복하다가 start > end가 된다면 찾는 값이 배열에 없다는 뜻이다. 정렬된 배열 안에서 특정 원소를 찾을 때 사용한다. 시간복잡도는 O(logn)이다. 탐색구간이 반씩 줄어들기 때문에 시간복잡도는 O(logn)이 된다.. 2023. 2. 17. [알고리즘] 너비 우선 탐색(BFS) - JAVA(자바) 너비 우선 탐색(Breadth-First Search) - 노드 수가 적고 최단 경로를 찾을 때 유리함 그래프의 시작 노드나 임의의 노드에서 시작해 가장 가까운 노드 부터 방문하면서 탐색하는 기법으로 그래프 완전 탐색 방법이다. BFS를 시작할 노드를 정한다. 시작노드와 가까운 노드부터 방문여부를 체크하며 방문한다. 가까운 노드를 먼저 탐색 -> dfs와 목표를 찾는 경로가 다수일 때, 최단 경로로 찾는다. 가장 가까운 노드들을 다 방문했다면 다음 깊이로 넘어가서 탐색한다. 모든 노드를 방문할 때까지 반복한다. *한번 방문한 노드는 재방문하지 않는다. 선입선출방식인 큐를 사용해서 구현한다. 시간복잡도 그래프를 인접리스트로 표현할 경우 O(V+E)이 된다. V: 정점(vertex) 수(=노드 수) E: 간.. 2023. 2. 14. [알고리즘] 깊이 우선 탐색(DFS) - JAVA(자바) 깊이우선탐색(Depth-First Search) - 노드 수가 많고 특정 노드를 찾을 때 유리함 그래프의 시작 노드나 임의의 노드에서 시작해 최대 깊이까지 방문한 후 그 전으로 돌아가 다른 연결된 노드를 탐색하는 기법이다. 임의의 노드의 분기에 대해 완전 탐색을 한 뒤, 다른 쪽 분기를 탐색 -> 그래프 완전 탐색 DFS를 시작할 노드를 정한다. 시작노드부터 노드의 방문여부를 체크하면서 방문한다. 아직 방문하지 않은 연결된 노드가 있다면 방문하고 더이상 없다면 가장 최근에 방문한 노드로 돌아간다. 돌아가서 다른 쪽 분기에 있는 인접한 노드를 방문한다. 모든 노드를 방문할 때까지 반복한다. *한번 방문한 노드는 재방문하지 않는다. 구현 방법에는 2가지가 있다. 재귀 함수를 사용해 구현하는 방법 (스택 성질.. 2023. 2. 10. [알고리즘] 퀵 정렬(Quick Sort) - JAVA(자바) 퀵 정렬(Quick Sort) 기준 값을 정하고 그 값을 기준으로 작은 값과 큰 값으로 부분리스트를 분할하고 정렬하는 과정을 반복한 뒤, 부분리스트의 길이가 1이 되면 합치는 정렬이다. 기준 값(pivot)을 정한다. (1.왼쪽 끝 2.가운데 3.오른쪽 끝 4. 랜) pivot을 기준으로 왼쪽 시작점(start)에서부터 큰값을 찾고 오른쪽 시작점(end)에서부터 작은 값을 찾는다. 왼쪽에서 큰값과 오른쪽에서 작은 값이 있다면 서로 교환한다. start와 end가 만나면 왼쪽 영역과 오른쪽 영역에서 각각 새로운 피벗을 선정하고 같은 작업을 반복한다. staer와 end 사이에 값이 1개라면 정렬이 종료된다. * 피벗을 왼쪽으로 선정했을 때, 이미 정렬된 배열(오름차순)이라면 피벗은 항상 부분 영역에 가장 .. 2023. 2. 5. [알고리즘] 버블정렬(Bubble Sort) - JAVA(자바) 버블정렬(Bubble Sort) 거품정렬이라고도 하며, 인접한 두 원소를 비교하며 정렬한다. 처음부터 인접한 두 원소의 크기를 비교한다. 더 앞에 있는 원소가 크다면 자리를 바꾼다. (아니라면 그래도 둔다.) 이 과정을 반복하며 정렬한다. 시간복잡도는 O(n²)이다. n개라면 첫번째자리 n-1번, 두번째 자리는 n-2번이 반복된다. 제자리 정렬(=입력받은 배열외에 다른 메모리가 필요하지 않은 정렬) 안정 정렬(=동일한 값에 대해서는 순서가 바뀌지않는다.) 배열 [6,3,4,1,5,2]이 있을 때, 삽입 정렬로 정렬하는 과정 (오름차순) 위 그림처럼 현재 원소와 인접한 다음 원소를 비교하며 현재 원소가 클 경우 위치를 바꾼다. 크지 않다면 바꾸지 않는다. -> 안정정렬이다. [구현코드 - JAVA] pub.. 2023. 2. 3. [자료구조] 큐(Queue) - JAVA(자바) 큐(Queue) 스택과 다르게 가장 먼저 넣었던 값이 가장 먼저 나오게 되는 선입선출(FIFO: Last In First Out) 형태이다. 한 쪽은 front, 다른 한 쪽은 rear로, front에서는 삭제 연산만 하고 rear에서는 삽입 연산만한다. 후입선출(LIFO: Last In Firat Out)인 스택과 다르다. Enqueue: rear 위치에 데이터를 삽입한다는 의미 Dequeue: front 위치에 데이터를 삭제한다는 의미 삽입,삭제, 읽기 연산의 시간복잡도는 O(1)이고, 탐색은 특정 데이터를 찾을 때까지 탐색하므로 O(n)이다. 그래프의 넓이 우선 탐색(BFS)시 사용된다. 자바에서 큐는 인터페이스로만 작성되어 있다. Queue 생성 예시 - 자바에서는 큐는 스택과 달리 인터페이스로만.. 2023. 2. 1. 이전 1 2 다음
