본문 바로가기

CS18

투 포인터 two pointer 투 포인터리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하며 처리하는 알고리즘이다.리스트에 담긴 데이터에 순차적으로 접근해야할 때, 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 예를 들어, 1-30번까지의 학생 중 2, 7을 명시하여 2번부터 7번까지의 학생을 지칭할 수 있다.   특징끝 점이 항상 시작점 보다 앞서야 한다.시작점이 모든 리스트를 돌았을 때 종료해야 한다.  대표적 예시로 두가지로 사용하는 걸 알아보자 리스트에서 부분 합 구하기리스트에서 start ~ end 사이의 값들의 부분합을 구하는 방법이다. 리스트 맨 처음 인덱스를 start, end로 둔다.부분합 값이 구하고자 하는 값보다 작을 때, end를 +1 하여 부분합 값을 늘린다.부분합 값이 구하.. 2024. 8. 23.
분할 정복 Divide and Conquer 문제를 나눌 수 없을 때까지 작은 문제로 나눈 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘이다.Top-Down 접근법을 사용하여 아래로 내려가며 하위의 답을 구한 후, 이를 병합하여 상위의 답을 구한다.분할된 작은 문제는 상위의 문제와 같은 형식을 가지며, 분할된 작은 문제를 재귀적으로 해결하고 이를 결합하여 원래 문제를 해결한다. DP와 차이점DP는 부분 문제가 서로 중복되어서, 한 부분 문제를 해결해야 다음의 상위 부분 문제를 해결할 수 있다. 때문에 중복된 문제를 여러번 푸는 것을 피하기 위해 Memoziation이나 테이블을 이용하여 계산된 결과를 저장한다. 반면, 분할 정복에서 부분 문제는 서로 중복되지 않는다. 따라서 각각의 부분 문제들을 독립적으로 해결한다.  분할 .. 2024. 7. 17.
동적 계획법 Dynamic Programming 다이나믹 프로그래밍은 기본적인 아이디어를 이용해서  하나의 큰 문제를 여러 개의 작은 문제로 나누어, 그 결과를 저장해서 다시 큰 문제를 해결할 ㄸ 사용하는 것이다. 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법이다.간단히, 큰 문제를 작은 문제로 쪼갠 다음 각각의 답을 저장해가며 다시 활용하는 방법이다.  피보나치 수열을 통해 다이나믹 프로그래밍을 더 알아보자.피보나치 수열을 구하는 함수 f(n)를 통해, f(6)를 구한다고 해보자.f(6)를 구하기 위해 f(5)와 f(4)을, f(5)와 f(4)을 구하기 위해 f(4)와 f(3)... 를 구해야 하므로, f(x)를 다음과 같은 점화식으로 표현할 수 있다.𝐹0=0, 𝐹1=1, 𝐹𝑛+2=𝐹𝑛+1+𝐹𝑛 이러한 피보나치.. 2024. 6. 19.
이진 탐색 Binary Search 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인 순차 탐색과 달리,탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.시작점과 끝점 인덱스를 확인한 다음 둘 사이의 중간점을 정한다. (중간점이 실수 일 때 소수점 이하를 버린다.)찾으려는 데이터와 중간점 데이터를 비교하여, 탐색할 범위의 끝점 또는 시작점을 변경한다.1,2를 반복한다.중간점의 데이터와 찾으려는 데이터가 동일할 때 탐색을 종료한다.한번 확인(중간점과 비교)할 때마다 확인할 원소의 개수가 절반씩 줄어든다.시간 복잡도 : O(logN) array = [0, 2, 8, 9, 1, 3, 4, 7, 5, 6]target = 5array.sor.. 2024. 6. 13.

티스토리툴바