기록하는 습관 "기습"

투 포인터투 포인터(Two Pointers) 기법은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 알고리즘 설계 방법이다. 이 기법은 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 부분 배열이나 쌍을 찾는 문제를 풀 때 자주 활용된다.투 포인터는 주로 다음과 같은 상황에서 유용하다:- 두 요소의 합이나 곱과 관련된 조건을 만족하는 쌍을 찾는 경우- 특정 조건을 만족하는 부분 배열의 길이, 개수 등을 구하는 경우- 슬라이딩 윈도우와 함께 사용하여 효율적으로 부분합을 계산하는 경우투 포인터의 동작 원리초기화: 두 개의 포인터를 각각 배열의 시작과 끝에 두거나, 특정 조건에 맞게 시작점을 설정한다.조건 검토 및 이동: 조건에 따라 포인터를 이동시킨다..

분할정복분할 정복은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 뒤 결과를 결합하여 원래 문제의 해를 구하는 알고리즘 설계 기법이다.이 방법은 재귀적 접근을 기반으로 하며, 특정 문제를 풀기 위해 문제를 반복적으로 쪼개어 더 단순한 형태로 만들고 이를 조합하여 해를 도출한다. 이 과정은 아래 세 단계로 구성된다:분할(Divide):원래 문제를 더 작은 부분 문제로 분할한다.일반적으로 이 단계는 입력 데이터를 나누거나, 문제의 범위를 축소하는 과정을 포함한다.정복(Conquer):나뉜 부분 문제를 재귀적으로 해결한다.하위 문제의 크기가 충분히 작아지면(예: 크기가 1인 경우), 직접 해결(기저 사례)한다.결합(Combine):각 부분 문제의 결과를 결합하여 원래 문제의 해를 구한다.결합 과..

누적합누적합(Cumulative Sum)은 배열이나 리스트의 특정 구간 합을 빠르게 계산하기 위해 사용하는 알고리즘 기법이다. 일반적으로 대량의 데이터에서 특정 구간의 합을 반복적으로 구해야 하는 경우, 단순히 반복문을 이용해 매번 합을 계산하는 것은 비효율적일 수 있다. 이때, 누적합 배열을 활용하면 원하는 구간의 합을 상수 시간 내에 구할 수 있다. 누적합의 원리누적합의 기본 원리는 배열의 각 위치까지의 값을 순차적으로 더해 새로운 배열을 생성하는 것이다. 이를 통해 배열의 특정 구간 합을 빠르게 계산할 수 있다. 예를 들어, 배열의 i번째 위치까지의 누적합은 원본 배열의 0번째 인덱스부터 i번째 인덱스까지의 합을 저장하는 형태다.누적합 배열을 S라고 할 때, 원본 배열 A에서 구간 [i, j]의 합..

알고리즘이란? 주어진 문제를 해결하기 위해 체계적으로 기술한 것이다. 이를 설계하려면 문제해결을 위해 무엇을 해야 할지 명확히 알아야 한다. 즉, 입력으로부터 출력을 만들어내야 한다. 예를 들어보자. 한 학교에서 n명의 학생이 시험을 봤다. 그중 가장 높은 점수를 받은 학생만 뽑아야 한다. maxScore(x[],n){ x[1, ... , n]을 차례대로 찾는다. return 최대값을 반환한다. } 알고리즘은 배운다는 것은 곧, 생각하는 방법을 배우고 문제해결에 도움이 되는 생각의 빌딩블록을 제공받는 것이다.