정렬의 방법은 여러 가지가 있다. 그중 대표적인 정렬인 거품, 선택, 삽입, 퀵, 병합 정렬을 자바로 구현해보고 시간복잡도와 장단점을 가볍게 정리해보려고 한다. 1️⃣ 거품 정렬 (Bubble Sort) 인접한 두 원소의 대소를 비교, 조건에 따라 (오름차순 or 내림차순) 교환하여 가장 뒤로 하나씩 보내는 방식 static void bubbleSort(int[] arr){ int size = arr.length; for(int i = size; i > 0; i--){ for(int j = 1; j arr[j]) { int tmp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = tmp; } } } } 시간 복잡도..
정렬된 범위 내에서 어떠한 값을 찾아야 할 때 이분 탐색 알고리즘을 이용하면 좀 더 빠른 속도로 찾을 수 있다. 위와 같이 오름차순으로 정렬된 숫자 배열에서 7을 찾아야 할 경우 배열 전체를 탐색하는 방법이 아닌 시작점과 끝점을 범위 내 양 끝으로 정의 시작점과 끝점을 더한 값을 2로 나눈 위치(중앙) 값과 찾는 값 비교 중앙값이 찾는 값보다 크다면 끝점을 중앙값의 이전값으로 초기화, 작다면 시작점을 중앙값의 다음값으로 초기화 2 ~ 3 반복, 시작점이 끝점 이상이 될 경우 종료 의 방법으로 해결할 수 있다. 위 그림에서 위와 같은 이분탐색을 활용할 경우 14, 6, 8, 7 총 4번의 탐색만으로 7을 찾을 수 있다. 이런 유형의 문제에서 범위의 기준을 어떻게 잡을지를 판별하는 것이 중요한데 대부분의 경..
2022.02.14 - [알고리즘, 자료구조/기본] - [알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기 [알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기 1️⃣ 순열 서로 다른 n개중에 r개를 선택하는 경우의 수 순서 O 경우의 수 : n! / (n-r)! // 순열 public static void permutation(ArrayList list, int count) { // 다 뽑았을 때 if (count == 0) { System.out.println(list); perCount+ hanyeop.tistory.com 위 글에서는 list를 활용하여 순열, 조합을 구했다. 하지만 결과 배열을 따로 선언해놓고 그 값만 바꿔준다면 더 효율적으로 계산할 수 있다. 순열..
플로이드 알고리즘 가중치가 주어진 그래프에서 모든 정점 사이의 최단경로를 구할 때 사이클이 존재하지 않고, 가중치가 음이거나 양인 경우 플로이드 알고리즘을 사용할 수 있다. 경유지 k와 두 점 i,j 선택 두점 사이 이동 시 i -> j 보다 k를 경유해서 가는 것이 더 빠르다면 최솟값 갱신 모든 경우에 대해 반복 모든 경유지에 대한 정점 사이의 최단 경로를 전부 확인하므로 O(V^3) (V는 정점) 의 시간복잡도를 갖는다. 예제 코드 (백준 11404) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는..
서로소 집합이란? 위처럼 집합간의 공통원소가 없는 집합을 말한다. 서로소 집합을 구하기 위해 노드를 합치는 연산 (유니온), 노드의 루트 노드를 찾는 연산 (파인드) 을 활용하는 유니온 파인드 알고리즘을 사용할 수 있다. 파인드 (Find) - 노드의 루트 노드 찾기 원소 각각의 부모 노드를 저장할 배열을 생성하고 자기 자신으로 초기화 한다. 최상위 노드에 도달할 때 까지 자기 자신의 부모 노드를 탐색한다. 위 과정에서 포함된 노드들의 부모를 전부 최상위 노드로 바꿔준다. val parent = Array(n + 1) {it} fun find(x: Int): Int{ return if (x == parent[x]) x else { parent[x] = find(parent[x]) parent[x] } }..
최단경로 구하기 가중치가 주어진 그래프에서 최단거리를 구할 때 가중치가 양수이고, 사이클이 존재하지 않을 경우 다익스트라 가중치가 음수를 포함하고, 사이클이 존재할 경우 벨만-포드 알고리즘을 사용할 수 있다. 다익스트라 알고리즘 시작노드를 설정하고 그 노드와 연결되어 있는 모든 노드들의 최단거리 테이블 갱신 그 연결된 정점중에 비용이 최소인 노드 선택 해당 노드에서 연결되어 있는 모든 노드들의 최단거리 테이블 갱신 2,3 번 반복 다익스트라 알고리즘에서는 항상 비용이 최소인 노드를 선택하기 때문에 그리디 알고리즘의 성격을 띈다. 따라서 1,2번 과정에서 선택된 노드의 최단거리 테이블은 변하지 않기 때문에 사이클이 존재하거나, 가중치가 음수일 경우 사용이 불가능하다. 하지만 항상 최선의 경우를 탐색하기 때..
최소 신장 트리란? ▶ 그래프의 모든 정점을 사이클 없이 잇는(신장 트리)트리에서 간선의 가중치의 합이 최소가 되는 트리 크루스칼 알고리즘이란? ▶ 간선 중심으로 최소 신장 트리를 구하는 알고리즘 (간선이 적을 때 프림 알고리즘보다 유리) 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선 선택 그 간선이 지금까지 만들어진 MST와 사이클을 형성한다면 제외, 아니면 MST에 추가 모든 간선에 대해 반복 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 예시 코드 (..
1️⃣ 순열 서로 다른 n개중에 r개를 선택하는 경우의 수 순서 O 경우의 수 : n! / (n-r)! // 순열 public static void permutation(ArrayList list, int count) { // 다 뽑았을 때 if (count == 0) { System.out.println(list); perCount++; return; } for(int i = 0; i < n; i++) { if(list.contains(arr[i])) { continue; } list.add(arr[i]); permutation(list, count - 1); // 뽑을 때 마다 count - 1 list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거 } } ar..
투 포인터 알고리즘이란? ▶ 1차원 배열에 존재하는 순차적 부분 배열에 접근해야 할 때 두개의 점을 활용하여 중복 연산을 줄이는 알고리즘 예시 문제를 활용하여 알아보자. 문제 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 연속되는 부분수열의 합이 M인 경우를 찾는 문제이다. 예제 입력 2의 1 2 3 4 2 5 3 1 1 2 의 경우를 살펴보면 단순 탐색 시 1 2 3 4 2 5 3 1 1 2 1 ..
문자열 단순 비교 문자열 검색 시 주어진 문자열이 ABACAABA 주어진 패턴이 ABACAB 인 경우를 가정하자. 일반적인 방식으로 비교할 경우 A B A C A A B A A B A C A B 문자 하나씩 비교하면 앞의 5가지 문자는 일치했지만 마지막 B가 달라서 매칭에 실패하게 되고, A B A C A A B A A B A C A B 한 칸 앞으로 가서 위와 같은 비교를 반복할 것이다. 눈으로 봐도 불필요한 연산이 다시 진행되는 것을 확인할 수 있다. 그러면 단순히 틀린 위치부터 탐색하면 되지 않는가? 라고 생각할 수 있지만 그렇게 비교하게 되면 3번째 위치가 A고 패턴의 시작도 A기 때문에 이 경우에 정답이 존재할 수도 있으므로 스킵하면 안된다. 그래서 접두사와 접미사를 활용하여 확실한 중복 연산들..
내 블로그 - 관리자 홈 전환 |
Q
Q
|
---|---|
새 글 쓰기 |
W
W
|
글 수정 (권한 있는 경우) |
E
E
|
---|---|
댓글 영역으로 이동 |
C
C
|
이 페이지의 URL 복사 |
S
S
|
---|---|
맨 위로 이동 |
T
T
|
티스토리 홈 이동 |
H
H
|
단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.