Jun's TID

Kruskal? Kruskal 알고리즘은 Greedy 기법을 이용하여 각 가중치를 간선에 할당한 그래프(어떤 비용을 가지고 있는 간선으로 이루어진 그래프)의 모든 정점을 최소 비용으로 연결하는 최적의 해를 구하는 데 사용하는 알고리즘이다. 글로만 설명하면 머리만 아프니, 바로 그림과 함께 예제를 보자. 위와 같이 간선과 노드, 그리고 각 간선이 가지는 비용으로 이루어진 그래프가 주어졌을 때, 우리의 임무는 각 노드들을 최소한의 비용으로 모두 연결하는 것이다. 그러나 여기서 각 연결은 서로가 맞물리는 상황(사이클)이 발생하지 않아야 한다. Kruskal 알고리즘의 기본적인 원리는 다음과 같다. 1. n개의 노드가 모두 연결되는 제일 작은 경우의 수는 n-1이다. 2. 비용 기준으로 오름차순 정렬하여 제일 ..

Union-Find 알고리즘은 합집합을 찾는다는 의미를 가진 그래프 알고리즘이며, Disjoint Set(서로소) 알고리즘이라고도 부른다. 구체적으로 여러 개의 수가 존재할 때, 각 수에 노드를 매긴 후, 현재 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. Union-Find 알고리즘을 이용하여 다양한 고급 알고리즘을 활용할 수 있으니, 심화적인 그래프 알고리즘을 다루기 전에 반드시 짚고 넘어가야 하는 알고리즘이다. 위와 같이 무작위 순서로 연결되어 있는 수의 집합을 순서대로 연결하기 위해서는 각 숫자들은 자신보다 작은 수를 자식으로 가지고, 큰 수를 부모 노드로 가질 필요가 있다. 이러한 노드의 순서는 두 개의 배열로 나타낼 수 있다. Array1: 각 수의 노드를 가지는 배열 ..

Greedy(탐욕) 알고리즘은 직전에 다뤘던 동적 계획법과 대조되는 개념으로, 큰 문제를 쪼갠 부분 문제를 전부 검토하여 정답을 도출하는 것이 아니라, 풀이를 진행하는 순간순간마다 최적이라고 생각하는 정답을 도출해내는 방법이다. 즉, 모든 경우의 연산을 전부 수행하여 "완전한 정답"을 찾기보다는 각 상황마다 최적이라고 생각하는 연산만 골라 수행하여 좀 더 빠르게 "근사치"를 찾는 기법이라고 할 수 있다. 예를 들어보면, 더보기 https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohi..

프로그래머스 연습 문제를 바로 들어가기 전에, 동적 계획법과 탐욕 알고리즘은 확실하게 짚고 넘어가야 할 거 같아서 따로 포스팅하기로 했다. 우선 동적 계획법 알고리즘부터 자세하게 다뤄보자. 1. Dynamic Programming? 동적 계획법이란 하나의 큰 문제를 쪼개어 부분적인 부분을 풀어 큰 문제를 해결할 수 있도록 고안된 알고리즘이다. 개념만 딱 들어보면 분할 정복과 다르지도 않은 것 같지만, 큰 차이점이 존재한다. 분할 정복 알고리즘은 큰 문제를 쪼개어 나온 부분 문제를 전부 해결하여 큰 문제에 대한 정답을 도출할 수 있었다면, 동적 계획법 알고리즘은 이미 도출한 부분 문제의 정답을 저장해놓았다가, 중복의 연산을 해야할 때 이를 스킵하고 저장한 값을 사용하여 좀 더 효율적인 연산이 가능하다. -..

완전 탐색 알고리즘에서 임의의 숫자로 되어있는 문자열을 준 뒤, 이 문자열에서 조합이 가능한 경우의 수를 뽑는 문제가 자주 나오는 것 같다. LV2 문제를 풀다가 도저히 선정리 없이는 풀기가 힘들고, 입사 코딩 테스트에도 등장할 개념 같아서 자세하게 다루고 넘어가려고 한다. {1,2,3,4,5,6,7}의 배열을 가지고 3자리의 수를 전부 뽑는다고 가정하면, {1, 2, 3}과 {3, 2, 1}을 같은 경우로 생각하냐 마냐의 2가지 경우로 나눌 수 있다. 1. 중복을 허용하는 수열 뽑기 수열은 123을 뽑는 경우와 321을 뽑는 건 다르다고 생각하는 경우이다. 즉, {1,2,3,4,5,6,7} 중 3개를 뽑는 "모든" 경우의 수를 구하는 개념이다. 재귀함수를 이용하여 코드를 작성하면, private sta..

어제부터 Sort를 이용하는 Programmers 연습 문제를 풀기 시작했는데, 어제 푼 문제가 LV1이여서 그런건지, 아니면 내가 java에 내장되어있는 sort()를 사용해서 그런건지 모르겠는데 역대급 낮은 점수인 2점을 받았다... 그렇게 심각한 문제는 아니지만, 혹시 sort 알고리즘을 내부에서 직접 구현을 안해서 그런거라면..? 하는 생각이 들어서 더 높은 LV의 sort문제를 풀기 전에 한번 정리를 하고 넘어가려고 한다. (Heap Sort는 이전 포스팅에서 한번 다뤘으니 따로 다루지는 않겠다.) 1. Bubble Sort 인접한 두 인자가 정해진 순서를 따르고 있지 않다면, 두 인자의 위치를 바꾸며 정렬을 진행하는 정렬 방법이다. 즉, 4 2 1 5 3 2 4 1 5 3 2 1 4 5 3 2..

그 동안 여러 코딩 테스트, 알고리즘 문제를 풀면서 다양한 자료 구조를 사용하긴 했지만, 따로 정리한 내용이 부족한 것 같기도 하고, 오늘 강의에서 Java의 Collection 에 있는 자료 구조를 전부 설명해 주시길래 정리해보려고 한다. 1. ArrayList: 워낙 기본적인 내용이기도 하고 많이 사용해서...자세한 내용은 Pass. package com.choonham.list; import java.util.ArrayList; import java.util.Iterator; public class ArrayListTestClass { public ArrayListTestClass() { // TODO Auto-generated constructor stub } public static void a..

분명히 3학년 때 알고리즘 강의를 수강하면서 한번 스쳐갔던(심지어 코드를 전부 암기했었던...) 개념이긴 한데 막상 활용해서 내 코드에 적용하려니 생각이 잘 안나서 다시 한번 정리할 겸 포스팅을 하려고 한다. 1. Heap Heap은 Priority Queue, Heap Sort 등을 구현하기 위해 사용되는 자료 구조로, 데이터의 정렬이나 검색 보다는 우선 순위의 있는 데이터가 무엇인지 알아내고, 삭제하는 데 좀 더 유용한 자료 구조이다. 정보처리기사를 공부하면 계속 나오는 개념 중 하나인 Binary Search에 사용하는 Binary Tree의 형식으로 보통 많이 쓰인다. Binary Heap은 가장 상위 노드의 최대 값을 갖는 Max Heap 과 최소 값을 갖는 Min Heap으로 각각 구현이 가능..