알고리즘 문제 해결을 위한 문제 해결 패턴

문제 해결 패턴

카운터 패턴

• 루프를 적용하여 만든 객체를 사용하고, 중첩되지 않은 두번째 루프를 사용한다. 그러먼 O(n) 시간 복잡도를 유지할 수 있다.

다중 포인터 패턴

• 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간지점에서부터 시작지점, 끝지점, 양쪽 지점을 향해 나아가는 방식.
  • 배열이나 문자열과 같은 선형 구조, 이중연결리스트, 단일 연결리스트를 만든다.
  • 한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다.

기준점 간 이동 배열 패턴(슬라이딩 윈도우 패턴)

• 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다.
  • 규모가 큰 데이터셋에서 데이터의 하위 집합을 추적하는 경우에 사용한다.
  • 한 배열에서 시작점을 하나씩 왼쪽 혹은 오른쪽으로 옮겨가는 경우 O(N)

분할과 정복 패턴

• 배열이나 문자열같은 큰 규모의 데이터셋을 처리. 연결리스트 또는 트리도 포함됨.
  • 시간 복잡도를 엄청나게 감소시킬 수 있다.
  • 값을 찾기 위해 배열의 처음과 끝을 순회하는 것보다는, 배열을 작은 조각으로 세분하여 각 조각들을 어디로 이동시킬 지 결정하는 경우에 유용
  • 퀵/병합 정렬/이진탐색 등은 분할 정복 패턴에 해당함.