일반적으로 배열에서 2개의 인덱스(포인터)를 움직이면서 문제를 해결하는 방법보통 왼쪽(left), 오른쪽(right) 혹은 시작(start), 종료(end) 쌍으로 포인터를 표현한다.외워야 할 알고리즘이라기 보다는 이렇게도 문제를 풀 수 있구나 정도로 알아두면 된다.2개의 포인터를 동시에 +1씩 움직이면서 답을 구하는 알고리즘은 [슬라이딩 윈도우] 라고 부르기도 한다.  Referencehttps://www.acmicpc.net/problem/2559https://school.programmers.co.kr/learn/courses/30/lessons/42885https://school.programmers.co.kr/learn/courses/30/lessons/67258

DP (Dynamic Programming : 동적 계획법)N-a번째 답(값)을 이용하여 N번째 답을 구하는 알고리즘Memoization 한 번 구한 값을 배열 등에 저장(메모)해두고, 다음에 같은 값이 필요하면 메모해 둔 값을 사용하는 것으로 시간적 효율성을 증가시킨다.일반적으로 N번째 답(값)을 구하기 위해 기존에 구해둔 N-a번째 답(값)을 사용하므로, 초기값은 직접 구해서 세팅하는 경우가 많다.주로 For문과 DP값을 저장하는 배열로 구현하며 재귀함수로 구현하기도 한다.📌 DP 접근 방법N-1번째 혹은 N-2번째 답(값)을 이용하여 N번째 답(값)을 구할 수 있을까 고민해본다.경우의 수 구하는 문제가 DP문제인 경우가 상당히 많다.일종의 점화식을 이용해서, 초기값 1번째 혹은 2번째 값까지는 직..

Backtracking백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.가장 중요한 점은 제한 조건을 위배한다면 그 노드를 제외한다는 점이다,.현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다.DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요 없는 부분을 쳐내는 행위를 백트래킹(가지치기)이라고 생각하면 된다.DFS와 Backtracking의 다른점DFS..

⭐️ DFS (Depth First Search)정해진 규칙에 의해 시작 정점에서 멀어지는 방향 우선으로 탐색하는 방법일반적으로 재귀함수를 사용해서 구현한다. (Stack으로도 구현 가능하지만, 구현이 상당히 복잡해진다.)그래프가 트리 형태일 때, DFS 알고리즘이 자주 쓰인다.최단거리를 구하기에는 적합한 알고리즘이 아니다. (시간 초과 주의)재귀로 구현된다는 점에서 Backtracking 과 유사하다.📝 DFS (Depth First Search) 탐색 구현 방법방문 체크 용 (재방문 방지) 배열을 만든다.현재 정점을 파라미터로 넘겨 받는 함수(메소드)를 정의한다.함수(메소드) 내부에서..현재 정점이 이미 방문한 정점이면 return 한다.현재 정점의 방문 체크를 한다.해당 정점에서 방문 가능한 다음..