Etc/Algorithm12 이분 탐색(Binary Search) 이분 탐색 BigO: O(log N) 결정 문제의 답이 이분적일 때(Yes or No) 사용할 수 있는 탐색 기법이다. 데이터가 오름차순 정렬된 배열에서 특정 값(N)을 찾아낸다. 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는다. 검색이 반복될 때마다 검색 범위가 반으로 줄어들기 때문에 속도가 빠르다. 예를 들어서 1~50의 숫자가 오름차순 정렬된 카드 더미에서 28번 카드를 찾는다고 가정하자. 첫 번째 카드부터 I번째 카드는 v[i], 28은 val로 정의할 때, 우리가 찾고자 하는 값은 i를 증가시키면서 v[i] >= val가 되는 지점(처음 결정 문제가 True가 되는 지점)의 i 값이다. 이분 탐색의 아이디어는 경계를 포함하는 구간 [start, end]을 잡은 뒤 구간의 길이를 절.. 2023. 1. 25. 분할 정복(Divide & Conquer) 분할 정복 크고 방대한 문제를 쉽게 풀 수 있는 문제 단위로 나누고, 그것들을 다시 합쳐서 문제를 해결하는 방법이다. 일반적으로 재귀 함수를 통해 구현하며, 메모리 제한이 없다면 비교적 빠르게 문제를 해결할 수 있다. 부분 문제가 다른 부분 문제에 영향을 미치지 않는다. (DP의 경우 영향을 미친다.) Divide: 기존 문제를 작은 문제로 나눈다. → 큰 문제를 어떻게 나눌 것이고, 이 과정의 최종 목표는 무엇인가? Base Case: 더 작은 부분의 문제로 나누지 않아도 바로 답을 구할 수 있는 경우 Recursive Case: 같은 형태의 부분 문제로 쪼개야 하는 경우 Conquer: 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행하고, 그렇지 않으면 문제를 해결한다. Combi.. 2023. 1. 25. [그래프 탐색] BFS / DFS 대표적인 문제 유형 1. 경로 탐색(최단 거리, 시간) 2. 네트워크 연결 3. 조합 [Python] 백준 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. cookiee.tistory.com BFS(Breadth-First Search): 너비 우선 탐색 그래프에서 가까운 노드부터 우선적으로 탐색한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조 Queue를 사용한다. 경로가 매우 길 경우에는 탐색 가지가 증가함에 따라 많은.. 2022. 11. 19. [정렬] Comparable과 Comparator 객체를 서로 비교한다 Java에서 정렬을 할 때 흔히 Arrays.sort() 혹은 Collections.sort()을 사용한다. 이는 기본적으로 오름차순 정렬이 되어 있기 때문에 정렬 조건을 정의하기 위해서 인터페이스인 Comparable이나 Comparator를 활용해야 한다. 배열 {1, 3, 2}를 오름차순으로 정렬한다면 먼저 원소 1과 3을 비교한다. 1 - 3의 값은 음수이므로 선행 원소의 값이 더 작다는 것을 의미하고 자리를 바꾸지 않는다. 다음으로 원소 3과 2를 비교하는데, 3 - 2의 값은 양수이므로 후행 원소의 값이 더 작다는 것을 의미하여 자리를 바꾼다. 양수일 경우: 자리를 변경한다. 음수일 경우: 자리를 변경하지 않는다. Arrays.sort(arr, (a, b) -> { ret.. 2022. 10. 18. Algorithm with Math - 순열, 조합 GCD/LCM(최대공약수, 최소공배수) 순열/조합 멱집합 순열(permutation)과 조합(Combination) 순열: 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수. 조합 : 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수. 🎪 카드 뽑기 5장의 카드 중 순서를 고려하고, 혹은 고려하지 않고 3장을 뽑을 때의 경우의 수는? 1. 순열(P ; Permutation) nPɾ = n! / (n - r)! 5 X 4 X 3 = 60가지의 방법 첫 번째 나열하는 카드를 선택하는 방법: 다섯 가지 첫 번째 카드를 나열하고, 두 번째 카드를 선택하는 방법: 네 가지 두 번째 카드를 나열하고, 세 번째 카드를 선택하는 방법: 세 가지 [A, B, D]와 [A, D, B]는 나열하는 순서.. 2022. 7. 30. Implementation - Simulation, Brute-Force, Binary Search 구현 능력을 보는 대표적인 사례 시뮬레이션: 문제가 요구하는 복잡한 구현 요구 사항을 하나로 빠트리지 않고 코드로 옮긴다 완전 탐색: 모든 경우의 수를 전부 확인하여 문제를 해결한다 완전 탐색 알고리즘 Brute-Force Algorithm, 시행착오 방법론 지능형 전략을 사용하지 않고 컴퓨팅 성능에 의존하여 모든 가능성을 시도한다 (최적의 솔루션이 아니다) · 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때 · 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 한계: 문제 복잡도에 민감하다 🌿 순차 검색 for문을 활용해서 인덱스 0부터 마지막 인덱스까지 차례로 검색 🌿 문열 매칭 길이가 N인 전체 문자열이 M 문자열 패턴을 포함하는가? public boolean BruteForceS.. 2022. 7. 28. 이전 1 2 다음
