C++의 sort, stable_sort, set, map는 비교 함수를 설정할 수 있다. 정렬 기준을 설정하는 것이다.참고로 stable_sort는 동일한 값을 가진 원소들의 상대적 순서(삽입 순서)가 정렬 후에도 보존되는 정렬 알고리즘이다. C++에서 비교 함수가 true를 반환하면  첫 번째 인자가 더 앞에 오게 한다. 즉, comp(a, b)가 true를 반환하면 a가 앞에 오는 것이다. 따라서 a>b를 비교 함수로 설정하면 a가 더 클 때 true이고 더 큰게 앞으로 오므로 내림차순 정렬이 된다. 이 비교 함수는 람다 표현식으로 익명 함수를 생성해 편리하게 설정할 수 있다. 람다 표현식의 기본 문법은 다음과 같다.[캡처](매개변수) -> 반환타입 { 함수 본문 } 캡처 클로저 [ ]: 외부 변수..

https://www.acmicpc.net/problem/2473전에 풀었던 두 용액을 섞어서 0과 가장 가까이 만드는 문제와 세 수를 합해서 딱 0을 만드는 문제를 합친 버전이다. 우선 0과 가장 가까이 만들어야하고, 세 수를 합한다는 점에서 (i, j)의 합을 먼저 구하고 그 합과 어떤 숫자 idx를 합해서 0과 가장 가까이 만드는 idx를 찾는 방식으로 접근했다. 문제는 두 용액이 아닌 세 용액이라는 점이다. 기존 두 용액에서는 lower_bound(~~, ~~, -i) = idx 라 했을 때 idx - 1, idx를 보면 된다. 다만 idx가 i와 겹치는 경우를 고려해서 idx + 1까지 봤던 것이었다.이번에는 용액이 세 가지이므로 idx는 idx + 1을 똑같이 보고, [i, j] 와 같은 경우..

https://www.acmicpc.net/problem/2467https://www.acmicpc.net/problem/3151용액을 먼저 풀어보고 합이 0을 풀어보는 것을 추천한다. 백준 2467: 용액용액은 간단하게 합이 0과 가장 가까운 index를 찾으면 된다.arr [i]를 기준으로 찾으면 될 것 같은데 결론부터 말하자면 arr [i]와 합이 0과 가장 가까워지는 index를 찾으려면 -arr [i]를 lower_bound() 함수에 적용하면 된다. lower_bound(~~, ~~, -arr [i])의 결과는 -arr [i] 이상인 값이 될 테고 그 값을 arr [k]라 하자.arr [k]는 -arr [i]가 될 수도 있고 그 값보다 클 수도 있다. 또, arr [k-1]은 -arr [i] ..

https://www.acmicpc.net/problem/5904N이 10^9 개로 N번째 글자를 구한다는 것이 몇 번째 수열을 구해야 하는지 감도 안잡히고 굉장히 큰 수여서 long long으로도 담지 못한다.즉, 재귀적으로 길이가 n 이상인 수열을 구해서 n번째 문자를  찾으려 한다면 절대 풀 수 없다.조금 다르게 생각해서 n번째 글자만 알면 되므로 어떤 수열에 대해 n번째 글자를 알아내는 과정을 재귀로 생각하여야 한다. 사실 다 풀고 나서야 이렇게 명료하게 말할 수 있지만 풀 때는 다음과 같은 과정을 거쳤다.수열의 길이가 n 이상인 moo 수열 구하기 -> 구현을 다 하고 보니 n이 얼마 이상 커지면 오류k번째 moo 수열 S(k)에 대해 S(k-1)의 길이를 알면 S(k)를 알 수 있음. 그럼 길..

https://www.acmicpc.net/problem/1647예제7 121 2 31 3 23 2 12 5 23 4 47 3 65 1 51 6 26 4 16 5 34 5 36 7 4ans : 8문제의 요구사항은 다음과 같다.도시를 2개로 분할하라.분할된 2개의 도시 사이에는 간선이 존재하지 않는다.각 도시의 마을은 MST로 구성되어 있다.일단 3번 조건을 보면 MST를 구현해야하긴 하는데 어떻게 2개로 분할해야 가장 Minimum한 MST를 만들 수 있을지가 고민된다.N이 100개정도면 완전탐색으로 구현해도 될테지만 N은 10만... 완전탐색은 아니다. 만약 도시 분할 조건이 없다면 바로 MST를 구해도 된다. 그렇다면 MST를 구하는 과정에 Union-Find를 하게 되고 이 부분을 응용해서 2개의 ..

예제454430 2 2 22 0 3 32 3 0 42 3 4 0출력 : 9MST 문제인데 MST 문제는 구현도 어렵지만 왜 MST인지 잘 판단해야 한다. 논을 파는 방법은 직접 논에 우물을 파거나 다른 논에서 끌어오는 방법이 있다.당장 떠오르는 방법은 그리디 하게 가장 싼 우물을 파되, 불필요하게 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야 한다. 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야한다는 점에서 MST를 떠올렸고 프림 알고리즘을 선택했다. 알고리즘은 다음과 같다.우물을 파는 비용을 모두 우선순위 큐에 넣는다.우선순위 큐에서 논을 하나 빼서 MST에 포함시킨다.MST에 포함된 논의 간선 중 MST가 아닌 논과 연결된 간선을 우선순위 큐에 넣는다.N개의 논에 대해 N-1개의 간선이 MST..