오늘 백준에서 문제를 풀다가 vector정렬 시 내가 원하는 순서대로 커스텀해서 정렬하는 compare함수를 만들어서 사용하다가 Runtime Error를 만나서 구글링으로 알아낸 결과를 정리하려고 한다. 결론은 벡터를 정렬하기 위해 sort로 넘겨준 cmp 함수가 잘못돼서 발생한 문제였다. 1. C++ 공식 문서에서 알아보는 Sort C++ STL의 sort함수는 수학적으로 strict weak ordering 조건을 만족해야 한다. 1. cmp(a, a) == false 2. cmp(a, b) == true이면 cmp(b, a) == false. 두 비교체를 바꾸면 참/거짓 값도 변경되어야한다. 3. cmp(a, b) == true이고 cmp(b, c) == true이면 cmp(a, c) == tru..
c++
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다. 문제에 나온 TestCase 3을 예시로 들어 설명하자면 10 4 4177252841 지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. Logic - 0에서부터 왔다가 돌아와서 책을 다시 가져가야 하기 때문에 모든 (경로값 * 2)를 하게된다. 그렇기 때문에 입력을 모든 값중 절댓값이 가장 큰 경로에 있는 책을 제일 마지막에 가져다 놓아서 * 2를 하지 않아야겠다는 생각을 했다. 1, 양수를 저장하는 positive배열과 음수를 저장하는 negative 배열을 받아서 각각 저장하며 절댓값을 통해 절댓값이 가장 큰 값을 저장해놓는다..
https://www.acmicpc.net/problem/1325 > n >> m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i > m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. Logic - Topdown 방식으로 풀이 현재 index에서 갈 수 있는 방향이 한정되어있기 때문에 아래의 좌우 로 한개씩 보내주고 리턴되는 값 중 최댓값을 대입한다. DP table : dp[몇번째 층인지][몇번째 숫자인지] 재귀를 타고 내려가면서 층수를 한개 올려주고 현재 노드의 인덱스와 같은 인덱스 한개 + 1한 인덱스 한개를 재귀로 보내줫다. 2. Code #include using namespace std; int n; int dp[501][501]; ..
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 1. Logic - 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다. 최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘..
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. Logic 1. 주어진 정수 X를 조건대로 검사하며 조건에 맞게 재귀함수에 넣어 계산 한 후 임시 변수 next에 담는다. 2. 다음에 나올 값이 현재의 dp에 담긴 값보다 작아야 연산을 최소로 하기 때문에 해당 next값과 현재 ret 즉 지금의 dp[num]값과 비교를 해서 next값이 더 작다면 dp와 나중에 path를 출력해줄 before 배열을 갱신시켜준다. 2. Code #include using namespace std; int n; const int INF = 987654321; i..
