전체 글

LCS ( Longest Common Subsequence )두 문자열을 입력 받고, 그 중에서 최장 공통 부분 수열을 찾는 문제이다. -원리두 문자열 X(x1, x2, x3...), Y(y1, y2, y3...)가 있을 때 가장 마지막 원소부터 비교해본다.같은 경우, 그 다음 시도부터는 해당 원소를 빼고 생각해도 되므로 각 문자열 크기가 1씩 줄어든다.다른 경우, X의 마지막 원소랑 Y 원소 전체랑 비교하거나 반대로 Y의 마지막 원소랑 X 원소 전체랑 비교하여 각각 문자열의 크기를 줄여나간다. DP는 크기를 줄이는 게 목적이므로 이런 식으로 subproblem을 구상하는 것이다. 위 경우의 수를 점화식으로 표현하면 다음과 같다. -점화식 -DP 과정 (Bottom-up approach)X: GEGG..

11866) 요세푸스 문제 0→https://www.acmicpc.net/problem/11866 #include #include using namespace std;int main() { int N,k; cin >> N >> k; queue q; for(int i=1; i 1) cout ";}★원형으로 앉아있다는 문제여서 처음엔 index = (index+1)%queueSize 위 방식도 처음에는 바로 value = q.pop();으로 작성하였는데, pop은 void 반환이라는 오류가 떴다... 내가 구현할 때는 return으로 해당 원소를 반환하고 지우는 걸로 주로 구현했어서 실제 STL이랑 헷갈린 것 같다..........나중에 STL도 다시 제대로 ..

01. Quick Select Quick Select는 선택 문제(특정 순서 통계값을 찾는 문제)를 해결하는 분할 정복 알고리즘 주어진 배열에서 i번째 작은 값을 찾는 문제를 퀵 정렬(Quick Sort)의 개념을 변형하여 해결함 퀵 정렬처럼 피벗(pivot)을 사용해 배열을 두 부분으로 나누고, 그 중 하나의 부분만을 선택해서 재귀적으로 진행함 Quick Select의 시간 복잡도는 최악의 경우 O(n^2)이지만, 평균적으로는 O(n) 02. Quick Sort Quick Sort는 배열의 요소들을 피벗을 기준으로 나누고, 각 부분을 재귀적으로 정렬하는 분할 정복 기반 정렬 알고리즘 과정: 배열에서 하나의 피벗을 선택 피벗을 기준으로 작은 값들은 왼쪽, 큰..