본문 바로가기
반응형

프로그래밍85

이진 탐색(Binary Search) 알고리즘 - C언어, Java, Python 예시코드, UpperBound, LowerBound 이진 탐색(Binary Search)이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾아내는 효율적인 알고리즘입니다. 이진 탐색은 중간값을 반복적으로 비교하며 탐색 범위를 반으로 줄여 나가므로, 데이터의 크기가 클수록 매우 효과적입니다. 1. 이진 탐색의 개념이진 탐색은 다음의 과정을 통해 동작합니다:배열의 중간값을 확인합니다.찾고자 하는 값이 중간값보다 작으면 탐색 범위를 왼쪽 절반으로 좁힙니다.찾고자 하는 값이 중간값보다 크면 탐색 범위를 오른쪽 절반으로 좁힙니다.원하는 값을 찾을 때 까지 위 과정을 반복합니다.이진 탐색은 정렬된 배열에서만 동작한다는 점에 유의해야 합니다. 2. 이진 탐색의 동작 원리초기 배열: [1, 3, 5, 7, 9, 11], 찾고자 하는 값: 7중간.. 2024. 12. 19.
그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 최적의 해를 구하기 위해 각 단계에서 가장 좋다고 생각되는 선택을 하는 알고리즘입니다. 이 방법은 문제를 해결하는 과정에서 부분적으로 최적의 선택을 반복하여 전체적으로 최적의 해답에 도달하려고 합니다.1. 그리디 알고리즘의 개념그리디 알고리즘은 다음 두 가지 속성을 만족하는 경우에만 올바른 결과를 도출할 수 있습니다:1.1 그리디 선택 속성 (Greedy Choice Property)정의: 각 단계에서의 선택이 전체 문제에 대한 최적의 해를 보장해야 합니다.설명: 현재 단계에서 최선이라고 판단되는 선택을 했을 때, 이 선택이 이후의 결정에 영향을 미치지 않고 최적의 결과를 이끌어낼 수 있어야 합니다.예시: 거스름돈 문제에서 가장 큰 단위의 동전을 먼저 선택하는 방식은 최적의 해를 보장합.. 2024. 12. 19.
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도) 2024.12.19 - [알고리즘] - DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나best-coding.tistory.com2024.12.19 - [알고리즘] - BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복.. 2024. 12. 19.
DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나 특정 경로를 찾는 데 유용하며, 다양한 문제 해결에 활용됩니다.1. DFS의 개념DFS는 스택(Stack) 자료구조를 기반으로 하거나 재귀를 사용하여 구현되며, 그래프의 한 경로를 깊게 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 경로로 되돌아갑니다. 이를 "백트래킹(Backtracking)"이라고 합니다.(일반적으로 코딩테스트 문제 풀이 시 재귀로 dfs를 구현합니다.) 2. DFS의 동작 원리시작 정점을 방문하고 스택 또는 재귀 호출을 통해 탐색합니다.현재 정점의 인접 정점 중 방문하지 않은.. 2024. 12. 19.
반응형

티스토리툴바