복습용 블로그

외계로부터 신호의 부분 수열 중 합이 K인 것이 몇 개인지 찾는 문제입니다. 외계로부터의 신호는 다음과 같이 생성됩니다. A[0]=1983 A[i] = (A[i-1] * 214013 + 2531011) mod 2^32 i번째 입력 신호는 A[i-1] mod 10000 +1 입니다. (ex. 1984, 8791, 4770, 7665, 3188, ....) N: 신호 배열의 길이, K: 합 K> C; while (C--) { cin >> K >> N; cout

이 책의 19장은 스택, 큐 등에 관한 내용입니다. 유명한 자료구조이고 해당 내용 중 스택의 대표 문제인 괄호 문제를 풀어보겠습니다. 문제는 간단합니다. 괄호가 제대로 되어있으면 YES, 틀리면 NO를 출력합니다. 스택을 이용해 여는 괄호면 스택에 넣고, 닫는 괄호면 스택의 맨 위(top)의 여는 괄호와 쌍이 맞는 지 확인하면 됩니다. 맞다면 top을 pop시키고, 틀리면 바로 false를 리턴합니다. 최종적으로 스택이 비어있으면 true, 남아있는게 있으면 false입니다. 코드 #include #include #include using namespace std; bool matched(const string& formula) { const string opening("({["), closing(")}..

n명의 사람이 있고, 첫 번째 사람을 기준으로 k번째 사람이 차례로 죽어나갑니다. 이 때 2명이 되면 2명은 살아남습니다. 조세푸스가 2명 안에 들기 위해 몇 번 째에 있어야 하는지 구하는 문제입니다. (첫번 째 사람 1번, 시계 방향으로 번호 증가) C++의 list를 이용하여 구현하였습니다. list의 iterator를 kill이라 하고 처음에 kill = list.begin( ) 으로 잡습니다. 이후 2명이 남을 때까지 kill의 위치의 노드를 지우고 (erase) 노드를 한 칸씩 당기는 것을 반복합니다. 코드 #include #include #include using namespace std; int C, N, K; void josephus(int n, int k) { listsurvivors; ..

부분 합 : 배열의 각 위치에서 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열 어떤 구간의 평균, 분산 등을 구하기 위해서는 간단히 생각하면 해당하는 위치에 있는 애들을 다 더 해서 처리해야한다. O(N)의 시간이 걸리지만, 이 방법을 여러 번 구현 한다면 전체 복잡도가 증가할 것이다. 이 때, 부분 합을 이용하면 해당 구간의 합을 구하는 데에 O(1)로 해결할 수 있으므로 전체 복잡도를 줄일 수 있다. arr[a]~arr[b] 까지 합 : psum[b] - psum[a-1] c++ : STL에 partial_sum( ) 활용해도 됨 partialSum : 전체 부분합 구하기, rangeSum : 배열의 a~b번째 합 구하기 vector partialSum( vector a){ vector ..

1학년 때 엄청나게 논 태우를 도와주는 문제입니다. 자세한 내용은 책을 참고해주시면 됩니다. 문제 : N개의 과목 중 K개 이상을 수강해야 졸업이 가능하다. 그리고 한 학기마다 열리는 강의의 수는 제한되어있고, 해당 과목을 수강하기 위해서는 선수과목을 들어야한다. 입력 테스트 케이스 C, 전공과목 수 N, 들어야하는 과목 수 K, 학기의 수 M, 한 학기 최대 수강 과목 수 L이 주어진다. 그리고 N개의 줄에 0번 과목부터 선수과목의 목록이 주어진다. 선수과목의 개수와 선수과목 목록을 입력받는다. 예를 들어, 2번 과목의 줄에 3 0 1 3 인 경우 선수과목 3개, 선수과목 목록 : 0,1,3 번 과목 인 것이다. 그 다음으로 해당 학기에 개설되는 과목의 수와 과목 목록을 입력받는다. 예를 들어, 2번 ..