LUNA's Archive

동적 프로그래밍이란? 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘 문제 풀이 순서 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색(Brute-Force Search) 접근을 시도한다. 근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 것 같다. 이럴 때, 모든 경우를 빠르게 탐색하는 방법으로 동적 프로그래밍 접근을 시도한다. 동적 프로그래밍 접근 순서 풀고 싶은 가짜 문제 정의 가짜 문제를 풀면 진짜 문제를 풀 수 있는가? 초기값은 어떻게 되는가? 점화식 구해내기 진짜 문제 정답 출력하기 예제 피보나치 수열 가짜 문제 정의 D[i] : i 번째 까지 피보나치 수열의 합. 진짜 문제를 풀 수 있는가? ..

Data Structure & Algorithm 2023. 8. 27. 14:43

탐욕 알고리즘이란? 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법니다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법니다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차 : 현재 상태에서의 최적의 해담을 선택한다. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한..

Data Structure & Algorithm 2023. 5. 22. 22:45

백트래킹 알고리즘이란? 백트래킹 알고리즘은 모든 가능한 경로를 탐색하는 데 사용되는 알고리즘입니다. 다만, 이때 모든 가능성을 탐색한다는 것은 그 경로가 해결책으로 이어질 가능성이 있을 때만 해당 경로를 따라가는 것을 의미합니다. 만약 그 경로가 해결책ㅇ로 이어질 가능성이 없다면 그 즉시 해당 경로는 버림(pruning)되며 다른 경로를 탐색합니다. 백트래킹은 주로 결정 문제에서 사용되며, 이러한 문제는 해결책이 존재하는가? 또는 모든 해결책을 찾을 수 있는가?와 같은 질문에 대답하는 데 사용됩니다. 백트래킹 알고리즘의 작동 방식 백트래킹 알고리즘은 깊이 우선 탐색(DFS)와 비슷한 방식으로 작동합니다. DFS와 마찬가지로 백트래킹도 트리 또는 그래프의 모든 경로를 탐색하지만, 백트래킹은 어떤 경로가 해..

Data Structure & Algorithm 2023. 5. 21. 22:00

이번 블로그에서는 이진 탐색(Binary Search)에 대해 알라보도록 하자. 이 이진탐색은 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 출어들기 때문에 탐색 속도가 매우 빠르다. 하지만 이 탐색기법은 정렬된 배열을 전제로 하는 한계점을 가지로 있다. 그러므로, 이진 탐색을 사용할때는 배열이 정렬되 있는 상태거나 배열 정렬 시 발생되는 소요시간이 많지 않은 상황에서 사용하는 것이 좋다. 이진 탐색(Binary Search)의 탐색 과정 이제 한번, 위같은 정렬된 배열에서 이진 탐색(Binary Search) 알고리즘을 적용했을때 어떠한 과정을 거치는지 함께 살펴보도록 합시다. 위의 데이터 집합에서 8이란 데이터를 탐색하도록 하겠습니다. 자, 우선 첫번째 과정으로는 데이터 집합의 중앙 요소를 선택합니..

Data Structure & Algorithm 2021. 1. 31. 21:06

버블 정렬, 삽입 정렬, 선택 정렬은 단순한 알고리즘들이지만 정렬하는데 시간이 많이 든다는 커다란 단점이 있다. 즉 자료가 많을때 이들 정렬 방법들을 부적절하고 보다 빠른 정렬 알고리즘이 필요하다. 이번에는 좀 더 빠른 정렬 방법중 하나인 합병 정렬(merge sort)에 대해 살펴보겠다. 합병 정렬? 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 이 정렬 방법은 분할 정복(divide and conquer) 기법에 바탕을 두고 있는데, 분할 정복 기법이란 하나의 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 방법을 말한다. 분할 정복 기법은 대개 순환 호출..

Data Structure & Algorithm 2019. 8. 25. 01:28

간단한 정렬 알고리즘 중 하나인 삽입 정렬에 대해서 알아보자. 삽입 정렬? 삽입 정렬이란 정렬이 되어있지 않은 부분의 데이터를 뽑아서 정렬된 부분의 적절한 위치에 삽입하는 방법이다. 즉, 배열에서 생각해보면 다음 그림과 같이 배열에서 정렬이 되지 않은 부분의 숫자를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복한다. 삽입 정렬은 추가적인 배열을 사용하지 않고 입력 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 부분의 크기는 하나 커지게 되고, 정렬이 되지 않은 부분의 크기는 하나 줄어들게 된다. 이러한 삽입 연산을 정렬되지 않은 요소..

Data Structure & Algorithm 2019. 8. 23. 19:07

이번 시간에는 가장 이해하기 쉬운 정렬 알고리즘 중 하나인 선택 정렬에 대해 알아보겠다. 선택 정렬 알고리즘은 구현하기 굉장히 단순하지만 정렬시 많은 시간이 걸리는 비효율적인 방법이다. 선택 정렬? 선택 정렬 알고리즘이 어떻게 동작하는지 살펴보자. 먼저 정렬되지 않은 숫자들이 들어 있는 리스트와 정렬이 완료된 숫자들이 들어가는 리스트가 있다고 하자. 아래 그림과 같이 초기 상태에서 정렬된 리스트는 비어 있고 정렬되어야 할 숫자들은 모두 오른쪽 리스트에 들어 있다. 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다. 이것은 오른쪽 리스트가 공백 상태가 될 때까지 되풀이 된다. 위 설명에서는 두 개의 리스트로 나누어 설명했지만 실제로 선택 정렬을 구현하기 위해 ..

Data Structure & Algorithm 2019. 8. 21. 22:29

이번에는 평균적으로 매우 빠른 수행 속도를 보장하는 정렬 방법인 퀵 정렬에 대해 알아보겠다. 퀵 정렬(quick sort)? 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 이 정렬 방법은 분할-정복법(divide and conquer)을 사용하고, 합병 정렬과 달리 리스트를 균등하지 않게 분할한다. 여기서 분할-정복법이란 문제를 작은 문제들로 분리하여 각각 해결하고 결과를 모아서 문제를 해결하는 전략이다. 그리고 분할-정복법은 대게 순환 호출을 이용하여 구현한다. 이제 퀵 정렬이 어떻게 이뤄지는지 살펴보자. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다..

Data Structure & Algorithm 2019. 8. 5. 19:48