자바 프로그래밍/알고리즘(Algorithm) 검색 결과

해당 글 15건

알고리즘 - 분할정복(Divide & Conquer)

1. 분할정복 이란? 알고리즘 디자인 패러다임 중 하나이다. 정의 : 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법 분할정복 방식으로 해결되는 문제들은 예를 들면 다음과 같다. ① 정렬문제(퀵 정렬 - 참조, 병합 정렬 - 참조) ② 큰 숫자 곱하기(Karatsuba 알고리즘) : n자리 수 2개를 곱하여 결과를 나타내는 알고리즘 ③ 이진 탐색(Binary Search - 참조) ④ Closest Pair of Points 문제 : 모든 point의 쌍의 거리 중 최소의 거리를 찾는 문제 ⑤ Strassens's 알고리즘 : 두 행렬을 곱하는 ..
자바 프로그래밍/알고리즘(Algorithm) 2021. 5. 27. 20:43

알고리즘 - Quick(퀵) vs Merge(병합) 정렬(+TCO, 참조 지역성)

해당 포스팅은 표준(Standard)적인 퀵 / 병합 정렬의 경우에 대해 설명합니다. 각 정렬 방식의 응용에 따라 다양한 Variation이 있는 부분은 감안하지 않았습니다. 퀵 정렬과 병합 정렬 차이 우선 기본적으로 퀵 / 병합 정렬이 무엇인지 다시 한 번 간단히 알아보자.(관련 포스팅은 여기 → 퀵 / 병합) 귀찮은 분들을 위해 간단히 코드는 아래의 접힌 글에 써놓았다. 더보기 1) 퀵 정렬 public class QuickSort{ public static void main(String[] args){ int[] arr = new int[100]; for(int i=0; i < arr.length; i++){ arr[i] = (int)(Math.random() * 100); } quickSort(a..
자바 프로그래밍/알고리즘(Algorithm) 2021. 5. 26. 19:34

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

1. 그리디 알고리즘(Greedy Algorithm)이란? 간단히 설명해, 그리디 알고리즘은 "매 선택에서 현재 당장 최적인 답"을 선택해 전체 적합한 결과를 도출하자는 알고리즘 기법이다. 즉, 백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다! 그런데 문제는, 그리디 알고리즘은 전체에서 최적값을 언제나 구할 수는 없다는 것이다. 예를 들면 아래와 같다. 위와 같은 예시에서 우선 A에서 다음 위치로 가는 경우를 찾아야 한다. 그 선택을 할 때는, A, B, C, D의 4개만 보고 선택을 하게 된다. A - E로 가는 3가지 경로가 있을 때, 가장 먼저 A에서 B/C/D 중 최적 경로는 C로 가는 길이다. 그러나 C-E는 150이 걸리기 때..
자바 프로그래밍/알고리즘(Algorithm) 2021. 4. 7. 21:21

알고리즘 - 백트래킹(Backtracking)

1. 백트래킹이란? 백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지(유망하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다. 여기서 알아둘 것은 특정 상태(노드)를 제외한다는 것이다. 백트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사한다. 여기서 더 이상 탐색할 필요가 없는(유망하지 않은) 상태(노드)를 제외하는 것을 가지치기(pruning)라고도 한다. 즉, 이 방법을 통해 우리는 모든 경우의 수를 체크 하지 않고 필요한 것만..
자바 프로그래밍/알고리즘(Algorithm) 2021. 2. 3. 23:36

알고리즘 - 완전탐색(Exhaustive Search)

1. 완전탐색 알고리즘이란? 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다. 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것이다.(최대 10,000번의 시도로 해결 가능) 하지만, Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다. 1. 사용된 알..
자바 프로그래밍/알고리즘(Algorithm) 2021. 1. 19. 15:11

알고리즘 - LIS(가장 긴 증가하는 부분 수열)

1. 개요 LIS는 Longest Increasing Sequence의 약자로 특정 값들이 저장되어 있는 배열 형태에서 순차적으로 증가하는 부분 수열 중 가장 길이가 긴 것을 의미한다. 예를 들어, 현재 아래와 같은 배열이 있다고 가정하자. 인덱스 i 0 1 2 3 4 5 6 7 8 arr[i] 10 20 40 30 1 3 5 2 90 여기서 가장 긴 증가하는 부분 수열, 즉 LIS는 어떤 것이 있을까? 우선 각 숫자가 이전의 수보다 크다면, 그 순서가 가장 큰 경우를 구해보자. 그 배열을 sequence의 약자인 seq라고 해보자. 우선 i = 0 인 arr[0] = 10 일 때, 자기 자신 혼자 있더라도 수열을 만들 수 있으며 혼자서라도 LIS의 일부가 될 수 있으니 1로 시작할 수 있다. arr[1..
자바 프로그래밍/알고리즘(Algorithm) 2021. 1. 10. 22:45

알고리즘 - Dynamic Programming(동적 계획법)

1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다. 2. DP를 쓰는 이유 왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 ..
자바 프로그래밍/알고리즘(Algorithm) 2021. 1. 5. 15:08

알고리즘 - 진법 변환하기(10진수 - N진수)

1. 개요 수학 교육 과정에서 배운 진법 변환을 코드로 구현해보자. 10진법에서 N진법으로, N진법에서 10진법으로 변환하는 방법을 알아본다. 수학에서 변환했던 방법을 생각하며 아래의 진법 변환을 알아보자. 2. 10진법에서 N진법으로 변환하기 10진법에서 N진법으로의 변환은 매우 쉽다. 수학으로 생각하면 10진법으로 표기된 숫자를 N으로 나누어 그 나머지를 표시하고 더 이상 나눌 수 없을 때까지 반복하여 표기하는 방식이다. 예를 들어 10진법 5를 3진법으로 바꾼다면, 5를 3으로 나누면 나머지 2에 몫은 1이다. 최종 나누어진 값부터 표시하므로 12가 된다. 이를 자바 코드로 살펴보자. public class Conversion { public static void main(String[] args)..
자바 프로그래밍/알고리즘(Algorithm) 2020. 12. 29. 17:55