알고리즘/그 외 알고리즘 (3) 썸네일형 리스트형 백트래킹(Back Tracking) 백트래킹(Backtracking)은 모든 가능한 해를 탐색하는 과정에서, 현재 상태에서 더 이상 해를 찾을 가능성이 없는 경우 되돌아가서 이전 상태로 돌아가는 기법이다. 이 방법은 최적화 문제와 조합적 탐색 문제에서 사용되는 경우가 많다.백트래킹의 기본 개념문제 해결을 위한 상태 공간 트리:백트래킹은 상태 공간 트리를 탐색하면서 해결책을 찾는다. 상태 공간 트리는 가능한 모든 상태(해결책 후보)를 나타내는 트리를 말한다. 백트래킹은 이 트리의 모든 노드를 탐색하여 해를 찾는 방법이다.가능성 없는 해의 가지치기(Pruning):백트래킹의 핵심은 겹치거나 가능성이 없어보이는 경로를 탐색하지 않고 이를 더이상 탐색하지 않는 것다. 이를 가지치기(Pruning)이라고 부른다. 더이상 탐색하지 않아도 되는 경로는.. 누적합(Prefix Sum) 알고리즘 누적합 알고리즘(Prefix Sum Algorithm)은 배열이나 리스트같은 데이터에서 연속된 부분의 합을 빠르게 계산하기 위한 알고리즘이다. 이 알고리즘은 주어진 배열의 각 요소에 대해 이전 요소까지의 누적합을 미리 계산해 두고, 이를 활용하여 특정 구간의 합을 효율적으로 구하는 데 사용된다. 누적합과 관련된 여러 문제가 있지만 먼저 가장 기본적인 누적합의 형태에대해 알아보자.누적합 알고리즘의 기본 개념누적합 배열(Sum Array):주어진 배열 A의 누적합 배열 Sum을 만든다. S[i]는 A 배열의 0번째부터 i번째 요소까지의 합을 뜻한다. 즉, S[i] = A[0] + A[1] + ... + A[i]구간 합 계산:배열 A의 구간 [i, j] (i 시간 복잡도 전처리: 누적합 배열을 생성하는 데 O.. 탐욕 알고리즘(Greedy - 그리디) 1. 탐욕 알고리즘(Greedy - 그리디) 그리디 알고리즘은 매번 항상 최적의 답안을 선택하여 적절한 해를 구해내는 알고리즘입니다. 탐욕 알고리즘은 과정이 직관적이기 때문에 일반적으로 시간 복잡도가 낮고, 구현이 단순하여 빠르게 동작합니다. 이때문에 이해하기 쉽고 구현하기 간단합니다. 하지만 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우가 많습니다.2. 탐욕 알고리즘의 특성(1) 탐욕적인 선택조건(Greedy Choice Property) : 각 단계에서 내리는 최적의 선택이 결국 전체 문제에 대한 최적해로 이어질 수 있어야 합니다. (2) 최적 부분 구조(Optimal property) : 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있어야 합니다. 3. 동전 문제를 통한 탐욕 알고리즘의.. 이전 1 다음
