복습용

문제 별 잡다한 얘기를 다 붙여놨는데, 주어지는 integer sequence중에서 중복 원소를 포함하지 않는 longest subsequence의 최대 길이를 구하라는 문제다. (nlgn)안에 풀 수 있는 문제다. max_length를 갱신해가는 logic으로 풀었는데 일단 코드는 다음과 같다. #include #include using namespace std; /*Given a sequence of integers, find the length of the longest contiguous subsequence containing no repeated elements. */ int main() { int N; cin >> N; while (N--) { int test,max_length=0,leng..

문제 문제는 N이 주어지고 N명의 학생이 듣는 5개의 수업이 주어진다. 이 때 한 명의 학생은 한 가지의 '수업 조합'을 갖게 된다. ex) 100 101 102 103 488을 듣는 학생은 {100,101,102,103,488}의 '수업 조합'을 갖게 된다. (문제에서 수업의 듣는 순서는 중요하지 않다.) 이 때 어떤 하나의 '수업 조합'이 몇 명의 학생에게서 나오는가를 popularity라 정의하자. 예를 들어 문제의 첫 sample input에서 {100,101,102,103,488}의 popularity는 2이다. 이 때 most popular, 즉 popularity가 가장 큰 수업을 듣는 학생의 수를 구하시오. 풀이) 나는 그냥 어떤 수업의 조합별로 그 수업이 나온 빈도를 체크한다음에 최대인 ..

언젠간 풀고만다

문제 문제 이해 자체는 어렵지 않다. 우리가 키보드를 칠 때 Home키 누르면 입력중인 text의 맨 앞으로 cursor가 이동하고 End키를 누르면 입력중인 text의 맨 뒤로 cursor가 가게 되는데, 이를 [와]로 표현한 Text가 있는 것이다. 따라서 문자를 하나하나 읽으면서 [와 ]이 나올때마다 cursor의 위치를 바꿔야 하는데 이것을 하는 데는 list가 제격인 자료구조다. 풀이는 다음과 같다. #include #include #include using namespace std; int main() { string str; while (cin >> str&&!cin.eof()) { list result; list::iterator cursor; cursor = result.begin(); ..

문제 문제는 쉽다. 주어지는 숫자를 2진수로 봤을 때 아래 bit부터 1이 몇개가 나올텐데, 번갈아가면서 a와 b에 추가해가면 된다. 코드는 다음과 같다. #include #include using namespace std; int main() { int n,count,a,b; bitset bits; while (cin >> n) { if (n == 0) break; //terminal condition count = 0; a = 0; b = 0; bits = n; for (int i = 0; i < 32; i++) { if (bits[i] == 1) { if (count % 2 == 0) a += (1

문제 문제는 긴데 그냥 칼렌더 채우라는 거, 내 풀이가 좋은 지는 잘 모르겠음. 굳이 1000000개의 bitset을 써야하나 싶지만 competitive algorithm책에서는 그런 방법의 풀이를 제시하고 있음 #include #include using namespace std; int main() { int n, m,s,e,r; bool conflict; bitset schedules; while (cin >> n >> m) { if (n == 0 && m == 0) break;//terminal case schedules.reset(); conflict = false; for (int i = 0; i > s >> e; for (int j..

-문제 -문제 설명 문제 이해가 조금 힘들수도 있는데, 풀어서 설명해보면 다음과 같은 문제다. 차원 N이 주어지면 N개의 bit로 구성된 (b1,b2,...,bn)와 같은 n-dimensional bit좌표를 생각해볼 수 있다. 이 때 어떤 좌표 하나를 점으로 생각하면, 그 점과 하나의 bit만이 차이나는 다른 점을 이웃하는 점으로 정의한다. 또한, 이 점에 대해 weight가 주어지는데 이것은 입력에서 0,1,2,3,4,5,6...2n-1의 순서대로 주어진다. 즉 처음 주어지는 weight에 해당하는 점은(0,0,0,..,0,0) 다음은 (0,0,...,0,1), 다음은 (0,0,0,..,1,0) 그 다음은 (0,0,0,..,1,1)에 해당하는 weight가 주어지게 된다. 이 때 어떤 점의 poten..

문제 주어지는 string의 사전식으로 다음에 올 순열을 출력하기 ->next_permutation()을 잘 쓰자. 코드 #include #include using namespace std; int main() { string a; while (cin>>a) { if (a == "#") break; if (next_permutation(a.begin(), a.end()))cout