MergeSort - 합병 정렬합병(병합) 정렬은 문제를 분할하고 분할한 문제를 다시 합치는 과정에서 정렬을 수행하는 알고리즘이며 분할 정복(Divide and Conquer) 알고리즘을 기반으로 두고 있다. 시간복잡도는 모든 상황에서 O(nlog(n))의 시간복잡도를 가진다. 합병 정렬은 문제 분할 후 데이터를 비교하면서 찾기 때문에 비교 정렬이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 제자리 정렬이 아니다. 예제코드public class MergeSort { private static final Logger logger = Logger.getLogger(MergeSort.class.getName()); private static int[] arr; p..
Kruskal AlgorithmKruskal 알고리즘은 최소신장트리 MST(Minimum Spanning Tree)를 구하는 알고리즘이다. Greedy하게 N개의 정점을 N-1개의 간선을 이용해 최소 비용으로 연결한다. Kruskal 알고리즘의 기본 개념은 Greedy이기 때문에 간선 정보를 가중치 기준으로 오름차순 정렬한다. 다음으로, Union-Find 알고리즘을 이용해 모든 N개의 정점을 N-1개의 간선을 통해 최소 비용으로 연결할 수 있다. 따라서, Kruskal 알고리즘은 Greedy + Union-Find 알고리즘의 개념을 합쳐놓은 알고리즘으로 최소신장트리를 구하는데 이용된다. [Data Structure] Minimum Spanning Tree - 최소 신장 트리노드의 갯수가 n개일때, 간..
Union-Find Union-Find 알고리즘은 서로소인 부분집합(그래프)을 표현하기 위한 알고리즘이다. union(x, y), find(x) 연산으로 이루어져 있으며 union(x, y)는 노드 x와 노드 y를 루트노드로 가지는 각 집합을 합하는 연산을 의미하고 find(x)는 x가 속한 집합의 루트노드를 확인하는 연산을 의미한다. Union-Find 알고리즘을 구현하기 위해서 필요한 자료구조는 각 노드의 부모노드를 저장하기 위한 배열이 필요하다. Union-Find 코드 public class Main { private static int[] parent; public static void main(String[] args) { parent = new int[N+1]; //union-find에 사용..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 기존코드 class Solution { //시작 좌표 private int sx, sy; //이동 변화값 배열 private int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //노드 방문 기록 배열 private boolean[][] vis; //최소 시간 기록 변수 private int answer = Integer.MAX_VALUE; public void init(String[] maps) { for(int i=0; i
Two Pointer Algorithm 투 포인터 알고리즘은 연속되는 1차원 배열 또는 리스트를 순차적으로 접근할때 사용하는 알고리즘이다. 이름 그대로 시작점과 끝점을 가리키는 두 개의 포인터를 이용하여 부분배열을 탐색한다. 투 포인터 알고리즘을 사용하는 이유는 당연히 배열 탐색시 시간복잡도에서의 효율을 위해서이다. 예를 들어, 길이가 100인 배열(0 포함)에서 합이 15가되는 부분배열 중 길이가 가장 짧은 배열을 찾아야한다고 해보자. 첫번째 원소부터 차례대로 탐색한다면 99번 원소에 15가 있다고 할때 최악의 경우로 약 O(n^2/2)의 시간복잡도를 가질 것이다. 투 포인터 알고리즘의 예제와 투 포인터 알고리즘을 사용한다면 시간복잡도가 어떻게 나오는지 살펴보자. 아래는 투 포인터 알고리즘을 적용할 ..
개요 알고리즘 문제를 풀면서 대진표를 짜는 문제를 마주한적이 있었는데 무작정 중첩 for문을 돌렸던 기억이 있다. 당연히 코드는 엉망이 되었고 문제도 겨우겨우 풀어서 제출했었는데 이번에 조합을 구하는 문제를 풀어보면서 조합을 구하는 알고리즘을 제대로 정리해야겠다는 생각이 들었다. 재귀를 이용한 조합 알고리즘을 이해하고 언제든 활용할 수 있도록 정리해보도록 하자 Combination 구하기 조합은 nCr에 대한 내용만 이해하고 있다면 재귀를 이용해 손쉽게 구현할 수 있다. 코드상으로 조합의 대상이되는 n의 크기를 가진 배열과 깊이 r의 재귀를 이용해 nCr, n개의 원소 중 r개를 중복없이 선택하는 조합을 만들 수 있다. A, B, C, D, E 5개의 팀이 있다고 할때, 모든 팀이 다른팀과 1번씩..
목표 알고리즘 문제를 풀면서 약수·최대공약수·최소공배수를 구하는 문제를 만났는데 기본적으로 구현을 할 수는 있지만, 관련 공식을 쓰지 않아 매우 비효율적으로 답을 찾고 있다는 것을 깨달았다. 약수·최대공약수·최소공배수를 구하는 경우는 생각보다 자주 보이기때문에 이 기회에 정리해두려고 한다. 해당 문제를 만나면 공식을 쓸 수 있도록 이해하고 코드로 정리해보자. 약수(Divisor) 구하기 12의 약수를 구한다고 할때, 처음 약수를 구할때는 아래와 같이 1부터 12까지 반복문을 돌려서 나머지가 0이되는 숫자를 찾는 식으로 접근했다. 하지만, 이렇게 접근하면 O(n)의 시간복잡도를 가지게 되는데 n이 커지고 문제가 복잡해진다면 분명 매우 큰 시간을 잡아먹을 것이다. List divisor = new Arr..
목표 알고리즘 문제를 풀면서 DFS를 정리한 글로 정리한 적이 있다. BFS 또한, 완벽하게 알고있어야하는 알고리즘이라고 판단되어 DFS와 반대되는 탐색 개념인 BFS 그래프 탐색 알고리즘에 대해 이해하고 하고자 한다. DFS의 개념이 부족하다면 아래 글을 읽고 오면 좋다. https://zzzzseong.tistory.com/23 [Algorithm] DFS - 깊이 우선 탐색 목표 Greedy, Dijkstra, DP 알고리즘과 같이 대표적인 알고리즘 중 하나인 DFS 그래프 탐색 알고리즘에 대해 이해하고 학습한다. DFS(Depth First Search)란 DFS(Depth First Search) DFS란 초기 노드에서 시작하여 해 zzzzseong.tistory.com BFS(Breadth..
목표 Greedy, Dijkstra, DP 알고리즘과 같이 대표적인 알고리즘 중 하나인 DFS 그래프 탐색 알고리즘에 대해 이해하고 학습한다. DFS(Depth First Search)란 DFS(Depth First Search) DFS란 초기 노드에서 시작하여 해를 찾을때까지 자식 노드를 계속해서 타고 들어가며 탐색하는 완전탐색 알고리즘이다. 깊이(Depth)의 노드를 우선적으로 탐색하는 BFS와 반대되는 개념이라고 생각하면 이해하기 쉽다. DFS는 Stack 또는 재귀를 이용해 구현할 수 있는데 재귀를 이용해 구현하는것이 일반적이다. BFS에 대한 개념이 부족하다면 아래 글을 읽고 오면 좋다. https://zzzzseong.tistory.com/22 [Algorithm] BFS - 넓이 우선 탐색 ..
