알고리즘6 분할정복(Divide and Conquer Algorithm)에 대하여 분할 정복이란?그냥 있는 그대로 받아들이면 분할해서 정복한다,큰 문제를 작은 문제로 나누어서 해결하는 알고리즘 입니다. 여기까지 들으면 우리가 알고있는 다른 알고리즘이 하나 떠오릅니다.바로 DP (동적 계획법) 입니다.하지만 조금 다른 점이 있는데 어디에 적용하는지(목적), 어떤 곳에 쓰는지(대상)이 다릅니다. 동적 계획법 : 작은 문제를 풀면서 그 결과를 저장해 나아가 전체 문제를 해결합니다.ex) 최적화, 최단경로분할 정복 : 큰 문제를 작은 문제로 나누어서 해결합니다.ex) 아주 큰 수의 곱셈, 퀵 정렬(Quick Sort) 분할 정복의 적용 단계분할(Divide) : 문제를 작은 부분의 문제로 나눕니다.정복(Conquer) : 작은 부분으로 나눈 문제를 해결합니다.결합(Combine) : 작은 부.. 2024. 7. 15. 우선순위 큐(PriorityQueue)에 대하여 우선순위 큐(PriorityQueue) 란?일반적으로 큐는 선입선출구조인 FIFO형식의 자료구조이다.반면에 우선순위 큐는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다. 우선순위 큐는 보통 힙의 자료구조를 통해서 구현하기 때문에 힙에 대해 알고계시는 것이 좋습니다.힙에 대한 정리글 : https://dodledd.tistory.com/105 힙과 힙 정렬 알고리즘힙이란?힙은 완전 이진 트리(Complete Binary Tree)의 일종으로,부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있다.마지막 레벨에 있는 노드를 제외한 모든 레벨 노드가 완전히 채워져 있는 트리dodledd.tistory.com 우선순위 큐 사용 법자바에서는 우선순위 큐를 Queue인터페이스에서 상속받아 .. 2024. 7. 12. 이분 탐색이란(Binary Search)? 이분 탐색은 이진 탐색, Binary Search라고도 하며 모든 경우의 수를 도는 순차적 탐색보다더 빠른 탐색을 위해 나온 방법이다.순차적 탐색말 그대로 순차적으로 건너뛰는 일 없이 0부터 탐색하는 것이다. 이분 탐색이분 탐색에서 중요한 것은 정렬이 되어있어야 한다.정렬되어 있지 않으면 탐색이 불가능하기 때문에 필수 조건이다. mid = (left + right) / 2만약 크다면 left = mid + 1만약 작다면 right = mid -1찾으려는 특정 원소와 시작점, 끝점을 찾아 중간 점을 구한다.찾으려는 원소의 값이 중간 점보다 작다면 시작점은 유지, 끝점은 중간점에서 -1 하여 바꿔주고 중간점을 구한다.만약 크다면 반대로 시작점을 중간점 +1로 변경, 끝점 유지하여 중간 점을 다시 구해준다.찾.. 2024. 7. 8. 힙과 힙 정렬 알고리즘 힙이란?힙은 완전 이진 트리(Complete Binary Tree)의 일종으로,부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있다.마지막 레벨에 있는 노드를 제외한 모든 레벨 노드가 완전히 채워져 있는 트리 구조이다.단어 설명 !부모노드(Parent Node) : 특정 노드의 상위에 위치한 노드자식노드(Child Node) : 특정 노드의 하위에 위치한 노드루트노드(Root Node) : 트리구조에서 가장 상위에 위치한 노드리프노드(Leaf Node) : 트리구조에서 가장 하위에 위치하며 자식 노드가 없는 노드레벨(Level) : 루트노드부터 시작하여 트리에서 밑으로 몇 번째 층에 있는지를 나타낸다.(보통 루트노드의 레벨은 0이다)높이(Height) : 레벨과는 반대로 제일 낮은 리프노드에서부터 시.. 2024. 7. 4. 그리디 알고리즘에 대하여(Greedy Algorithm) 그리디 알고리즘이란?최적의 값을 구하는 알고리즘중 하나로써 각 단계에서 문제에 대한 가장 좋은 선택지를 선택해나가는 것을 반복하여 우리가 원하는 최종 해에 대한 근사한 값을 가지는게 목표이다.(보통 문제를 단계별로 나누어 가장 좋은 선택지를 고르고 이후에 가장 좋은 선택지를 모두 더 해서 전체적인 해를 도출해내는 것이다.) 밑에 그림이 가장 간단하게 보여주는 것 같은데 문제는 더했을 때 가장 큰 수를 찾아라우선 첫 번째 그림은 그냥 아무 선택지나 골라서 간 것이다. 두 번째 그림은 각 각의 선택지에서 가장 큰 수를 찾아서 더하는 것이다.(정답은 아닐 수도 있지만 정답에 근사값을 구할 수 있다) 그럼 그리디 알고리즘을 적용할 수 있는 조건을 보자1. 탐욕 선택 속성 (Greedy Choice Proper.. 2024. 7. 2. [알고리즘] 이진 탐색 오늘은 이진 탐색 알고리즘에 대해 공부해보았다. 이진 탐색 알고리즘이란? 간단하게 말해서 리스트의 크기가 커질수록 순차탐색보다 빠르게 검색할 수 있는 알고리즘이다. 다만 2진 탐색을 하기위해서는 값에 대해 정렬이 필수이다. 그럼 간단하게 설명해보겠다. 이진 탐색은 정렬한 배열에서 특정한 값을 찾고자 할 때 배열의 중간에 있는 임의의 값을 선택하여 우리가 특정한 값과 비교하고 특정한 값이 임의의 값보다 작으면 그것을 기준으로 좌측의 데이터들을 대상으로, 그 반대로는 우측을 대상으로 탐색을 반복하며 특정한 값을 찾는 것이다. 말로 풀어내면 어렵다. 실제 배열이 있다고 가정하고 구해보자. {1, 5, 27, 46, 66, 82, 98, 100} 이러한 배열에서 특정한 값 46을 찾아보겠다. 1. 우선 가장 먼.. 2024. 2. 12. 이전 1 다음
