본문 바로가기
728x90

기타/알고리즘13

[알고리즘] 이분탐색 : Upper/Lower Bound(feat. Java) Upper/Lower Bound란 Lower/Upper Bound는 이분 탐색에서 나온 개념으로 이분 탐색은 분할 정복을 이용하여 원하는 값을 적은 시간복잡도로 구할 수 있는 유용한 알고리즘이다.(분할정복 모르시는 분은 아래 링크 참고!!) https://codingralro.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5-feat-Java [알고리즘] 분할정복 (feat. Java) 분할정복 알고리즘이란 분할정복 알고리즘은 그대로 해결할 수 없는 큰 문제를 작은 문제로 분할하여 작은 문제부터 정복하여 결국에는 큰 문제를 해결하는 알고리즘이다. 대표적인 분할정복 codingralro.tis.. 2023. 10. 13.
[알고리즘] 크루스칼(Kruskal) 알고리즘(feat. Java) 크루스칼 알고리즘 크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 최소 비용 신장 부분 트리란, 노드와 비용을 가지는 간선으로 이루어진 그래프에서 모든 노드를 방문하는 경로 중 최소 비용을 가지는 경로를 갖는 부분 트리를 뜻한다. 작동 방식 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 또한, union find(서로소 집합) 알고리즘을 이용하기 때문에 사전에 공부를 해 두는 것이 이해에 도움이 된다. 주어진 그래프의 모든 간선을 간선의 연결비용을 오름차순 정렬 정렬된 간선 순서 대로 선택하면서, 간선의 양 끝 점을 Union한다. 이때에, 두 정점 모두 같은 집합에 있다면 포함X 이를 통해 최종적으로 선택된 간선을 연결한 것이 최소 비용 신장.. 2023. 10. 11.
[알고리즘] 슬라이딩 윈도우 알고리즘(feat. Java) 슬라이딩 윈도우 알고리즘 슬라이딩 윈도우 알고리즘은 1차원 배열을 2회 이상 반복 탐색해야 할 때의 문제점인 시간복잡도(O(n^2))를 O(n)으로 줄일 수 있는 유용한 알고리즘이다. 이름처럼 1차원 배열에서 고정된 윈도우 사이즈만큼의 부분 배열이 특정 조건을 일치하는 지 처음부터 끝까지 슬라이딩하며 탐색하는 알고리즘인 것이다. 슬라이딩 윈도우 알고리즘의 경우, 윈도우 사이즈가 고정적이기 때문에 구현을 하는 것도 쉽다. 간단하게 단계를 서술하면 다음과 같다.(아래 그림 참고) 윈도우 사이즈만큼의 배열의 값들을 집어넣음(list, queue, ...) 배열의 오른쪽으로 한칸 슬라이드 슬라이드 되었으므로 부분배열의 첫부분은 삭제, 추가된 부분의 값 추가 문제풀이를 통한 코드 이해 풀이할 문제는 프로그래머스 .. 2023. 10. 11.
[알고리즘] 탐욕(그리디) 알고리즘 탐욕 알고리즘(greedy algorithm) 그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위해 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념입니다. 그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불립니다. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘입니다. 물론 모든 경우에서 그리디 알고리즘이 통하지는 않습니다.(그리디 알고리즘은 단순히 지금 최선의 선택이 전체적으로도 최선의 선택이길 바랄 뿐이기 때문입니다) 쉬운 예를 들자면 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 .. 2023. 9. 26.
[알고리즘] 분할정복 (feat. Java) 분할정복 알고리즘이란 분할정복 알고리즘은 그대로 해결할 수 없는 큰 문제를 작은 문제로 분할하여 작은 문제부터 정복하여 결국에는 큰 문제를 해결하는 알고리즘이다. 대표적인 분할정복 알고리즘을 이용한 정렬 알고리즘은 퀵 정렬, 합병 정렬, 이진 탐색 등이 있다. 아래의 정렬 알고리즘 비교 표를 보면 알 수 있듯이 분할정복 알고리즘을 사용할 경우 적은 시간복잡도로 인해 실행시간이 빨라진다는 장점이 있다. 정렬 알고리즘 최대 실행 시간 최소 실행 시간 평균 실행 시간 선택 정렬 O(n^2) O(n^2) O(n^2) 삽입 정렬 O(n^2) O(n) O(n^2) 합병 정렬 O(nlogn) O(nlogn) O(nlogn) 퀵 정렬 O(n^2) O(nlogn) O(nlogn) 여기서는 정렬 알고리즘을 예로 들었지만 .. 2023. 9. 24.
[알고리즘]세그먼트 트리(feat. Java) 세그먼트 트리(Segment Tree) 세그먼트 트리는 트리 형태의 자료 구조를 사용하여 숫자가 저장된 배열이 존재할 때 해당 배열의 구간 합을 구하거나, 배열의 특정 인덱스의 값을 변경한 후에 다시 구간합을 구해야 하는 경우에 적은 시간 복잡도로 작업을 진행할 수 있도록 해주는 트리 구조이다. 즉, 세그먼트 트리에는 특정 구간 배열의 합들을 노드에 저장해 놓는 형태인 것이다. 예를 들어 배열의 크기가 10일 때 세그먼트 트리의 각 노드는 다음을 의미한다. 리프 노드는 배열의 각 인덱스의 값을 나타내고 (0번 노드는 배열[0] 값) 리프 노드 이외의 노드는 왼쪽 자식과 오른쪽 자식의 합, 즉 구간합을 나타낸다. 이렇게 트리를 구성할 경우, 특정 인덱스의 값이 바뀌어도 구간합의 변경이 O(logN)의 시간.. 2023. 9. 24.
[알고리즘]그래프6 - 벨만포드(feat. Java) 벨만-포드(Bellman-Ford) 알고리즘 그래프 최단 경로를 구하기 위한 알고리즘 하나의 정점에서 출발하는 최단 거리를 구함 음수 싸이클 없어야 함, 음수 가중치는 허용 O(mn) 시간 복잡도 과정 dist : 출발지로부터 최단 거리를 기록하는 1차원 배열. 출발지는 0 / 나머지는 무한으로 초기화 정점의 개수 n만큼 아래를 반복 간선 m개를 하나씩 살펴본다. 현재 간선의 가중치를 cost(v, w)라고 하면 dist[v]는 지금까지 계산한 출발지에서 v까지 최소 거리이다. dist[v]가 무한대가 아니라면 아랫단계 진행 지금까지 계산한 dist[v]와 dist[v]+cost(w, v) 중 최솟값을 다시 dist[v]에 할당 n = 5, m = 9, 출발 정점은 4 dist 배열에 무한이 아닌 값은 .. 2023. 9. 23.
[알고리즘]그래프5 - 다익스트라(feat. Java) 다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘 하나의 정점에서 출발하는 최단 거리를 구함 음수 가중치 X 가정 배열로 구현 그래프의 경우 : O(n^2) 우선순위 큐 사용 -> O(mlogn) 과정 아직 방문하지 않은 정점 중 출발지로부터 가장 거리가 짧은 정점을 방문 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신 pq : 우선순위 큐, 정점과 출발지에서 정점까지 가는 최소 거리를 저장, 거리가 짧을 수록 우선순위 높음 check : 정점을 방문한지 체크하는 배열 dist : int 배열로 출발지에서 최소 거리를 기록 출발지 4를 우선순위 큐에 넣음, 출발지이므로 거리는 0 우선순위 큐에서 하나 꺼내 nowVertex에 저장하고 방문체크, now.. 2023. 9. 22.
[알고리즘]그래프4 - BFS(feat. Java) BFS란? 저번 글에서 알아본 DFS는 깊이 우선 탐색이었다면 BFS(Breadth-First Search) 너비 우선 탐색으로서 DFS와 함께 코딩 문제에 단골로 등장하는 그래프 탐색 알고리즘이다. DFS는 제일 깊이 있는 노드까지 탐색한 뒤에 돌아오는 방식이면, BFS는 인접한 노드를 먼저 탐색을 하는 알고리즘이다. 그렇기 때문에 재귀(Stack 구조)를 활용하여 구현했던 DFS와 달리, BFS는 Queue를 통해 구현을 하게 되고 Queue를 생각하면 이해하는 것도 쉽습니다. 저번 시간에 다루었던 예제를 또 다루어보면, 1번 노드를 큐에 넣은 후 방문처리 큐에서 노드를 꺼낸 후 인접 노드를 큐에 넣고 방문 처리 바로 위의 과정을 반복 1번 노드 꺼낸 후 2, 3, 8번 노드가 큐에 들어감 (Queu.. 2023. 9. 21.
[알고리즘]그래프3 - DFS(feat. Java) DFS란? DFS란 그래프를 순회하는 알고리즘 중 하나이다. Depth-First Search의 줄임말로 깊이 우선 탐색이라고 한다. 이름에서 알 수 있듯이 연결된 노드(정점 : vertex)를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들이 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색을 한다. 예를 들어 다음 그림에서, 1번 노드에서 DFS를 사용하여 탐색을 진행한다고 한다면, (연결된 노드가 여러개라면 오름차순으로 방문한다고 가정) 1번 노드 방문 후 2, 3번 노드 중 2번으로 방문 2번 노드 방문 후 6, 8번 노드 중 6번으로 방문 6번 노드 방문 후 더 이상 연결된 노드가 없으므로 2번으로 돌아감 2번 노드에서 방문하지 않았던 8번으로 방문 8번 노드 방문 후 연결된.. 2023. 9. 21.
[알고리즘]그래프2 - 구현(feat. Java) 2차원 배열 2차원 배열을 사용하여 정점에서 다른 정점으로 가는 간선의 존재유무(1 : 존재, 0 : 없음)를 알 수 있다. 2차원 배열을 사용할 경우 연결된 정점을 찾기 쉽고 구현이 쉽다는 장점이 있지만 O(n^2)의 공간 복잡도를 가진다는 단점이 있다. 구현 코드 public static void main(String[] args) { int[][] edges = new int[][] { {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5} }; int n = 5; //정점의 개수 int[][] matrix = new int[n + 1][n + 1]; for(int[] edge : edges) { //무방향 그래프이기 때문에 양쪽 모두 1로 초기화 matrix[edge[.. 2023. 9. 21.
[알고리즘] 그래프1 - 그래프란? 그래프란? 그래프는 정점(노드, Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 의미이다. 위의 그림에서, V(G) = {1, 2, 3, 4, 5}이고, E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} 이다. 그래프의 종류 무방향 그래프 이름 그대로 간선에 방향이 없는 그래프이다. 그렇기 때문에 정점 v와 정점 w를 잇는 간선 (v, w)가 있다고 하면 (w, v)도 같은 간선이 되는 것이다. 그러므로 정점이 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다. 방향 그래프 간선에 방향이 있는 그.. 2023. 9. 21.
728x90
반응형

티스토리툴바