데이터의 개수가 N이기 때문에 가운데 값을 추출하는데 lgN의 시간으로 해결해야 한다. 우선순위 큐 STL은 top 값만 알 수 있고, 그 뒤의 값은 알 수가 없다. 힙 구조로 되어있기 때문에 최대, 최소값만 알 수 있게 해놓은 것 같다 따라서 가운데 값을 한 번에 알기 위해서는 우선순위 큐 2개를 사용하는 것이다. 하나는 최대 힙, 나머지는 최소 힙으로 구성한다. 크기는 최대 힙의 가장 큰 값 < 최소 힙의 가장 작은 값을 유지하는 구조를 가져야 한다. 짝수개의 데이터가 들어왔을 때는 가운데 값 중 작은 값을 추출해야기 때문에 반드시 최대 힙의 가장 큰 값이 테스트 케이스의 답이 된다. 1) 두 개의 힙 사이즈가 같다면, 최대 힙으로 넣는다 2) 두 개의 힙 사이즈가 다르다면 최소 힙으로 넣는다 두 개..

최소 힙을 구현해서 새로운 데이터가 들어가는 시간복잡도를 lgN으로 처리해야만 한다 문제: https://www.acmicpc.net/problem/1715 깃허브주소: https://github.com/surinoel/boj/blob/master/1715.cpp

휴일이 시작하면서부터 바로 캠핑을 즐기는 것이 최적의 해를 구하는 답이 된다. 나머지 연산을 통해 마지막 남은 연휴에 대해서는 즐길 수 있는 날과 대소비교를 통해 결과값을 구하면 된다 문제: https://www.acmicpc.net/problem/4796 깃허브주소: https://github.com/surinoel/boj/blob/master/4796.cpp

정렬 문제라고 되어있지만, 정렬을 이용하지 않아도 해결할 수 있다. N^2개의 조합을 모두 살펴볼 필요는 없는 것이 조합이라고 생각하고 구한 값에서 *2만 하면 된다. 따라서 1억번 연산을 반으로 줄일 수 있다. 문제: https://www.acmicpc.net/problem/2399 깃허브주소: https://github.com/surinoel/boj/blob/master/2399.cpp 위에는 2중 for문으로 해결해서 시간이 어느정도 걸리지만 좀 더 연구를 하다보면 for문 하나로 해결할 수 있다 [참고] https://aerocode.net/231

탐색을 했을 때 lgN만에 찾기 위해서는 트리를 이용해야 한다. C++ 라이브러리에 있는 map을 이용할 수 있다. M 제한이 10만으로 시간복잡도 M*lgN만에 해결할 수 있다. 보다 쉽게 하기 위해서 map을 2개 만들어서 문자와 숫자가 key일 때를 나눠서 해결했다 문제: https://www.acmicpc.net/problem/1620 깃허브주소: https://github.com/surinoel/boj/blob/master/1620.cpp

위치한 알파벳에 대해서 left, right의 개수를 추가한다. 그리고 대문자, 공백에 대해서 rest라는 변수를 둬서 1씩 더해준다. 탐색이 끝나면 left, right의 차가 최소가 되도록하며, 문제 조건에 있듯이 left가 하나 더 크도록만 예외처리를 해주면 된다 문제: https://www.acmicpc.net/problem/17487 깃허브주소: https://github.com/surinoel/boj/blob/master/17487.cpp