hiha님 문제

수 정렬하기: 버블정렬, 선택정렬과 같은 O(N^2) 정렬로도 시간초과가 나지 않으나, quick sort, merge sort와 같은 O(NlogN) 정렬이 정석 풀이이다. c++ stl 내장함수 sort또한 merge sort를 기반으로 하므로 시간초과가 나지 않는다. 어떤 정렬이든 연습이 가능한 문제.

단어 정렬: 정렬의 기준을 따로 정해야 하는 문제. 열심히 구현해도 좋고, sort함수에 따로 기준을 추가하고 싶으면 sort(v.begin(), v.end(), 기준)으로 한 후, 기준 함수를 따로 설정해주면 된다. 구글링하는 걸 추천.

나무 자르기: 이분탐색의 응용문제. 탐색을 시작할 최소와 최대 범위를 0, 굉장히 큰 어떤 수로 잡아주고, 그 두수의 중간보다 나무가 크면, 그만큼의 길이를 계속 합해줘서 조건에 만족하는지 안하는지 따져주자.

회전하는 큐: 앞으로도 빼고, 뒤로도 빼야 돼서 덱을 이용해야 하는 문제. 현재 원소의 위치는 deque.front()로 해주고, 어디 원소가 더 가까운지가 관건이겠다. 숫자를 부를 때 마다, 이 숫자가 현재 덱의 어디 위치인지 파악을 해줘야되므로, for문으로 돌려 부르는 숫자의 위치를 확인해주고, 위치 비교를 해보자

2sms22rjt님 문제

최대공약수: 잘 생각해보면, 111...11 의 수가 3의 배수가 되든, 7의 배수가 되든 이러한 경우는 결국 1로 이루어진 수가 최대인 약수임을 확인할 수 있다. 시간초과를 겪지 않으려면 log단위의 시간복잡도가 필요할텐데. 1로 이루어진 수가 최대인 약수이면? 답은 너무 간단해지지. 1의 개수와 관련있지 않을까?

거짓말: 진실을 아는 사람, 그리고 그 사람과 함께 있는 사람또한 진실을 알게 된다. 즉, 아예 진실을 아는 사람과 아예 접점이 없는 사람과만 파티를 하는 경우의 수가 답. 유니온 파인드가 생각나지 않는가? 그리고 N, M이 50 이하면 비트마스크로도 할 수 있을 것이다. (다만, 저는 비트마스크는 안썼습니다.) 진실을 아는 경우를 모두 같은 그룹으로 묶어버리고, 진실을 아예 알 수 없는 사람의 수가 파티의 참가자수와 같으면 그 파티에선 구라쳐도 되겠다.

수학은 너무 쉬워: 쉽긴 커녕 이번 과제 중 가장 어려운 문제다. 일단 소수 얘기가 나오니 에라토스테네스 체도 필요할 것이다. 문제가 무슨 소리인지 모르겠기도 하고, 어떤 알고리즘 써야할 지 감도 안올 것이다. 일단 가장 높은 점수라는 게 무엇일까? 모든 수의 최대공약수가 크려면? 잘 생각해보면 이 모든 수의 최대공약수가 최대가 되려면, 최소의 수를 크게 만드는 게 중요하다. 즉, 이 모든 수의 인수들의 곱을 모든 수에 평등하게 나눠주면, 최소가 그나마 덜 작아지지 않겠는가? 예를 들어 8 24 9 는 각각 2*2*2 / 2*2*2*3 / 3*3인데, 이걸 모두 곱하면 2^6 * 3^3 이다. 이걸 모두에게 공평하게 2^2*3으로 하면 모든 수가 12이고, 이 때의 최대공약수가 최대가 될 것이다. 즉, 이 문제는 소인수분해를 하는 것이 관건인 문제인 셈이다~ 소인수분해가 소수의 곱들로 이루어진 것과 관련하여 각 수를 구성하는 소수들을 구해주고 그 수들의 곱을 구해주면 되겠다.