그래프 탐색법 중 하나. 완전탐색이나 백트래킹등 탐색의 횟수, 그래프 경로가 정해져있거나 예측 가능한 경우의 문제에 사용. 1. 선택한 정점에서 해야할 작업 진행. 2. 선택한 정점에서 연결된 정점중 아직 방문하지 않은 정점 방문 3. 더 방문할 정점이 없으면(전부 방문 or 연결 정점 없음.) 이전 정점으로 되돌아감. 4. 1~3 반복. 이전 정점으로 되돌아가는 기능을 위해 Stack을 사용함. -> 재귀함수로도 가능함.

그래프를 탐색하는 방법중 하나. 최단거리, 최소비용등 최솟값을 구하는 문제에 적용할 수 있는 방법. 그래프 정점 사이의 거리가 1일때만 가능. 0. 시작할 정점을 저장함. 1. 저장된 정점에서 첫번째 정점를 선택. 저장에서 제거 2. 제거한 정점에서 할 작업 선택. 3. 제거한 정점과 연결된 정점중 방문하지 않은 모든 정점 저장. 4. 저장한 정점이 모든 노드가 삭제 될때까지 2~3 반복. 저장할 자료구조는 큐로 하는것이 편함.. 앞에서부터 탐색해나가야되기 때문. FIFO 구조면 저장된 정점을 앞에서 부터 하나씩 볼수 있기 때문.

전체의 큰 문제를 서로 다른 작은 문제로 나누어 풀고 합쳐서 전체 문제의 답을 구하는 알고리즘. 동적 계획법과 같아보이지만, 분할 정복은 "문제의 영역이 겹치지 않도록 나눈" 작은 문제로 푼다는 점이다. 1. 문제를 나눈다. 겹치지 않고 빠지는 경우가 없도록 나눈다. 2. 더이상 나눌수 없을때까지 1을 반복. 3. 분할이 끝나면 작은 문제들을 푼다. 4. 푼 문제들을 합쳐간다. 5. 전체 문제가 될때까지 4를 반복. 대표적인 문제 합병 정렬, a^n 구하기. a^n 구하기 1. n이 홀수일때 a^n을 a*a^(n-1) 로 나눈다. 2. n이 짝수일때 a^n을 a^(n/2)*a^(n/2) 로 나눈다. 더 나눌수 없을떄 까지 나누어 놓고 계산해서 점점 합쳐간다.

이미 정렬된 배열 or 리스트에 대해 특정 원소가 포함되어 있는지 판단하는 알고리즘. 전체 범위에서 중심 값을 이용해 판단 기준을 체크함. ex) 오름차순 정렬일때 해당값이 중심값보다 크면 중심값 왼쪽은 무시. 중심값보다 작으면 오른쪽 무시. 범위 줄임. 줄인 범위의 중심값. 다시 조건 검색으로 원소 있으면 true 없으면 false 이미 정렬이 된 배열에 대해서는 O(logN) 정렬이 안된 배열에 대해서는 O(NlongN) 이 필요.

큰 문제를 잘게 나누어 풀어놓고 그 해들을 이용해 큰 문제의 해를 찾는 방법. 1. 최적 부분 구조 : 문제의 답이 잘게 나눈 문제에 대해서도 답이어야함. 2. 부분 문제 반복 : Top - Down or Down - Top 으로 문제를 나누어 내려올 수 있음. 큰 문제와 나눈 문제와의 풀이법이 같아야함. 똑같은 문제를 여러번 푸는 낭비를 막기 위해 "메모이제이션" 기법을 사용. 메모이제이션 : 미리 구해둔 정답을 메모해놓고 만약 다음에 같은 문제를 다시 풀어야 하면 불러와서 쓰는 방법. 대표적 예) 점화식. 등비,등차수열 하향식 방법 : Top - Down 방식으로 큰 문제를 계속 나누어 풀 수 있을 정도까지 나누고 문제를 풀어서 다시 올라가는 방식. 상향식 방법 : Down - Top 방식으로 작은 ..

이미 정렬이 완료된 배열 or 리스트에서 두 개의 인덱스(포인터)를 이용해 포인터에 담긴 값과 원하는 결과를 비교해 원하는 해를 구하는 알고리즘. 이중 반복문으로도 해결가능한 문제이나 O(N^2) 의 시간이 소요. 정렬이 안된 배열에서도 O(NlogN), 정렬된 배열에선 O(N)의 시간으로 단축됨. ex) 배열 내 합이 S가 되는 순서쌍 찾기. 배열의 앞 뒤에서 포인터로 좁혀오며 순서쌍을 찾찾. 투 포인터(앞 : l 뒤 : r)가 지시하는 두 요소의 합을 S 와 비교 l