전체 글
2661 백준
문제 문제 분석 가장 먼저 생각난 방법은 DP였다. 해당 길이의 모든 경우의 수를 메모리에 저장하고 그 다음 길이에 이전에 저장한 메모리에 1,2,3을 붙여서 새로운 문자열을 만드는 방식을 택하려 했다. 그런데 메모리 초과가 났는데 생각해보면 당연한 결과였다. n = 50이고 대충만 봐도 3^50가지 경우의 수가 존재하기 때문이었다. 처음에는 '모든 길이'가 문제인줄 알고 어차피 이전 길이의 경우의 수만 이용하므로 이전 길이의 좋은 수열만 저장했는데 문제는 이것이 아니였다. 왜냐하면 이전 길이 경우의 수만 저장한다 하더라도 모든 길이 경우의 수를 저장할 때보다 커져봐야 1개의 추가적인 문자열만 더 표현가능하기 때문이었다. (1 + 2 + 4 < 8) 때문에 DP로는 해결할 수 없다고 생각하고 재귀를 이용..
15686 백준
처음 보자마자 든 생각은 bfs를 통한 최소거리 문제인가? 라고 생각했는데 단순히 "치킨집과의 거리" 가 아닌 m개가 남을 때 최소가 되는 치킨집과의 거리를 구해야하는 문제였다. 즉 거리 뿐만 아니라 어떤 치킨집을 남길지도 선택해야 하는가? 가 문제인데 문제의 input을 확인해보자. 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 여기서 치킨집의 갯수는 13보단 작고 M보단 크거나 같다 집의 개수는 2N개를 넘지 않는다 그렇다면 치킨집 중 M개를 선택하고 그것에 따른 최소거리들을 비교하는 문제를 확인해보자. 이 문제를 대충 나누면 두가지로 볼 수 있을 것 같다. 1. 치킨집을 M개로 나누는 파트 걍 dfs이용하면 나눌 수 있을 듯 2. 나눠진 치킨집에서 최소거리를 구하는 파트..
5430 백준
음... 문제 틀리고 다시 풀어서 기분좋은 그런 느낌을 받지 못하는 문제? 였던거같다 뭔가 이거구나~~!!! 가 아니라 응??? 이런느낌이었다. 앞뒤로 뒤집고 복사하거나 삭제하는 복잡도가 대충 O(N)이니까 그건 개오바인거 같고, deque 이용하면 될것 같았다. deque를 이용해서 풀었는데 만약 R이면 is_inverted flag를 true로 하고 차후에 print와 delete를 시행할 때 xxx_back을 이용하고, false라면 xxx_front를 이용해서 문제를 풀면 될것 같았다. 근데 문제는 여기서 error에 관한것이었는데 문제 level이 낮다고 대충 문제를 읽고 풀어서 그랬는지 error의 조건에 대해서 잘못 생각했었다. 예제만 보고 error가 size == 0일때 반드시 출력한다고..
1874 백준
문제가 명확한 만큼 그냥 stack을 이용하여 top과 input이 다르면 다음 순서의 번호를 push하고, 같다면 pop을 하여 풀어서 해결하면 되는 문제였다. 그런데 시간초과가 나서 이상하다고 생각하고 고민해봤었는데 아무리 생각해도 push는 최대 10^5만큼만 발생할 것이고 pop도 같은 수만큼 발생할 것이라고 생각했다. stack에서는 이것들이 O(1)이니까 문제가 일어나는 부분이 절대 아니라고 생각해서 output을 담당하는 string에 의심을 하기 시작했다. 나는 string을 갱신하기 위해서 append를 사용했는데, 이전에 vector에서 insert와 erase와 같은 함수 자체의 복잡도가 상수가 아닌 경우를 의심했고, 찾아보니 역시나였다 append를 push_back과 같이 문자열을..
10989 백준
www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net N의 범위는 10^7, 각 원소의 크기는 10^4 다 넣고 정렬하기에는 중복된 수가 많을 뿐 더러 N의 크기가 크기 때문에 NlogN의 복잡도를 가지는 sort, map등을 사용할 수 없다. 다행히 범위가 적기 때문에 하나의 길이를 그냥 메모리에 저장하고 갯수의 크기를 저장하면 된다. 이걸 카운팅 정렬이라고 부른다 카더라 정렬? 이라고 부르기엔 음,,,
1920 백준
A안에서 X의 존재 여부를 출력하는 문제 N과 M의 크기는 10^5, 모든 정수 범위는 int형 그냥 하나하나씩 찾으면 10^10이니까 N의 input에 대해 정렬하고 각 M의 원소에 대하여 binary search하면 될 것같다. 13분, 좀 더 줄이자. 굳이 binary search구현 할 필요 없이 1. lower_bound를 이용하여 가장 근접한 작은 값의 인덱스를 찾고 값비교 하면 더 빠르고 쉽다. algorithm에 정의된 lower_bound를 보면 Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val. 이미 정렬된 곳에서 comp보다 작지 않은..