이 문제는 외계 생물에게 번호를 매긴다고 되어있지만 결국 full binary tree에 부모의 번호를 자식의 번호보다 작게 매기는 경우의 수를 구하는 문제이다.
모든 경우를 다 해봐야 하는... dp같다. 하지만 dp로 어떻게 접근해야할 지 쉽게 떠오르지 않는다. 모든 경우를 다 해본다....
음 d[r][num] : root를 (서브)트리의 루트 노드인 노드 r에 번호 num을 매겼을 때, 번호를 매기는 경우의 수... 로 해도 문제가 좀 있다.
부모의 번호보다 자식의 번호가 커야 하는데, 이게 루트 노드부터 시작해서 그 자식들에게 번호를 매기는 식으로 내려가면 왼쪽 서브트리에서 어떻게 하냐에 따라 오른쪽 서브트리에 영향을 미친다. 즉, 왼쪽 서브트리에서 어떤 번호를 썼는지 알아야 오른쪽 서브트리에 배치할 수 있는 경우의 수를 구할 수 있다... 번호는 최대 2048-1 = 2047까지 있는데... 상태 dp를 할 수도 없고...어렵다.
일단 오늘은 접고 다음에 좀 더 고민하다가 풀이를 봐야겠다. 이 문제처럼 전혀 감이 안 오는 문제는 너무 오래 고민하지 말자. 대신 풀이를 보면 확실하게 내 것으로 만들고 정리하자.
2016년 11월 29일 화요일
BOJ 13911 집 구하기
이 문제는 고민 좀 했는데... 알고보니 내가 예전에 풀었던 유형이었다.
SCPC 예선에도 나왔었고, JM book에 나와있는 유명한(?) 문제 유형이다.
문제를 잘 읽어보면 결국은 맥날과 스벅 사이의 최단 거리를 구하는 문제로 볼 수 있는데, 맥날이랑 스벅의 수도 여러 개이고 정점의 수도 10000개라 다익스트라를 여러번 돌려서는 시간 초과가 날 것이다.
하지만 그래프를 조금만 변형 해보면 맥날과 스벅사이의 최단 거리를 다익스트라 한 번으로 구할 방법이 있다. 바로 새로운 출발점을 하나 만들고 거기에 가중치 0의 간선으로 모든 맥날(또는 모든 스벅)과 연결하는 것이다. 그리고 그 출발점에서 출발하여 각 정점까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하면 각 맥도날드에서 각 스벅까지의 거리 중 최단 거리를 찾을 수 있다. 참 처음에 이 방법을 JM book에서 봤을 때, 정말 기가막히다고 생각했는데 지금 다시 봐도 멋진 방법이다.
그런데 이 문제는 조금 더 생각해야 할 것이 있다.
바로 맥날과 스벅사이의 경로에 맥날과 스벅이 아닌 일반 집 하나가 꼭 있어야 한다. 예를 들어 맥날 - 스벅 이렇게 최단 거리일 경우 답이 될 수 없다.
음 맥날과 스벅이 정점 번호로 여러 개 주어지는데, 이걸 다 일일이 비교해서 집인지 아닌지 판별해야 하나? 그럼 너무 오래 걸릴텐데...
다익스트라 알고리즘을 생각해보면 일단 시작하자마자 각 맥날까지의 최단 거리는 0이다. 그렇기 때문에 다른 맥날에서 맥날을 거쳐갈 일이 없다.(그 맥날까지의 거리가 더 짧은 거리로 갱신돼야 하는데 이미 0이므로 갱신될리가 없다.) 즉, 맥날에서 어떤 정점까지의 경로는 출발점 바로 다음의 맥날 하나 뿐이다. 그 외의 맥날은 없다.
그렇다면 스벅은 어떨까? 맥날부터 어떤 스벅까지의 경로에는 분명 다른 스벅이 있을 수 있다. 하지만 다른 스벅을 거쳐 도착한 스벅까지의 경로는 절대 맥날-스벅 간의 최단 거리가 될 수 없다. 왜냐하면 이미 그 전에 거친 스벅 바로 거기까지의 거리가 더 짧을 것이기 때문이다.
즉, 맥날부터 스벅까지의 최단 거리를 구하되, 맥날부터 스벅까지 몇 개의 길을 거쳐갔는지 기록해서 .... 가 아니라.. 안된다. 몇 개의 길을 거쳤는지 기록해서 원래 2개 이상 거친 것 중에서 최단 거리를 찾으려 했지만 그럴 경우 중간에 스벅이 끼어있고 일반 집은 없을 수도 있다. 이런 경우를 커버할 수 없다.
꽝이다! 잘못 생각했다.
그리고 다시 생각해보니 이 문제는 무작정 맥날과 스벅사이의 최단 거리를 구하는 문제는 아닌 것 같다. 왜냐하면 어떤 집이 꼭 맥날과 스벅 사이에 있어야 할까? 아니다
맥날 - 집 - 스벅 이 아닌 맥날 - 스벅 - 집 일 수도 있다!!! 왜냐하면 문제에서 구하라는 것은 집의 맥도날드까지의 최단거리와 스타벅스까지의 최단거리 합이므로...
그렇다면 어떻게 해야할까?
생각해봤다.
다익스트라를 두 번 돌린다. 처음에는 새로운 출발점을 맥날들에 연결하고 시작해서 일단 일반 집까지의 최단 거리를 다 구하고, 또하나의 새로운 출발점을 일반 집들에 연결하되 간선의 가중치는 앞서 구한 맥날에서 각 집까지의 최단 거리로 놓는다. 그리고 dist배열을 다익스트라 처음 시작할 때 처럼 다 초기화한 후 그 출발점에서 시작해서 최단 거리를 구해서 스벅까지의 최단 거리를 보면 결국 맥날 - 집 - 스벅까지의 최단거리를 알 수 있게 될 것이다.
위와 같이 하면 첫 다익스트라에서 각 집에서 맥날까지의 최단 거리를 구했을 것이고 두번째 다익스트라에서 각 집에서 스벅까지... 아!!!
이것도 맞지만 그냥 각 집에서 처음부터 시작하면 되는 거 아닌가? 그럼 다익스트라를 한 번만 돌리면 될 것이다. 각 집에 새로운 출발점을 간선 가중치 0으로 연결하고 각 집에서 출발한다. (아니면 각 집들을 거리 0으로 바로 큐에 다 넣고 시작해도 똑같다.)
그렇게 다익스트라를 돌리면 집에서 맥날까지의 최단거리, 집에서 스벅까지의 최단거리가 구해져 있을텐데... 음 아 이럴경우는 어떤 집에서 출발했는지 알 필요가 있으므로 같은 집에서 출발한 최단거리끼리 합치고 그 중 최소값을 구하면 될 것이다. 다익스트라를 한 번만 돌리는 대신 출발점이 어딘지를 기록해야 하고 비교해서 같은 것 끼리 더하고 그 중 최소값을 찾는 과정이 필요하다.
두 방법 모두 다 해봐야겠다. 아 그리고 맥세권, 스세권 모두 되는지 확인하는 것도 필요하다!
집에서 출발하는 것으로 구현중인데, 같은 집에서 출발한 것을 찾는게 O(N제곱)짜리 밖에 떠오르지가 않는다... 처음에 생각한 방법처럼 맥날들 부터 시작해서 다익스트라를 2번 돌려야겠다.
아 근데... 또 하나의 문제에 직면했다. 바로 맥세권 스세권을 따져주는 것인데, 각각 멕세권인지 스세권인지 따져야 하므로 좀 까다롭다...
일단 처음에 맥날에서 집까지의 거리는 맥세권 제한 x이하인 경우만 보는 걸로 처리하면 되는데, 각 집에서 (맥날에서의 최단 거리를 가지고) 출발해서 스벅까지의 최단거리를 구하는 과정에서가 문제다. 이 것을 해결하기 위해 아까 했던 것 처럼 출발점이 어딘지를 기록해서 최단거리를 다 구한 후 답을 구할 때, 스벅까지 최단거리-(출발점까지의 거리)의 값이 스세권 제한 y이하인지 판별해야 할 것 같다.
일단 그렇게 해서 AC를 받았다....
이 문제... 쉬운 줄 알았는데 그렇지 않았다.
그리고 생각해보니 집에서 출발해서 각 최단 거리를 구하고 출발지가 같은 것을 합하는 방식은 반례가 있다. 안된다...
예를 들어 맥날까지의 최단 거리는 집1에서 부터의 거리이고, 스벅까지의 최단 거리는 집2에서부터의 거리이고 답은 맥날 - 집1 - 집2 - 스벅 인 경우를 처리할 수 없다...
하지만 내가 맥날에서 집까지의 최단 거리를 구하고 그 값들을 가지고 각 집들에서 스벅까지의 최단 거리를 구하는 것은 잘 생각해보면, 집을 경유하는 (맥날에서 스벅까지의) 최단 경로를 구하는 것과 같기 때문에 가능한 것 같다.
좀 헷갈리기도 하고, 정말 좋은 문제였다.
그리고.. 다른 분들의 풀이를 보고 있는데.... 헉... 더 좋은 방법이 있었다.
맥날에서 각 집까지의 (맥세권인)최단 거리를 구하고, 스벅에서 각 집까지의 (스세권인)최단 거리를 구한 후 각 집을 기준으로 두 최단 거리를 합쳐서 그 중 최소값을 구하면 된다...
와... 이거 어디서 본 것 같은데.. 익숙한 방법인데 난 전혀 생각도 못하고 괜히 어렵게 생각하고 있었다. 이렇게 하면 또 좋은 것이 맥세권인지 스세권인지 판단하기 편하다 그냥 다익스트라 함수 내부에서 바로 각 집까지의 거리가 맥세권이나 스세권인 경우만 처리하면 된다.
그리고 훨씬 이해하기도 좋은 방법같다. 문제를 많이 풀어보고 공부도 많이 해야한다...
SCPC 예선에도 나왔었고, JM book에 나와있는 유명한(?) 문제 유형이다.
문제를 잘 읽어보면 결국은 맥날과 스벅 사이의 최단 거리를 구하는 문제로 볼 수 있는데, 맥날이랑 스벅의 수도 여러 개이고 정점의 수도 10000개라 다익스트라를 여러번 돌려서는 시간 초과가 날 것이다.
하지만 그래프를 조금만 변형 해보면 맥날과 스벅사이의 최단 거리를 다익스트라 한 번으로 구할 방법이 있다. 바로 새로운 출발점을 하나 만들고 거기에 가중치 0의 간선으로 모든 맥날(또는 모든 스벅)과 연결하는 것이다. 그리고 그 출발점에서 출발하여 각 정점까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하면 각 맥도날드에서 각 스벅까지의 거리 중 최단 거리를 찾을 수 있다. 참 처음에 이 방법을 JM book에서 봤을 때, 정말 기가막히다고 생각했는데 지금 다시 봐도 멋진 방법이다.
그런데 이 문제는 조금 더 생각해야 할 것이 있다.
바로 맥날과 스벅사이의 경로에 맥날과 스벅이 아닌 일반 집 하나가 꼭 있어야 한다. 예를 들어 맥날 - 스벅 이렇게 최단 거리일 경우 답이 될 수 없다.
음 맥날과 스벅이 정점 번호로 여러 개 주어지는데, 이걸 다 일일이 비교해서 집인지 아닌지 판별해야 하나? 그럼 너무 오래 걸릴텐데...
다익스트라 알고리즘을 생각해보면 일단 시작하자마자 각 맥날까지의 최단 거리는 0이다. 그렇기 때문에 다른 맥날에서 맥날을 거쳐갈 일이 없다.(그 맥날까지의 거리가 더 짧은 거리로 갱신돼야 하는데 이미 0이므로 갱신될리가 없다.) 즉, 맥날에서 어떤 정점까지의 경로는 출발점 바로 다음의 맥날 하나 뿐이다. 그 외의 맥날은 없다.
그렇다면 스벅은 어떨까? 맥날부터 어떤 스벅까지의 경로에는 분명 다른 스벅이 있을 수 있다. 하지만 다른 스벅을 거쳐 도착한 스벅까지의 경로는 절대 맥날-스벅 간의 최단 거리가 될 수 없다. 왜냐하면 이미 그 전에 거친 스벅 바로 거기까지의 거리가 더 짧을 것이기 때문이다.
즉, 맥날부터 스벅까지의 최단 거리를 구하되, 맥날부터 스벅까지 몇 개의 길을 거쳐갔는지 기록해서 .... 가 아니라.. 안된다. 몇 개의 길을 거쳤는지 기록해서 원래 2개 이상 거친 것 중에서 최단 거리를 찾으려 했지만 그럴 경우 중간에 스벅이 끼어있고 일반 집은 없을 수도 있다. 이런 경우를 커버할 수 없다.
꽝이다! 잘못 생각했다.
그리고 다시 생각해보니 이 문제는 무작정 맥날과 스벅사이의 최단 거리를 구하는 문제는 아닌 것 같다. 왜냐하면 어떤 집이 꼭 맥날과 스벅 사이에 있어야 할까? 아니다
맥날 - 집 - 스벅 이 아닌 맥날 - 스벅 - 집 일 수도 있다!!! 왜냐하면 문제에서 구하라는 것은 집의 맥도날드까지의 최단거리와 스타벅스까지의 최단거리 합이므로...
그렇다면 어떻게 해야할까?
생각해봤다.
다익스트라를 두 번 돌린다. 처음에는 새로운 출발점을 맥날들에 연결하고 시작해서 일단 일반 집까지의 최단 거리를 다 구하고, 또하나의 새로운 출발점을 일반 집들에 연결하되 간선의 가중치는 앞서 구한 맥날에서 각 집까지의 최단 거리로 놓는다. 그리고 dist배열을 다익스트라 처음 시작할 때 처럼 다 초기화한 후 그 출발점에서 시작해서 최단 거리를 구해서 스벅까지의 최단 거리를 보면 결국 맥날 - 집 - 스벅까지의 최단거리를 알 수 있게 될 것이다.
위와 같이 하면 첫 다익스트라에서 각 집에서 맥날까지의 최단 거리를 구했을 것이고 두번째 다익스트라에서 각 집에서 스벅까지... 아!!!
두 방법 모두 다 해봐야겠다. 아 그리고 맥세권, 스세권 모두 되는지 확인하는 것도 필요하다!
아 근데... 또 하나의 문제에 직면했다. 바로 맥세권 스세권을 따져주는 것인데, 각각 멕세권인지 스세권인지 따져야 하므로 좀 까다롭다...
일단 처음에 맥날에서 집까지의 거리는 맥세권 제한 x이하인 경우만 보는 걸로 처리하면 되는데, 각 집에서 (맥날에서의 최단 거리를 가지고) 출발해서 스벅까지의 최단거리를 구하는 과정에서가 문제다. 이 것을 해결하기 위해 아까 했던 것 처럼 출발점이 어딘지를 기록해서 최단거리를 다 구한 후 답을 구할 때, 스벅까지 최단거리-(출발점까지의 거리)의 값이 스세권 제한 y이하인지 판별해야 할 것 같다.
일단 그렇게 해서 AC를 받았다....
이 문제... 쉬운 줄 알았는데 그렇지 않았다.
그리고 생각해보니 집에서 출발해서 각 최단 거리를 구하고 출발지가 같은 것을 합하는 방식은 반례가 있다. 안된다...
예를 들어 맥날까지의 최단 거리는 집1에서 부터의 거리이고, 스벅까지의 최단 거리는 집2에서부터의 거리이고 답은 맥날 - 집1 - 집2 - 스벅 인 경우를 처리할 수 없다...
하지만 내가 맥날에서 집까지의 최단 거리를 구하고 그 값들을 가지고 각 집들에서 스벅까지의 최단 거리를 구하는 것은 잘 생각해보면, 집을 경유하는 (맥날에서 스벅까지의) 최단 경로를 구하는 것과 같기 때문에 가능한 것 같다.
좀 헷갈리기도 하고, 정말 좋은 문제였다.
그리고.. 다른 분들의 풀이를 보고 있는데.... 헉... 더 좋은 방법이 있었다.
맥날에서 각 집까지의 (맥세권인)최단 거리를 구하고, 스벅에서 각 집까지의 (스세권인)최단 거리를 구한 후 각 집을 기준으로 두 최단 거리를 합쳐서 그 중 최소값을 구하면 된다...
와... 이거 어디서 본 것 같은데.. 익숙한 방법인데 난 전혀 생각도 못하고 괜히 어렵게 생각하고 있었다. 이렇게 하면 또 좋은 것이 맥세권인지 스세권인지 판단하기 편하다 그냥 다익스트라 함수 내부에서 바로 각 집까지의 거리가 맥세권이나 스세권인 경우만 처리하면 된다.
그리고 훨씬 이해하기도 좋은 방법같다. 문제를 많이 풀어보고 공부도 많이 해야한다...
BOJ 13908 비밀번호
어렵다. 생각이 잘 안난다.
그래서 떠오르는 건 brute force밖에 없다...
일단은 최대 7자리 숫자이기 때문에, 모든 숫자를 다 만들면 1000만 번이 필요하다.
그리고 각 숫자에 대해서 주어진 m개의 숫자를 포함하는지 확인하는데 7번이면 된다.
즉, 모든 경우를 다 해봐도 7천만 번에 다 처리할 수 있다.
해보자. 좀 더 효율적이고 좋은 방법이 있을 법도 한데... 일단 이렇게 해보자.
각 숫자에 대해 주어진 m개의 숫자를 포함하는지 확인하는 부분에서 살짝 까다로웠지만 일단 구현은 했다.
AC는 받았는데, 시간이 역시 엄청 걸렸다. 그리고 맞은 사람 목록을 보니 나보다 훨씬 시간이 적게 걸린 분들이 많고 심지어 0ms로 푸신 분들도 꽤 있다.
어떤 분의 코드를 봤는데 그 분의 코드는 n, m만 입력 받길래 도대체 다른 입력은 어디서 받는 건가 궁금해서 실행해봤더니 다른 입력은 받지 않고 그냥 n, m만 입력하면 답이 나온다...?! 헉.. 아... 그렇다.. 그런 것이다. 바로 m만 알면 m개의 수가 어떤 수이든 간에(문제에서 서로 다른 수라고 했으니) 경우의 수는 똑같이 나오는 것이다...!!!
와...생각도 못했었네... 그 분의 코드를 살펴보니 매우 짧고 간결한데 분석해본 결과 다음과 같다.
일단, 모든 수를 구하시긴 하는데 bit연산과 재귀를 이용해서 구한다. 예를 들어 3자리 수라고 하면 각 자리에서 어떤 수를 선택했는지를 표시하는 것이 아닌 0부터 9중 어떤 수를 선택했는지만 표시한다. 각 자리별로 dfs 깊이를 들어가면서 (즉 깊이는 자리 수 만큼 들어가게 된다) 0부터 9중에 어떤 수를 선택하는지 기록한다. 결국 모든 경우를 다 보게 되고, 마지막 자리까지 다 선택한 후 위의 m개의 수가 어떤 수든 간에 똑같다는 것을 이용해서 미리 만들어 놓은 (1<<m)-1 즉 0, 1, .., m-1까지의 수 자리를 1로 채워놓은 것과 &연산을 통해서 (1<<m)-1이 그대로 나온다면 0부터 m-1까지의 수 즉, m개의 수가 포함되었다는 것이므로 카운트를 한다....
와우.. 위의 방법은 모든 경우를 구하되 정말 딱 필요한 것만 쓴 그런 방법 같다. 멋지다. 재귀를 통해 모든 경우를 다 구하고 (그렇게 안 보이지만 다 구하는 거나 마찬가지) 비트 연산을 적절히 활용해서 m개의 수가 포함되었는지 계산하는 정말 멋있는 방법같다.
자 이제 0ms 코드를 분석해 봐야겠다.
근데 이해는 잘 못하겠다.
대충 식을 써보면
10^n - nC1 * 9^n + nC2 * 8^n - nC3 * 7^n + .... 이런 식으로 덧셈 뺄셈을 번갈아 가면서... 가는 왠지 어디선가 본 모양의 식이다. 익숙하긴 한데.. 모르겠다. 아 수학 공부 열심히 할 걸... 후회할 건 후회하고 지금부터 열심히 하면된다. 늦었지만 안 하는 것보단 훨씬 낫다.
이 문제는 수학 공부좀 해보고 다시 도전해보자. 정수론, 이산수학, 고등수학...
그래서 떠오르는 건 brute force밖에 없다...
일단은 최대 7자리 숫자이기 때문에, 모든 숫자를 다 만들면 1000만 번이 필요하다.
그리고 각 숫자에 대해서 주어진 m개의 숫자를 포함하는지 확인하는데 7번이면 된다.
즉, 모든 경우를 다 해봐도 7천만 번에 다 처리할 수 있다.
해보자. 좀 더 효율적이고 좋은 방법이 있을 법도 한데... 일단 이렇게 해보자.
각 숫자에 대해 주어진 m개의 숫자를 포함하는지 확인하는 부분에서 살짝 까다로웠지만 일단 구현은 했다.
AC는 받았는데, 시간이 역시 엄청 걸렸다. 그리고 맞은 사람 목록을 보니 나보다 훨씬 시간이 적게 걸린 분들이 많고 심지어 0ms로 푸신 분들도 꽤 있다.
어떤 분의 코드를 봤는데 그 분의 코드는 n, m만 입력 받길래 도대체 다른 입력은 어디서 받는 건가 궁금해서 실행해봤더니 다른 입력은 받지 않고 그냥 n, m만 입력하면 답이 나온다...?! 헉.. 아... 그렇다.. 그런 것이다. 바로 m만 알면 m개의 수가 어떤 수이든 간에(문제에서 서로 다른 수라고 했으니) 경우의 수는 똑같이 나오는 것이다...!!!
와...생각도 못했었네... 그 분의 코드를 살펴보니 매우 짧고 간결한데 분석해본 결과 다음과 같다.
일단, 모든 수를 구하시긴 하는데 bit연산과 재귀를 이용해서 구한다. 예를 들어 3자리 수라고 하면 각 자리에서 어떤 수를 선택했는지를 표시하는 것이 아닌 0부터 9중 어떤 수를 선택했는지만 표시한다. 각 자리별로 dfs 깊이를 들어가면서 (즉 깊이는 자리 수 만큼 들어가게 된다) 0부터 9중에 어떤 수를 선택하는지 기록한다. 결국 모든 경우를 다 보게 되고, 마지막 자리까지 다 선택한 후 위의 m개의 수가 어떤 수든 간에 똑같다는 것을 이용해서 미리 만들어 놓은 (1<<m)-1 즉 0, 1, .., m-1까지의 수 자리를 1로 채워놓은 것과 &연산을 통해서 (1<<m)-1이 그대로 나온다면 0부터 m-1까지의 수 즉, m개의 수가 포함되었다는 것이므로 카운트를 한다....
와우.. 위의 방법은 모든 경우를 구하되 정말 딱 필요한 것만 쓴 그런 방법 같다. 멋지다. 재귀를 통해 모든 경우를 다 구하고 (그렇게 안 보이지만 다 구하는 거나 마찬가지) 비트 연산을 적절히 활용해서 m개의 수가 포함되었는지 계산하는 정말 멋있는 방법같다.
자 이제 0ms 코드를 분석해 봐야겠다.
근데 이해는 잘 못하겠다.
대충 식을 써보면
10^n - nC1 * 9^n + nC2 * 8^n - nC3 * 7^n + .... 이런 식으로 덧셈 뺄셈을 번갈아 가면서... 가는 왠지 어디선가 본 모양의 식이다. 익숙하긴 한데.. 모르겠다. 아 수학 공부 열심히 할 걸... 후회할 건 후회하고 지금부터 열심히 하면된다. 늦었지만 안 하는 것보단 훨씬 낫다.
이 문제는 수학 공부좀 해보고 다시 도전해보자. 정수론, 이산수학, 고등수학...
BOJ 13906 대문자
소문자로만 이루어진 문장이 주어지고, 인접한 세 개의 동일한 소문자를 하나의 대문자로 바꿀 수 있다. 그리고 어떤 소문자든지 지울 수 있고 안 지워도 상관없다. 이 때, 주어진 소문자 열로 만들 수 있는 모든 대문자로만 이루어진 문장의 개수를 구해야 한다.
dp로 접근해보자.
d[xth] = xth번째에서 n번째까지의 문자열에서 만들어 질 수 있는...
모르겠다. 나중에 다시 풀어보자.
dp로 접근해보자.
d[xth] = xth번째에서 n번째까지의 문자열에서 만들어 질 수 있는...
모르겠다. 나중에 다시 풀어보자.
Plane Sweeping BOJ 3392 화성 지도 7626 직사각형
plane sweeping(평면 스위핑, line sweeping이라고도 함) 에 대해 공부해보려 한다.
일단 JM book에 나와있는 평면 스위핑은 O(N제곱)의 시간복잡도를 가진다. 이 것으로 3392 화성 지도 문제는 통과됐지만 아마 7626번 문제를 풀기위해선 좌표압축을 하고 O(NlogN)의 플레인 스위핑이 필요하다.
O(NlogN)짜리 평면 스위핑을 위해서는 segment tree를 써야하는데 감사하게도 검색해보면 잘 정리된 블로그가 몇 개 있다.
그 중 내가 참고한 블로그인데
그림과 함께 매우 잘 설명이 되어있다. 하지만 아마 O(N제곱)짜리 plane sweeping도 이해 못한 상태에서 본다면 전혀 이해가 안될 수도 있다...(내가 그랬다.) 그리고 위의 블로그에는 좌표 압축을 하는 경우와 하지 않는 경우 둘 다 코드가 있다.
일단 난 좌표압축이 필요한 경우를 공부해 보려고 한다.
JM book 의 O(N제곱) plane sweeping 이해 -> 세그먼트 트리, 좌표 압축에 대해 공부 -> O(NlogN)짜리 plane sweeping 공부
일단 위의 블로그에서 설명하는 plane sweeping알고리즘의 원리 자체는 O(N제곱)짜리와 같지만 segment tree를 사용하는데, segment tree가 일반적인(내가 여태 사용해 왔던) segment tree와 좀 다르다.
라인 하나로 왼쪽에서부터 오른쪽으로 평면을 쓸면서 봐야하는데 보면서 만나는 직사각형의 세로 선들을 구별해서(직사각형의 왼쪽 세로선인지 오른쪽 세로선인지..) count를 해줘야 한다. 그리고 이 세그먼트 트리에서는 count에 따라 상위 노드를 업데이트 할지 말지 결정하게 된다.
좌표 압축을 한 상태에서 봐도 세그먼트 트리는 y축의 모든 구간을 다 커버한다. 즉 라인이 움직이면서 만난 직사각형의 y축 범위가 어느 범위든 간에 다 커버된다. 그리고 세그먼트 트리를 이용하면 세그먼트 트리에서 y축 범위에 해당하는 부분을 logN만에 업데이트하는데, 원래 세그먼트 트리에서 range update는 lazy propagation을 쓰지 않으면 range * logN만큼 걸렸다.
그래서 어찌보면 여기서 사용하는 segment tree의 방식이 lazy propgation과 형태가 조금 비슷..?..하다고 볼 수 있겠다.
어쨌든, update를 할 때, 해당 범위의 leaf node들까지 다 업데이트 하는 것이 아니라 해당 범위에 해당하는 가장 위쪽의 node들만 업데이트 한다. 그리고 직사각형의 시작 부분에 해당하면 +1, 끝부분에 해당하는 세로 선이면 -1을 해서 count를 기록한다.
이 세그먼트 트리의 노드들은 count값과 y축의 크기값을 가지고 있는데, count가 1이상인 것은 현재 라인이 y축의 크기만큼 직사각형과 겹쳐있다는 뜻이고 count는 겹쳐있는 직사각형의 개수를 뜻한다.
count가 1이상이면 해당 범위에 해당하는 가장 위쪽의 node에 해당하는 것으로 보면되고, y축의 크기값은 존재하는데 count 가 0이면 count가 1이상인 노드들의 합을 저장하고 있는 것으로 보면된다. 그리고 우리가 필요로 하는 것은 현재 라인이 직사각형들과 겹쳐 있는 총 길이이고 그 값은 전 범위를 나타내는 세그먼트 트리의 루트 노드에 저장되어 있다.
바로 그 루트 노드값이 logN만에 업데이트 될 수 있도록 segment tree를 사용하는 것이다.
그래서 좀 자세한 동작 과정을 보면 어떤 노드의 count값이 0에 해당하면 자식 노드들의 합으로 업데이트를 해준다. 하지만 count가 1이상이면 자식 노드들의 합으로 업데이트 하지 않고 자신의 값을 가지고 있는다. 즉, count값이 1이상인 것은 해당 범위에 직사각형이 존재한다는 것을 의미하고, 그 직사각형의 세로길이(y축 크기)를 기록해야 한다. 예를 들어, 그 노드의 자식 노드에 해당하는 부분에 있던 직사각형이 없어진 것을 반영해서 그 노드를 업데이트 해버리면, 그 노드에 해당하는 직사각형은 존재하는데, 그 직사각형의 일부가 사라지게 되는 잘못된 결과를 내게 된다.
라인을 움직이면서 어떤 직사각형의 시작 선이나 끝 선을 만날 때마다 변화가 생기므로 그 때마다 변화가 생기기전의 넓이 값을 계산해서 더해주는 식으로 나가는 것이다.
사실 내가 완벽히 이해하진 못했는데, 계속 고민하기 보다 일단 내가 이해한 데까지만 기록해두고 직접 짜보는 것이 좋을 것 같다. dfs, bfs가 그랬던 것처럼 dp가 그랬던 것처럼... 언젠가는 더 이해하게 될 날이 올 것이다. 너무 시간 끌지말고 앞으로 나아가자.
2016년 11월 28일 월요일
BOJ 13902 개업 2
항상 주어진 웍에 딱 맞게 요리해야 하고, 한 번에 두 개의 웍으로 동시에 요리가 가능하다.
주어진 양을 처리하기 위해 필요한 최소 요리 횟수를 구하는 문제이다.
같은 크기의 웍이 여러개 주어질 수도 있으므로 웍의 크기별 개수도 기록해야 할 것 같다...
일단 웍에 딱 맞게 요리해야 하므로... 느낌이 동전 문제와 비슷한 느낌이 든다.
dp...!! 그리고 생각해보면 두 개의 웍으로 동시에 요리가 가능하므로 같은 크기의 웍이 3개이상 있는 것은 의미 없다.
d[n] = 짜장면 n개 주문을 처리하기 위해 필요한 최소 요리 횟수
d[n] = min(x1, x2 가능한 모든 경우.. | d[n-x1-x2] + 1)
웍의 개수가 최대 1000개인데, 이 중 2개를 골라서 쓰는 경우와 1개만 쓰는 경우가 있는데, 1개만 쓰는 경우는 1000가지이고, 2개를 골라서 쓰는 경우는 최대 1000C2 = 1000*999/2 = 약 50만...
n제한은 10000이기에.. 시간초과가 날 것 같다.
저 50만을 좀 줄여볼 방법으로... 1개를 골라쓰고, 2개를 골라쓰는 경우로 볼 것이 아니라 한 번에 얼마나 요리하는지로 보면 될 것 같다. (어차피 n이 1이상 10000이하이므로)
대신 미리 50만번 정도의 연산을 통해 한 번에 요리할 수 있는 양의 경우를 다 구해놓고
d[n] = min(x의 가능한 모든 경우 | d[n-x] + 1) 이런 식으로 dp를 해보면 될 것 같다.
AC를 받고 다른 분들의 코드를 보는데 어떤 분의 코드는 나와 방식은 비슷한데, 나처럼 미리 한 번에 요리할 수 있는 양의 경우를 다 구하는 것을 그냥 바로 d배열에 한 번에 요리할 수 있는 양의 경우x에 대해 d[x]=1로 초기화를 해주도, d[n] = min(d[n-x]+d[x]) ... 이런 식으로 구현돼있다. 결국 나랑 연산하는 수도 비슷하고 거의 똑같아 보이는데 시간차이는 꽤 많이 난다. 내 코드가 더 느리다...
이 문제는 처음 볼 때는 어려워 보였지만 dp로 접근해서 시간 초과 문제에 직면했을 때, 시간을 줄이기 위해 어떻게 해야할까 고민해서 풀었고 좋은 문제같다.
2016년 11월 24일 목요일
BOJ 13905 세부 주의할 점과 간략 풀이
이 문제는 1939 중량 제한 문제와 거의 같은 문제인데,
주의해야할 점이 있다.
내가 처음에 이분 탐색을 이용해서 구현했는데, WA를 받았다.
내 코드를 아무리 살펴봐도 틀린점이 없어 보이는데... 뭐 틀린점이 없어보여도 틀린 경우가 많긴하지만...
알고보니 난 이분 탐색을 구현할 때, l=0, r=1000000로 두고, 답은 r을 출력하는 식으로 했는데, 그것이 틀린 원인이었다. l=1로 두면 AC를 받는다. 엥?? 뭐지 그래서 이번에는 r을 출력하는 방식이 아닌 ans라는 변수를 따로 두고 했는데 ans를 -1, 1로 초기화해 봤는데 둘 다 틀리게 나오는 것이었다. 그래서 ans를 0으로 초기화했더니 AC를 받았다...!?...
생각해보니... 출발지에서 목적지까지 갈 수 없는 경우가 있는 것 같다.
위에서 l, r을 사용할 경우 l=0으로 두고 할 경우, r=mid-1이 계속 되어 결국 r=-1이 되고 끝나게 된다. 그래서 목적지까지 갈 수 없는 경우는 0을 출력해야 되는데 그렇지 못한 것이다.
하지만 같은 경우에 l=1로 둘 경우, r=0이 되고 끝난다.
분명 이분 탐색으로 모든 경우를 다 볼 수는 있지만, 아예 경로가 존재하지 않는 경우를 전혀 생각못했다.
l, r을 이용해서만 풀려고 했던 것과, ans를 -1로 초기화하는 습관때문에 알아낼 수 있었다.
감사합니다.
다익스트라나 MST+LCA로 풀 경우에도 주의해야 할 것 같다.
다익스트라는 할 만할 것 같은데, 목적지까지 가는 경로가 없는 경우 MST를 만들 때 목적지가 포함이 안될 것이고... 그럼 MST에서 depth를 구할 때 -1로 초기화하고, 출발점이나 도착점의 depth가 제대로 구해지지 않으면 거기서 바로 끊어서 0을 출력하든지 해야할 것 같다.
크루스칼로 MST를 만든 후에 출발점과 도착점이 같은 그래프에 속해있는지를 살펴보고 같은 그래프가 아니면 바로 0을 출력하는 것이 더 좋아보인다.
MST + LCA로 풀었는데, WA를 받았다. 도대체 뭐가 문제인지 모르겠어서 랜덤 데이터로 비교해 보는데도... 계속 정답 코드와 같은 결과가 나오다가.. 결국 다른 데이터를 발견했다!!!
아... 다행히 데이터 크기도 작아서 직접 MST를 그려보고 했는데...
이 문제에서는 경로가 존재하지 않는 경우도 있다고 했는데, 바로 그래프가 여러개로 나눠져 있을 수 있다는 것이고, 정점이 동떨어져 있을 수도 있다.
나는 MST에서 depth를 찾기 위해서 dfs를 할 때, root를 1로 두고 했는데... 1이 MST에 포함 안 되었을 수도 있다. 그래서 안전하게 출발점 or 도착점을 root로 하면 될 것 같다.
AC를 받았다!! 아 진짜 이런 건 생각도 못했다.. 진짜 그래프가 나눠져 있으니 주의해야 할 것이 많은 것 같다. 아마 랜덤 데이터가 나오지 않았다면 못 찾았을 것이다... 감사합니다!
이제 dijkstra, MST+LCA로 풀었으니
MST+dfs로 풀어 봐야겠다.
dfs가 쉬울 줄 알았는데 막상 해보니 까다롭다... 오히려 MST+다익스트라 돌리는 게 더 쉬울지도... dfs로 구현하기가 힘들어서 일단 전역변수 ans를 두고, dfs를 s에서 시작해서 return값은 도달한 노드번호로 해서 return값이 e이면 ans에 해당 cost를 비교해서 최소값을 넣고 return e를 해준다... 그냥 아래에 적어놓은 질문 게시판의 어떤 분의 방법이 젤 좋을 듯하다. MST를 만들면서 찾아주는 게 제일 나을듯... 한 번 그렇게 구현해 봐야겠다.
이 방법이 제일 간단하고 멋지고 빠른 것 같다.
그리고 MST로 할 경우 LCA외에 dfs로 해도 되겠지만, 질문 게시판에 올라온 어떤 분의 글을 보니 그 분은 크루스칼 알고리즘으로 MST를 만들면서 출발점과 도착점이 같은 부모를 가지게 되는 순간(같은 그래프에 속하는 순간)의 간선의 가중치 값을 출력하는 식으로 구현하셨다. 그 순간이 출발점과 도착점 사이를 잇는 경로가 완성되는 순간이면서 그 때의 가중치가 최소값이기 때문이다. 물론 이 경우도 마지막에 0을 출력해줘야 한다.
1939 중량제한 문제도 이렇게 풀어봐야겠다.
이 문제는 데이터로 여러 개로 나눠져 있는 그래프가 들어오기 때문에 고려할 부분이 좀 있는 문제였다. 좋은 문제 였고 많은 공부가 되었다.
참고 : https://www.acmicpc.net/board/view/10880
주의해야할 점이 있다.
내가 처음에 이분 탐색을 이용해서 구현했는데, WA를 받았다.
내 코드를 아무리 살펴봐도 틀린점이 없어 보이는데... 뭐 틀린점이 없어보여도 틀린 경우가 많긴하지만...
알고보니 난 이분 탐색을 구현할 때, l=0, r=1000000로 두고, 답은 r을 출력하는 식으로 했는데, 그것이 틀린 원인이었다. l=1로 두면 AC를 받는다. 엥?? 뭐지 그래서 이번에는 r을 출력하는 방식이 아닌 ans라는 변수를 따로 두고 했는데 ans를 -1, 1로 초기화해 봤는데 둘 다 틀리게 나오는 것이었다. 그래서 ans를 0으로 초기화했더니 AC를 받았다...!?...
생각해보니... 출발지에서 목적지까지 갈 수 없는 경우가 있는 것 같다.
위에서 l, r을 사용할 경우 l=0으로 두고 할 경우, r=mid-1이 계속 되어 결국 r=-1이 되고 끝나게 된다. 그래서 목적지까지 갈 수 없는 경우는 0을 출력해야 되는데 그렇지 못한 것이다.
하지만 같은 경우에 l=1로 둘 경우, r=0이 되고 끝난다.
분명 이분 탐색으로 모든 경우를 다 볼 수는 있지만, 아예 경로가 존재하지 않는 경우를 전혀 생각못했다.
l, r을 이용해서만 풀려고 했던 것과, ans를 -1로 초기화하는 습관때문에 알아낼 수 있었다.
감사합니다.
다익스트라나 MST+LCA로 풀 경우에도 주의해야 할 것 같다.
다익스트라는 할 만할 것 같은데, 목적지까지 가는 경로가 없는 경우 MST를 만들 때 목적지가 포함이 안될 것이고... 그럼 MST에서 depth를 구할 때 -1로 초기화하고, 출발점이나 도착점의 depth가 제대로 구해지지 않으면 거기서 바로 끊어서 0을 출력하든지 해야할 것 같다.
크루스칼로 MST를 만든 후에 출발점과 도착점이 같은 그래프에 속해있는지를 살펴보고 같은 그래프가 아니면 바로 0을 출력하는 것이 더 좋아보인다.
MST + LCA로 풀었는데, WA를 받았다. 도대체 뭐가 문제인지 모르겠어서 랜덤 데이터로 비교해 보는데도... 계속 정답 코드와 같은 결과가 나오다가.. 결국 다른 데이터를 발견했다!!!
아... 다행히 데이터 크기도 작아서 직접 MST를 그려보고 했는데...
이 문제에서는 경로가 존재하지 않는 경우도 있다고 했는데, 바로 그래프가 여러개로 나눠져 있을 수 있다는 것이고, 정점이 동떨어져 있을 수도 있다.
나는 MST에서 depth를 찾기 위해서 dfs를 할 때, root를 1로 두고 했는데... 1이 MST에 포함 안 되었을 수도 있다. 그래서 안전하게 출발점 or 도착점을 root로 하면 될 것 같다.
AC를 받았다!! 아 진짜 이런 건 생각도 못했다.. 진짜 그래프가 나눠져 있으니 주의해야 할 것이 많은 것 같다. 아마 랜덤 데이터가 나오지 않았다면 못 찾았을 것이다... 감사합니다!
이제 dijkstra, MST+LCA로 풀었으니
MST+dfs로 풀어 봐야겠다.
dfs가 쉬울 줄 알았는데 막상 해보니 까다롭다... 오히려 MST+다익스트라 돌리는 게 더 쉬울지도... dfs로 구현하기가 힘들어서 일단 전역변수 ans를 두고, dfs를 s에서 시작해서 return값은 도달한 노드번호로 해서 return값이 e이면 ans에 해당 cost를 비교해서 최소값을 넣고 return e를 해준다... 그냥 아래에 적어놓은 질문 게시판의 어떤 분의 방법이 젤 좋을 듯하다. MST를 만들면서 찾아주는 게 제일 나을듯... 한 번 그렇게 구현해 봐야겠다.
이 방법이 제일 간단하고 멋지고 빠른 것 같다.
그리고 MST로 할 경우 LCA외에 dfs로 해도 되겠지만, 질문 게시판에 올라온 어떤 분의 글을 보니 그 분은 크루스칼 알고리즘으로 MST를 만들면서 출발점과 도착점이 같은 부모를 가지게 되는 순간(같은 그래프에 속하는 순간)의 간선의 가중치 값을 출력하는 식으로 구현하셨다. 그 순간이 출발점과 도착점 사이를 잇는 경로가 완성되는 순간이면서 그 때의 가중치가 최소값이기 때문이다. 물론 이 경우도 마지막에 0을 출력해줘야 한다.
1939 중량제한 문제도 이렇게 풀어봐야겠다.
이 문제는 데이터로 여러 개로 나눠져 있는 그래프가 들어오기 때문에 고려할 부분이 좀 있는 문제였다. 좋은 문제 였고 많은 공부가 되었다.
참고 : https://www.acmicpc.net/board/view/10880
2016년 11월 22일 화요일
BOJ 13904 과제
하루에 하나의 과제를 끝낼 수 있고, 각 과제마다 마감일까지 남은 일수가 주어진다. 마감일을 넘으면 과제에 대한 점수를 못받는다. 이 때, 받을 수 있는 점수의 최대값을 구하는 문제인데, 어디서 많이 본듯한 그리디 문제이다.
점수를 최대한으로 받으려면, 점수가 큰 과제를 우선적으로 하거나 많은 과제를 해야 한다.
여기서 마감일이 주어지는데,일단 점수가 크든 작든 마감일이 많이 남은 과제는 나중에 생각해도.. 일단 하루에 한 과제씩 할 수 있으므로 주어진 최대 마감일까지 하루에 한 과제씩 꼭 해야한다. 그리고 한 과제씩 하되 점수가 큰 과제를 해야한다.
그리고 마감일이 주어지면 어떤 과제든 마감일 안에 아무때나 해도 점수는 같기 때문에 마감일이 길면 마감일이 짧은 작업에 양보해주고 그 작업은 나중에 하는 것이 좋다.
그렇지만 마감일이 짧은 작업을 먼저 하느라 더 큰 과제를 놓치면 안되기 때문에 점수 순으로 정렬을 해서 점수가 큰 과제부터 본다.
그리고 어차피 하루에 한 과제가 최대이기 때문에 이왕 하는 거 점수가 큰 과제를 하는 것이 이익이다. 그리고 점수가 큰 과제부터 하되, 그 과제의 마감 기한의 마지막 날에 해야 마감일이 짧은 작업들을 최대한 많이 할 수 있다.
그래서 점수가 큰 과제부터 하되, 마감 기한의 마지막 날에 배정하면서 점수를 계산하면 될 것이다.
BOJ 2109 순회 강연 문제와 비슷한 문제이길래 내가 블로그에 정리해놓은 것을 봤는데,
다시 정리해보면 어떤 날에 과제를 할 것이라면 가장 큰 점수의 과제를 하는 것이 좋고, 앞의 날들일수록 과제들끼리 공유되는 부분이 크므로(즉, 가능한 과제의 경우가 많으므로) 그 과제의 기한의 마지막 날에 하는 것이 가장 좋은 방법이다. 그리고 만약 가장 큰 점수의 과제 대신 작은 점수의 과제를 한다고 해서 이익이될 것이 없다. 왜냐하면 그날 할 수 있는 과제는 어차피 1개이고, 그날 과제를 함으로써 영향이 발생하는 것은 그날이 기한 안에 있는 과제들을 못하게 된다는 것인데, 앞서 말했듯이 그 날 하나의 과제를 할 것이라면 가장 큰 점수를 하는 것이 이익이므로 가장 큰 점수의 과제를 그 과제의 기한의 끝에 하는 것이 가장 큰 점수를 얻는 방법이 될 것이다.
점수를 최대한으로 받으려면, 점수가 큰 과제를 우선적으로 하거나 많은 과제를 해야 한다.
여기서 마감일이 주어지는데,
그리고 마감일이 주어지면 어떤 과제든 마감일 안에 아무때나 해도 점수는 같기 때문에 마감일이 길면 마감일이 짧은 작업에 양보해주고 그 작업은 나중에 하는 것이 좋다.
그렇지만 마감일이 짧은 작업을 먼저 하느라 더 큰 과제를 놓치면 안되기 때문에 점수 순으로 정렬을 해서 점수가 큰 과제부터 본다.
그리고 어차피 하루에 한 과제가 최대이기 때문에 이왕 하는 거 점수가 큰 과제를 하는 것이 이익이다. 그리고 점수가 큰 과제부터 하되, 그 과제의 마감 기한의 마지막 날에 해야 마감일이 짧은 작업들을 최대한 많이 할 수 있다.
그래서 점수가 큰 과제부터 하되, 마감 기한의 마지막 날에 배정하면서 점수를 계산하면 될 것이다.
BOJ 2109 순회 강연 문제와 비슷한 문제이길래 내가 블로그에 정리해놓은 것을 봤는데,
다시 정리해보면 어떤 날에 과제를 할 것이라면 가장 큰 점수의 과제를 하는 것이 좋고, 앞의 날들일수록 과제들끼리 공유되는 부분이 크므로(즉, 가능한 과제의 경우가 많으므로) 그 과제의 기한의 마지막 날에 하는 것이 가장 좋은 방법이다. 그리고 만약 가장 큰 점수의 과제 대신 작은 점수의 과제를 한다고 해서 이익이될 것이 없다. 왜냐하면 그날 할 수 있는 과제는 어차피 1개이고, 그날 과제를 함으로써 영향이 발생하는 것은 그날이 기한 안에 있는 과제들을 못하게 된다는 것인데, 앞서 말했듯이 그 날 하나의 과제를 할 것이라면 가장 큰 점수를 하는 것이 이익이므로 가장 큰 점수의 과제를 그 과제의 기한의 끝에 하는 것이 가장 큰 점수를 얻는 방법이 될 것이다.
BOJ 13903 출근
음 일반적인 bfs문제이다. 처음 시작점이 될 수 있는 1행의 세로블럭들을 큐에 다 넣어두고 bfs탐색을 시작한다. 하지만 내가 bfs문제를 오랜만에 풀어서 그런지... 틀렸다. 그리고 도저히 원인을 찾을 수 없다가 도움을 받아 겨우 원인을 찾았다. 바로 .... 처음에 1행의 세로블럭들(출발점들)을 큐에 넣을 때, 방문했다는 표시를 하지 않은 것이다... 아 이런 실수를... 전에도 이런 실수를 했었는데... 으악...난 내 코드에는 문제 없다고 생각하고 그냥 문제에 내가 생각치 못한 함정이 있는 것인가 생각하고 있었다.
만약 처음 출발점을 방문했다는 표시를 하지 않을 경우, 생길 수 있는 문제에 대해 생각해보자. 그 출발점에서 출발해서 다시 돌아오는 건 별 상관없어보인다. 도착점까지의 최단거리만 구하면 되니까... 하지만 출발점이 여러개이기 때문에 한 출발점에서 다른 출발점으로 이동해서 그 시작점의 dist를 0에서 1로 바꿔버릴 수 있다. 그렇게 되면 도착점까지의 최단거리를 제대로 구할 수 없을 수도 있다.
앞으로 조심하자.
만약 처음 출발점을 방문했다는 표시를 하지 않을 경우, 생길 수 있는 문제에 대해 생각해보자. 그 출발점에서 출발해서 다시 돌아오는 건 별 상관없어보인다. 도착점까지의 최단거리만 구하면 되니까... 하지만 출발점이 여러개이기 때문에 한 출발점에서 다른 출발점으로 이동해서 그 시작점의 dist를 0에서 1로 바꿔버릴 수 있다. 그렇게 되면 도착점까지의 최단거리를 제대로 구할 수 없을 수도 있다.
앞으로 조심하자.
BOJ 13900 순서쌍의 곱의 합
주어진 N개의 정수로 만들 수 있는 순서쌍의 각각의 곱들의 합을 구하는 문제이다.
주어진 N개의 정수들로 만들 수 있는 조합의 각각의 곱들의 합을 구하는 문제로 보면 되는데, 내가 이 문제에 대해 생각한 것은 아니고 풀기전에 미리 풀이와 주의할 점을 들었기 때문에 바로 풀이와 주의할 점을 정리하겠다.
일단 주의할 점은 N개의 정수 중에서 2개를 뽑는 조합으로 보면 편하지만, 예를 들어 2, 2, 4가 주어지면 (2, 2), (2, 4) 로 끝이 아니라 (2, 2), (2, 4), (2, 4) 이렇게 3개이다.
그리고 오히려 이 주의할 점때문에 구하기가 편해진다.
만약 그냥 모든 순서쌍에 대해 일일이 다 구하려면 n이 10만개이기 때문에 O(n제곱)으로 시간초과가 날 것이다. 하지만 정말 멋진 방법이 있다.
이 문제에서 구하라는 것을 잘 보자.
각 조합에 속한 수의 곱의 합인데
2, 3, 4를 예로 들어보면
(2, 3), (2, 4), (3, 4) 이 세가지 조합에서 2*3 + 2*4 + 3*4 가 답이 된다.
잘 보면 2*(3+4) + 3*4로 나타낼 수 있다!!
그렇다. 미리 prefix sum을 구해놓게 되면 부분합을 O(1)만에 구할 수 있게 되고, 부분합을 알면 어떤 수x로 시작하는 조합의 곱들의 합을 O(1)만에 구할 수 있게 된다. 결국 문제에서 구하라고 하는 것을 O(n)만에 구할 수 있을 것이다.
AC를 받고 다른 분들의 풀이를 보니 이해는 잘 안 되지만 O(1)만에 구하신 분들도 있다... 그리고 어떤 분은 위의 과정을 그냥 입력받으면서 바로 처리하신 분도 있다... 별거 아닌 것 같아도 나는 생각도 못했는데...엄청나신 것 같다 다들...
추가 : 슬랙에 질문 게시판에 올라온 질문이 떠서 우연히 봤다.
이런 풀이도 있다 : https://www.acmicpc.net/board/view/10848
주어진 N개의 정수들로 만들 수 있는 조합의 각각의 곱들의 합을 구하는 문제로 보면 되는데, 내가 이 문제에 대해 생각한 것은 아니고 풀기전에 미리 풀이와 주의할 점을 들었기 때문에 바로 풀이와 주의할 점을 정리하겠다.
일단 주의할 점은 N개의 정수 중에서 2개를 뽑는 조합으로 보면 편하지만, 예를 들어 2, 2, 4가 주어지면 (2, 2), (2, 4) 로 끝이 아니라 (2, 2), (2, 4), (2, 4) 이렇게 3개이다.
그리고 오히려 이 주의할 점때문에 구하기가 편해진다.
만약 그냥 모든 순서쌍에 대해 일일이 다 구하려면 n이 10만개이기 때문에 O(n제곱)으로 시간초과가 날 것이다. 하지만 정말 멋진 방법이 있다.
이 문제에서 구하라는 것을 잘 보자.
각 조합에 속한 수의 곱의 합인데
2, 3, 4를 예로 들어보면
(2, 3), (2, 4), (3, 4) 이 세가지 조합에서 2*3 + 2*4 + 3*4 가 답이 된다.
잘 보면 2*(3+4) + 3*4로 나타낼 수 있다!!
그렇다. 미리 prefix sum을 구해놓게 되면 부분합을 O(1)만에 구할 수 있게 되고, 부분합을 알면 어떤 수x로 시작하는 조합의 곱들의 합을 O(1)만에 구할 수 있게 된다. 결국 문제에서 구하라고 하는 것을 O(n)만에 구할 수 있을 것이다.
AC를 받고 다른 분들의 풀이를 보니 이해는 잘 안 되지만 O(1)만에 구하신 분들도 있다... 그리고 어떤 분은 위의 과정을 그냥 입력받으면서 바로 처리하신 분도 있다... 별거 아닌 것 같아도 나는 생각도 못했는데...엄청나신 것 같다 다들...
추가 : 슬랙에 질문 게시판에 올라온 질문이 떠서 우연히 봤다.
이런 풀이도 있다 : https://www.acmicpc.net/board/view/10848
BOJ 13909 창문 닫기
N개의 창문이 있고, 1번부터 N번까지의 사람이 있고 모든 창문은 닫혀있다.
1번 사람은 1의 배수 번째의 창문들을, 2번 사람은 2의 배수 번째의 창문들을, ..., n번 사람은 n의 배수 번째 창문들을 열려있으면 닫고, 닫혀있으면 여는 행동을 취한다.
1번 사람부터 n번 사람까지 이렇게 했을 때, 마지막에 열려있는 창문의 개수를 구하는 문제이다.
직접 어느정도 해보다 보면 감이 온다.
n번째 창문은 n의 약수의 개수에 따라 열리고 닫히게 된다. n의 약수의 개수가 홀수개이면 마지막에는 열리게 되고, 짝수개라면 마지막 상태는 닫힌 상태가 된다.
약수가 짝수개인지, 홀수개인지 어떻게 알 수 있을까?
어떤 수 n의 약수를 구해보면, 일단 1이 있을 것이고 그에 상응하는 n이 있을 것이다. 이처럼 어떤 약수x가 있으면 반드시 그에 상응하는 약수(n/x)가 하나 존재한다. 그렇다면 항상 짝수개일 수 밖에 없을까? 아니다. 바로 어떤 수의 제곱으로 나타낼 수 있는 수는 그렇지 않다. 어떤 수 n이 x의 제곱이라면 n의 약수의 개수는 x를 기준으로 왼쪽, 오른쪽의 약수는 서로 대응되어 짝수개이지만 x는 x자신과 대응되므로 한 개이다. 결국 홀수개가 된다.
결국 이 문제는 1부터 n까지의 수 중에서 완전 제곱수의 개수를 구하는 문제가 된다.
구현은 여러 방법이 있겠지만.. 음 일단 가장 먼저 생각난 것은 n의 범위가 최대 21억까지인데, 5만 * 5만이 25억이므로 5만부터 대충 5만보다 좀 작은 수에서 시작해서 그 수의 제곱이 주어진 n과 같거나 작아지는 순간을 찾는 방법이나 sqrt(n+1)값을 버림한 정수 값과 그 값에서 1을 뺀 값 중 답을 찾는 방법을 쓰면될 것 같은데.. AC를 받고 다른 분의 코드를 보니 그냥 1부터 시작해서 그 제곱이 n보다 같거나 작은 경우까지 돌리는 경우도 꽤 있는 것 같다.
1번 사람은 1의 배수 번째의 창문들을, 2번 사람은 2의 배수 번째의 창문들을, ..., n번 사람은 n의 배수 번째 창문들을 열려있으면 닫고, 닫혀있으면 여는 행동을 취한다.
1번 사람부터 n번 사람까지 이렇게 했을 때, 마지막에 열려있는 창문의 개수를 구하는 문제이다.
직접 어느정도 해보다 보면 감이 온다.
n번째 창문은 n의 약수의 개수에 따라 열리고 닫히게 된다. n의 약수의 개수가 홀수개이면 마지막에는 열리게 되고, 짝수개라면 마지막 상태는 닫힌 상태가 된다.
약수가 짝수개인지, 홀수개인지 어떻게 알 수 있을까?
어떤 수 n의 약수를 구해보면, 일단 1이 있을 것이고 그에 상응하는 n이 있을 것이다. 이처럼 어떤 약수x가 있으면 반드시 그에 상응하는 약수(n/x)가 하나 존재한다. 그렇다면 항상 짝수개일 수 밖에 없을까? 아니다. 바로 어떤 수의 제곱으로 나타낼 수 있는 수는 그렇지 않다. 어떤 수 n이 x의 제곱이라면 n의 약수의 개수는 x를 기준으로 왼쪽, 오른쪽의 약수는 서로 대응되어 짝수개이지만 x는 x자신과 대응되므로 한 개이다. 결국 홀수개가 된다.
결국 이 문제는 1부터 n까지의 수 중에서 완전 제곱수의 개수를 구하는 문제가 된다.
구현은 여러 방법이 있겠지만.. 음 일단 가장 먼저 생각난 것은 n의 범위가 최대 21억까지인데, 5만 * 5만이 25억이므로 5만부터 대충 5만보다 좀 작은 수에서 시작해서 그 수의 제곱이 주어진 n과 같거나 작아지는 순간을 찾는 방법이나 sqrt(n+1)값을 버림한 정수 값과 그 값에서 1을 뺀 값 중 답을 찾는 방법을 쓰면될 것 같은데.. AC를 받고 다른 분의 코드를 보니 그냥 1부터 시작해서 그 제곱이 n보다 같거나 작은 경우까지 돌리는 경우도 꽤 있는 것 같다.
BOJ 2336 굉장한 학생
N명의 학생이 세 번의 시험을 치룬 결과가 주어지는데, 세 번의 시험에서 한 학생이 다른 한 학생보다 세 번 모두 성적이 좋으면 더 "대단한" 것인데, 어떤 학생보다 "대단한" 학생이 없다면 그 학생은 "굉장한" 학생이다. 이 때, 굉장한 학생의 수를 구하는 문제이다.
즉, 자신보다 세 번 다 성적이 좋은 학생이 없는 학생의 수를 구하는 문제이다. (0번, 1번, 2번 성적이 좋은 학생들의 수)
문제 분류가 '세그먼트 트리'로 되어있는데, 쉽게 떠오르지 않는다. 처음부터 세그먼트 트리로 생각하려 해서 그런가? 한 번 그냥 푼다면 어떻게 풀 것인지 생각해 봐야겠다.
갑자기 떠오른 생각이, 굉장한 학생의 수를 바로 구하는 것보다, 굉장하지 않은 학생의 수를 구해서 빼는 게 나을 것 같다.
굉장하지 않은 학생의 수는 자신보다 세 번 모두 성적이 좋은 학생이 있는 학생의 수를 구하면 된다.
집중도 안되고 딴생각만 들고... 결국 풀이를 봤는데도 잘 이해가 안된다. 어렵다.
정신 차리고 차근차근히 풀이를 정리해 보자. 독서백편 의자현. 이해될 때까지...
일단 굉장한 학생의 수를 구해야 한다. 굉장한 학생은 자신보다 세 번 모두 성적이 좋은 학생이 없어야 한다. 문제에서는 등수 순으로 주어진다.
일단 각 학생별로 1번 학생이 세 시험에서 각각 몇등을 했는지, 2번 학생이 세 시험에서 가각 몇 등을 했는지,... n번 학생이 세 시험에서 각각 몇 등을 했는지를 기록한다.
그리고 세 개의 시험 중 하나의 시험의 등수를 기준으로 정렬한다. 여기서 많이 헷갈렸는데, 정렬해버리면 몇 번 학생이 몇 등했는지는 알 수 없다. 하지만 알 필요없다. 우리는 굉장한 학생의 수만 구하면 된다. 정렬했기 때문에 몇 번 학생인지는 몰라도 첫번째 시험에서 1등한 사람이 두번째 시험과 세번째 시험에서 몇 등을 했는지를 알 수 있다.
즉, 누군지는 몰라도 한 사람이 각 시험에서 몇 등을 했는지에 대한 정보가 하나의 시험을 기준으로 정렬되어 있다. 2번째 시험을 기준으로 정렬했다고 하고 예를 들어보겠다.
왼쪽부터 한 사람씩(한 열씩) 보면 두번째 시험에서 1등을 한 사람은 첫번째, 세번째 시험에서 각각 2등, 3등을 했다는 사실을 알 수 있다. 일단 사람1은 두번째 시험에서 1등이므로 첫번째, 세번째 시험에서 자기보다 잘한 학생이 있어도 굉장한 학생이다. 이제 사람2를 보자. 이제 사람2부터는 (정렬을 했으므로) 항상 두번째 시험에서 자기보다 잘한 사람이 1명 이상 있다. 굉장한 학생은 자신보다 세 시험 성적이 모두 좋은 사람이 없어야 하는데, 사람2부터는 두번째 시험에서 자신보다 잘 본 사람이 있다. 그리고 정렬했기 때문에 두번째 시험에서 자신보다 잘 본 사람들은 앞에 존재하고, 그 사람들이 첫번째와 세번째 시험에서도 자신보다 성적이 좋다면 그 사람은 굉장한 학생이 될 수 없지만, 첫번째 시험과 세번째 시험 둘 중 하나에서라도 자신이 성적이 제일 좋다면(자신보다 성적이 좋은 사람이 없다면) 그 학생은 굉장한 학생이 될 것이다.
많이 헷갈린다. 지금 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 때문에 항상 자신의 앞사람들은 자신보다 두번째 시험은 잘 본 사람들이고, 이제 그 사람들의 첫번째 시험과 세번째 시험의 성적이 자신보다 좋아야 자신은 굉장한 학생이 될 수 없는 것이다. 두번째 시험을 자신보다 못 본 사람들은 첫번째 시험과 세번째 시험 성적이 아무리 좋아도 볼 필요가 없다. 세 시험에서 모두 자신보다 성적이 좋은 사람이 한 사람이라도 있는지 봐야하고 만약 있다면 자신은 굉장한 학생이 아니게 된다.
그래서 두번째 시험을 기준으로 정렬하고 나서는 두번째 시험에서 자신보다 앞에 있는 사람에 대해서 그 사람들의 첫번째, 세번째 시험 성적을 보면되고,여기서 첫번째 시험 성적 중 가장 좋은 성적과 자신의 첫번째 성적을 비교하고 , 세번째 시험 성적 중 가장 좋은 성적과 자신의 세번째 성적을 비교해서 첫번째, 세번째 모두 자신의 성적보다 좋으면 그 사람은 굉장한 학생이 될 수 없고, 그 중 하나라도 자신의 성적보다 안 좋다면 그 사람은 굉장한 학생이 된다! 왜냐하면 각 성적 중 가장 좋은 성적을 가져왔기 때문에 그 가장 좋은 성적이 자신의 성적보다 좋지 않다면 자신이 그 사람들 모두보다 성적이 더 좋은 것임을 바로 알 수 있기 때문이다. 즉 그 중에 자신보다 세 시험 모두 성적이 좋은 사람이 한 사람도 없다는 것을 바로 알 수 있기 때문이다.
그래서 구간의 최소값을 빠르게 구할 수 있어야 하는데, 풀이를 좀 더 보니 내 방법에서 좀 더 나아가 segment tree를 이용해야 하는 것 같다. 하지만 일단 n제한이 50만이니까 O(N)만에누적 최소값을 계산해두고(첫번째 부터 n번째 까지의 최소값이 필요하므로) 사용하면 될 것 같다. 일단 내가 생각한대로 풀어봐야겠다.
근데 내 방법으로 계속 틀리길래... 계속 고민하고 풀이를 찾아 읽어봤지만 도무지 알 수가 없던 차에
5
1 2 3 4 5
5 4 3 2 1
1 2 3 5 4
라는 예제를 가지고 백준님의 코드와 내 코드의 실행 결과를 비교해 봤더니 달랐다. 감사합니다... 바로 찾다니 그리고 저 예제로 생각해보고 내 풀이의 문제점을 알게되었다.
내가 대충 이해한 것은 맞다. 하지만 내 풀이처럼 첫번째 따로, 세번째 따로 찾게되면 한 학생의 첫번째, 세번째 점수가 아닌, 예를 들면 학생1의 첫번째 점수, 학생2의 세번째 점수와 비교하게 될 수 있다. 왜 이걸 전혀 생각 못했지... 정말 요즘 더 실력이 떨어진 것 같다... 노력하자.
그래서 이제 다시 생각해 봐야한다.... 음 이제 내가 참고했던 여러 풀이가 이해가 된다.
왜 굳이 세그먼트 트리를 쓰는지조차 이해가 잘 안됐는데, 아... 다시 정리해 보겠다.
일단 위에서 설명했던 것처럼 두번째 시험을 기준으로 성적이 좋은 순으로(오름차순) 정렬하고 첫번째와 세번째를 보는데 위에서 잘못한 것 처럼 따로 보면 안되고 한 사람 한 사람 단위로 봐야한다!! 일단 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 시작하면 자신의 앞에 있는 사람은 두번째 시험의 경우 항상 자신보다 성적이 좋다. 그리고 자신보다 뒤에 있는 사람은 두번째 시험 성적이 항상 자신보다 안 좋으므로 첫번째, 세번째 성적이 아무리 좋아도 자신보다 "대단할" 수 없다. 그래서 일단 자신보다 앞에 있는 사람들이 첫번째, 세번째 성적이 모두 자신보다 좋은 "대단한" 사람이 될 수 있는 후보들이다. 이 중에서 자신(현재 학생)보다 대단한 사람이 없다면 현재 학생이 굉장한 사람이 되는 것이다.
두번째를 정렬해서 봐야할 곳을 첫번째와 세번째 두 곳으로 줄였지만, 여전히 첫번째와 세번째 모두 현재 학생보다 성적이 좋은 것을 찾는 것이 쉽지 않다. 바로 이 때 세그먼트 트리를 써줄 것인데, 이번에는 첫번째 성적을 기준으로 정렬을 하는 효과를 내보자.
바로 첫번째 시험의 성적(등수)을 해당하는 세번째 시험 등수값의 인덱스로 지정한다. 그리고 그것으로 세그먼트 트리를 만들어서 range minimum query를 할 수 있게 하고 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간의 최소값(즉, 그 구간에 해당하는 세번째 시험의 성적중 가장 좋은 성적)을 구해서 현재 학생의 세번째 시험 성적과 비교하고 그 성적이 현재 학생의 세번째 성적보다 좋으면 현재 학생보다 "대단한" 학생이 존재하는 것이고, 만약 아니라면 "대단한" 학생이 없는 것이므로 현재 학생은 "굉장한" 학생이 된다.
엄청난 풀이다...
그리고 처음에는 segement tree를 매우 큰 값으로 초기화 해두고, 학생을 한 명씩 볼 때마다, 즉, 두번째 시험 기준으로 정렬된 순서에 따라 첫번째 성적에 해당하는 부분을 업데이트를 시켜줘야 한다. 왜냐하면 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간이여도 이미 정렬했던 두번째 시험 성적을 기준으로 볼 때, 두번째 성적이 더 좋은 성적이 아닐 수 있기 때문에 그럴 경우에는 세그먼트 트리에 실제 첫번째 성적과, 세번째 성적에 대한 정보대신 매우 큰 값이 들어가 있어서 더 "대단한"학생이 아닌 것으로 제대로 판단하게 된다.
어렵다. 내가 너무 나태해져서 머리가 잘 안 돌아가는 것 같기도 하다. 맥그리거의 말 처럼 멈추지 말고 쉬지도 말고 끊임없이 노력하자.
음 근데, 구현하면서도 문제가 좀 있었다.
일단 init을 INF로 해주는 것에서 leaf node만 INF로 해주었다던가... 또한 update를 구현할 때, update하려는 index가 구간의 범위 밖이면 그 구간의 rangeMin값을 반환해줘야 하는데, 마치 query처럼 INF를 반환해준 것... 정말 실력 부족이다...
그리고 일반 정수가 아닌 struct는 bool cmp(struct, struct)를 쓸 때, 그냥 쓰면 복사하는데 비용이 커지므로 const struct& 식으로 참조자를 사용해서 구현하자.
위의 것도 다 고쳤는데...근데 도대체 뭐에서 틀렸을까...
정말 랜덤데이터를 생성해서 여러번 시도해 봤는데도.. 틀린 경우를 찾을 수가 없어서 고민하다가 문득.. tree를 INF로 초기화해야 하는데, init함수를 그냥 for문으로 고치고 0번 노드부터 n*4-1번노드까지 무작정 INF로 초기화하고 제출했다. 그러니까 AC를 받았다.
헉... 분명 이 것은 아까 테스트를 해봤던 것이다. 혹시 제대로 안 들어가나 해서 rangeMin값이 잘 초기화 되었는지 출력해서 확인까지 해봤었는데... 뭐지...그래서 코드를 다시 봤는데..
헉...init함수 마지막줄에 rangeMin=min(leftMin, rightMin)만 해주고 return을 안하고 있다...근데 아까는 어떻게 INF값으로 초기화 된 것이지..??? 그냥 내 local환경에서만 된 것인가.. 설마 그래서 아무리 틀린케이스를 찾으려해도 못 찾았던 것인가... 아.. 의문이 하나 둘씩 풀린다. 진짜 이 문제만큼 (백준님의 정답 코드가 있음에도 불구하고, 풀이를 이해했음에도 불구하고) 틀린 이유를 찾기 힘든 적은 처음인 것 같다.
결국 init함수에서 내 실수로 인해... 제대로 초기화가 안됐고.. 계속 틀렸던 것이다.
다시 짜봐야 겠다.
이 문제를 풀게 되면서, 그리고 다시 짜보면서 init이나 update함수부분을 좀 더 잘 이해하게 된 것 같다. 아직 완벽히 이해했다고는 생각치 않지만...
그리고 bool cmp(struct, struct)에서 &(참조자)를 써야 더 빠를 것 같았는데 제출해보니 찍히는 시간상으로는 차이가 없어보인다. 그냥 int형이라면 포인터나 int형이나 크기가 비슷하니까 상관없겠지만 struct의 경우 int형이 지금 코드에서 3개라.. 12byte짜리를 복사할텐데.. 음 BOJ 가 64비트 시스템으로 바뀌고 나서 포인터가 8byte 가 되서 큰 차이가 없는 것인가... 여튼 웬만하면 const struct& 형식으로 쓰는 게 좋을 것 같다.
<참고>
http://blog.naver.com/kks227/220791986409
http://cloge.tistory.com/7
백준님 강의 자료, 코드
즉, 자신보다 세 번 다 성적이 좋은 학생이 없는 학생의 수를 구하는 문제이다. (0번, 1번, 2번 성적이 좋은 학생들의 수)
문제 분류가 '세그먼트 트리'로 되어있는데, 쉽게 떠오르지 않는다. 처음부터 세그먼트 트리로 생각하려 해서 그런가? 한 번 그냥 푼다면 어떻게 풀 것인지 생각해 봐야겠다.
갑자기 떠오른 생각이, 굉장한 학생의 수를 바로 구하는 것보다, 굉장하지 않은 학생의 수를 구해서 빼는 게 나을 것 같다.
굉장하지 않은 학생의 수는 자신보다 세 번 모두 성적이 좋은 학생이 있는 학생의 수를 구하면 된다.
집중도 안되고 딴생각만 들고... 결국 풀이를 봤는데도 잘 이해가 안된다. 어렵다.
정신 차리고 차근차근히 풀이를 정리해 보자. 독서백편 의자현. 이해될 때까지...
일단 굉장한 학생의 수를 구해야 한다. 굉장한 학생은 자신보다 세 번 모두 성적이 좋은 학생이 없어야 한다. 문제에서는 등수 순으로 주어진다.
2 5 3 8 10 7 1 6 9 4 1 2 3 4 5 6 7 8 9 10 3 8 7 10 5 4 1 2 6 9블로그도 보고, 백준님의 코드도 보고 하면서 생각도 하고 예제를 가지고 직접 써보다가 겨우 깨달았다. 정말 헷갈린다.
일단 각 학생별로 1번 학생이 세 시험에서 각각 몇등을 했는지, 2번 학생이 세 시험에서 가각 몇 등을 했는지,... n번 학생이 세 시험에서 각각 몇 등을 했는지를 기록한다.
그리고 세 개의 시험 중 하나의 시험의 등수를 기준으로 정렬한다. 여기서 많이 헷갈렸는데, 정렬해버리면 몇 번 학생이 몇 등했는지는 알 수 없다. 하지만 알 필요없다. 우리는 굉장한 학생의 수만 구하면 된다. 정렬했기 때문에 몇 번 학생인지는 몰라도 첫번째 시험에서 1등한 사람이 두번째 시험과 세번째 시험에서 몇 등을 했는지를 알 수 있다.
즉, 누군지는 몰라도 한 사람이 각 시험에서 몇 등을 했는지에 대한 정보가 하나의 시험을 기준으로 정렬되어 있다. 2번째 시험을 기준으로 정렬했다고 하고 예를 들어보겠다.
왼쪽부터 한 사람씩(한 열씩) 보면 두번째 시험에서 1등을 한 사람은 첫번째, 세번째 시험에서 각각 2등, 3등을 했다는 사실을 알 수 있다. 일단 사람1은 두번째 시험에서 1등이므로 첫번째, 세번째 시험에서 자기보다 잘한 학생이 있어도 굉장한 학생이다. 이제 사람2를 보자. 이제 사람2부터는 (정렬을 했으므로) 항상 두번째 시험에서 자기보다 잘한 사람이 1명 이상 있다. 굉장한 학생은 자신보다 세 시험 성적이 모두 좋은 사람이 없어야 하는데, 사람2부터는 두번째 시험에서 자신보다 잘 본 사람이 있다. 그리고 정렬했기 때문에 두번째 시험에서 자신보다 잘 본 사람들은 앞에 존재하고, 그 사람들이 첫번째와 세번째 시험에서도 자신보다 성적이 좋다면 그 사람은 굉장한 학생이 될 수 없지만, 첫번째 시험과 세번째 시험 둘 중 하나에서라도 자신이 성적이 제일 좋다면(자신보다 성적이 좋은 사람이 없다면) 그 학생은 굉장한 학생이 될 것이다.
많이 헷갈린다. 지금 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 때문에 항상 자신의 앞사람들은 자신보다 두번째 시험은 잘 본 사람들이고, 이제 그 사람들의 첫번째 시험과 세번째 시험의 성적이 자신보다 좋아야 자신은 굉장한 학생이 될 수 없는 것이다. 두번째 시험을 자신보다 못 본 사람들은 첫번째 시험과 세번째 시험 성적이 아무리 좋아도 볼 필요가 없다. 세 시험에서 모두 자신보다 성적이 좋은 사람이 한 사람이라도 있는지 봐야하고 만약 있다면 자신은 굉장한 학생이 아니게 된다.
그래서 두번째 시험을 기준으로 정렬하고 나서는 두번째 시험에서 자신보다 앞에 있는 사람에 대해서 그 사람들의 첫번째, 세번째 시험 성적을 보면되고,
그래서 구간의 최소값을 빠르게 구할 수 있어야 하는데, 풀이를 좀 더 보니 내 방법에서 좀 더 나아가 segment tree를 이용해야 하는 것 같다. 하지만 일단 n제한이 50만이니까 O(N)만에
근데 내 방법으로 계속 틀리길래... 계속 고민하고 풀이를 찾아 읽어봤지만 도무지 알 수가 없던 차에
5
1 2 3 4 5
5 4 3 2 1
1 2 3 5 4
라는 예제를 가지고 백준님의 코드와 내 코드의 실행 결과를 비교해 봤더니 달랐다. 감사합니다... 바로 찾다니 그리고 저 예제로 생각해보고 내 풀이의 문제점을 알게되었다.
내가 대충 이해한 것은 맞다. 하지만 내 풀이처럼 첫번째 따로, 세번째 따로 찾게되면 한 학생의 첫번째, 세번째 점수가 아닌, 예를 들면 학생1의 첫번째 점수, 학생2의 세번째 점수와 비교하게 될 수 있다. 왜 이걸 전혀 생각 못했지... 정말 요즘 더 실력이 떨어진 것 같다... 노력하자.
그래서 이제 다시 생각해 봐야한다.... 음 이제 내가 참고했던 여러 풀이가 이해가 된다.
왜 굳이 세그먼트 트리를 쓰는지조차 이해가 잘 안됐는데, 아... 다시 정리해 보겠다.
일단 위에서 설명했던 것처럼 두번째 시험을 기준으로 성적이 좋은 순으로(오름차순) 정렬하고 첫번째와 세번째를 보는데 위에서 잘못한 것 처럼 따로 보면 안되고 한 사람 한 사람 단위로 봐야한다!! 일단 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 시작하면 자신의 앞에 있는 사람은 두번째 시험의 경우 항상 자신보다 성적이 좋다. 그리고 자신보다 뒤에 있는 사람은 두번째 시험 성적이 항상 자신보다 안 좋으므로 첫번째, 세번째 성적이 아무리 좋아도 자신보다 "대단할" 수 없다. 그래서 일단 자신보다 앞에 있는 사람들이 첫번째, 세번째 성적이 모두 자신보다 좋은 "대단한" 사람이 될 수 있는 후보들이다. 이 중에서 자신(현재 학생)보다 대단한 사람이 없다면 현재 학생이 굉장한 사람이 되는 것이다.
두번째를 정렬해서 봐야할 곳을 첫번째와 세번째 두 곳으로 줄였지만, 여전히 첫번째와 세번째 모두 현재 학생보다 성적이 좋은 것을 찾는 것이 쉽지 않다. 바로 이 때 세그먼트 트리를 써줄 것인데, 이번에는 첫번째 성적을 기준으로 정렬을 하는 효과를 내보자.
바로 첫번째 시험의 성적(등수)을 해당하는 세번째 시험 등수값의 인덱스로 지정한다. 그리고 그것으로 세그먼트 트리를 만들어서 range minimum query를 할 수 있게 하고 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간의 최소값(즉, 그 구간에 해당하는 세번째 시험의 성적중 가장 좋은 성적)을 구해서 현재 학생의 세번째 시험 성적과 비교하고 그 성적이 현재 학생의 세번째 성적보다 좋으면 현재 학생보다 "대단한" 학생이 존재하는 것이고, 만약 아니라면 "대단한" 학생이 없는 것이므로 현재 학생은 "굉장한" 학생이 된다.
엄청난 풀이다...
그리고 처음에는 segement tree를 매우 큰 값으로 초기화 해두고, 학생을 한 명씩 볼 때마다, 즉, 두번째 시험 기준으로 정렬된 순서에 따라 첫번째 성적에 해당하는 부분을 업데이트를 시켜줘야 한다. 왜냐하면 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간이여도 이미 정렬했던 두번째 시험 성적을 기준으로 볼 때, 두번째 성적이 더 좋은 성적이 아닐 수 있기 때문에 그럴 경우에는 세그먼트 트리에 실제 첫번째 성적과, 세번째 성적에 대한 정보대신 매우 큰 값이 들어가 있어서 더 "대단한"학생이 아닌 것으로 제대로 판단하게 된다.
어렵다. 내가 너무 나태해져서 머리가 잘 안 돌아가는 것 같기도 하다. 맥그리거의 말 처럼 멈추지 말고 쉬지도 말고 끊임없이 노력하자.
음 근데, 구현하면서도 문제가 좀 있었다.
일단 init을 INF로 해주는 것에서 leaf node만 INF로 해주었다던가... 또한 update를 구현할 때, update하려는 index가 구간의 범위 밖이면 그 구간의 rangeMin값을 반환해줘야 하는데, 마치 query처럼 INF를 반환해준 것... 정말 실력 부족이다...
그리고 일반 정수가 아닌 struct는 bool cmp(struct, struct)를 쓸 때, 그냥 쓰면 복사하는데 비용이 커지므로 const struct& 식으로 참조자를 사용해서 구현하자.
위의 것도 다 고쳤는데...근데 도대체 뭐에서 틀렸을까...
정말 랜덤데이터를 생성해서 여러번 시도해 봤는데도.. 틀린 경우를 찾을 수가 없어서 고민하다가 문득.. tree를 INF로 초기화해야 하는데, init함수를 그냥 for문으로 고치고 0번 노드부터 n*4-1번노드까지 무작정 INF로 초기화하고 제출했다. 그러니까 AC를 받았다.
헉... 분명 이 것은 아까 테스트를 해봤던 것이다. 혹시 제대로 안 들어가나 해서 rangeMin값이 잘 초기화 되었는지 출력해서 확인까지 해봤었는데... 뭐지...그래서 코드를 다시 봤는데..
헉...init함수 마지막줄에 rangeMin=min(leftMin, rightMin)만 해주고 return을 안하고 있다...근데 아까는 어떻게 INF값으로 초기화 된 것이지..??? 그냥 내 local환경에서만 된 것인가.. 설마 그래서 아무리 틀린케이스를 찾으려해도 못 찾았던 것인가... 아.. 의문이 하나 둘씩 풀린다. 진짜 이 문제만큼 (백준님의 정답 코드가 있음에도 불구하고, 풀이를 이해했음에도 불구하고) 틀린 이유를 찾기 힘든 적은 처음인 것 같다.
결국 init함수에서 내 실수로 인해... 제대로 초기화가 안됐고.. 계속 틀렸던 것이다.
다시 짜봐야 겠다.
이 문제를 풀게 되면서, 그리고 다시 짜보면서 init이나 update함수부분을 좀 더 잘 이해하게 된 것 같다. 아직 완벽히 이해했다고는 생각치 않지만...
그리고 bool cmp(struct, struct)에서 &(참조자)를 써야 더 빠를 것 같았는데 제출해보니 찍히는 시간상으로는 차이가 없어보인다. 그냥 int형이라면 포인터나 int형이나 크기가 비슷하니까 상관없겠지만 struct의 경우 int형이 지금 코드에서 3개라.. 12byte짜리를 복사할텐데.. 음 BOJ 가 64비트 시스템으로 바뀌고 나서 포인터가 8byte 가 되서 큰 차이가 없는 것인가... 여튼 웬만하면 const struct& 형식으로 쓰는 게 좋을 것 같다.
<참고>
http://blog.naver.com/kks227/220791986409
http://cloge.tistory.com/7
백준님 강의 자료, 코드
2016년 11월 21일 월요일
BOJ 7626 직사각형
이 문제는 segment tree lazy propagation을 연습해볼 문제로 추천받은 문제인데,
아무리 생각해도... 어떻게 segment tree를 활용할지 떠오르지가 않는다.
일단 이 문제는 좌표위에 여러 직사각형들이 차례로 주어지는데, 범위는 무려 0부터 10의 9제곱까지... 그리고 이 직사각형들이 좌표평면을 덮는 면적을 구하는 문제이다. 즉 겹치든 말든 일단 좌표평면을 얼마나 덮는지 구하는 문제이다. 그리고 직사각형은 20만개가 들어온다.
일단 x좌표를 기준으로...하는 것은 메모리 초과이다.
잘 생각해보자. 세그먼트 트리는 구간합이나 구간의 최소, 최대값을 O(log N)만에 구할 수 있고, 업데이트 또한 O(log N)만에 할 수 있는 자료구조이다.
이 문제에서는 왠지 구간합을 구해야 할 것 같은데, 단순히 구간합만 구할 것이라면 굳이 세그먼트 트리와 lazy propagation을 쓸 필요가 없을 것이다.
업데이트가... 그것도 구간 업데이트가 빈번히 있을 가능성이 큰데.. 입력을 잘 보면 직사각형을 구성하는 x좌표의 구간, y좌표의 구간이 주어진다.
하지만 각 구간을 일일이 업데이트 한다고 생각해보면... 일단 범위가 너무 커서 segment tree를 만들 수 없다. 좌표 압축? 내가 좌표 압축을 해본적이 없기도 하지만... 이 문제에서는 면적을 구해야하는데, 만약 좌표 압축을 한다면 직사각형의 각 변의 길이나 넓이를 따로 기록해 둬야하나?...음...
2016년 11월 18일 금요일
BOJ 10999 구간 합 구하기 2 와 Lazy Propagation
segment tree와 lazy propagation을 이용해야 하는 문제다.
원래는 segment tree에서 update를 할 때, 하나의 수에 대해서 update를 logN만에 할 수 있었는데, 이 문제에서는 구간을 update해야 한다. 즉 (구간의 길이)*logN의 시간이 걸리는 것이다.
Range update를 O(logN)만에 할 수 있는 방법이 있다.
segment tree + lazy propagation을 활용하는 것이다.
lazy propagation을 이용하면 범위에 포함되는 트리의 leaf node까지 다 업데이트를 해주지 않는다. 일단은 그 범위를 대표하는 node까지(node의 위에 있는 노드들도)만 업데이트 한다. 그리고 lazy라는 배열에 그 node의 자식 node들에 얼마나 업데이트 해줘야 하는지 기록해놓는다. 대충 여기까지 하면 일단 O(logN)만에 구간 업데이트가 된 것이다. 엥? 그렇다면 다른 쿼리가 들어오면 어쩌려고... 다음에 업데이트한 구간에 조금이라도 관련있는(걸쳐있는) 쿼리나 업데이트가 필요할 경우, 필요한 노드들의 lazy배열을 살펴본다. 그래서 lazy배열에 얼마나 업데이트 해줘야할지 있는 기록을 보고 그 노드를 업데이트 해주고, 그 lazy배열을 0으로 만든 후 자식 노드에게 전파해준다. 이렇게 필요한 경우 lazy배열을 살펴보고 업데이트 해줘서 필요한 노드의 값만 챙기고 그 자식노드의 업데이트는 다음으로 미루는 식이다.
물론 이렇게 하면 그냥 point update할 때보다 아주 조금 더 시간이 들긴하겠지만 O(logN)이다.
특이한 점은 쿼리를 할 때도 업데이트가 진행되는 것이다. 그리고 어떤 노드의 업데이트가 진행되면 그 노드 위의 노드들의 업데이트는 원래 재귀 업데이트 방식으로 되면 된다.
달라지는 것은 필요한 것까지만 취하고, 그 아래 자식들의 업데이트를 뒤로 미뤄놓고 필요할 때만 해주거나, 필요한 걸 찾으면서 어차피 지나가는 김에 해주고 가는 식이다.
그래서 O(logN)만에 가능한 것이다.
정말 멋있는, 대단한 방법이다. 이런 방법을 어떻게 생각해 냈을까...나도 완벽히 이해한 것은 아니기 때문에 좀 더 공부해보고 직접 짜봐야겠다. 그리고 아래에 적어놓은 두 사이트의 도움을 많이 받았다.
자동차 공장 문제를 풀 때 처럼, Fenwick Tree의 range update, range query를 이용해서도 풀 수 있을 것 같은데 일단 lazy propagation을 해본 후에 도전해 보고, 거꾸로 자동차 공장 문제도 segment tree+lazy propagation을 이용해서 풀어봐야겠다.
Segment Tree + Lazy Propagation 을 공부한 곳인데, 정말... 단계별 그림과 친절한 설명과 코드로 완벽에 가깝게 설명이 돼있다. 물론 그래도 내 실력에서느느 이해하는 게 쉽지는 않았다. 이것을 이해하려면 Segment Tree에 대해서도 잘 이해해야 하고, 아래의 자료를 오랜 시간 보면서 여러번 읽어보고 해야할 것이다.
2016년 11월 17일 목요일
BOJ 13703 물벼룩의 생존 확률
수면 k센티미터 아래에 위치한 물벼룩이 1초마다 위 또는 아래로 1센티미터 이동하고 수면에 닿으면 물매암이에게 먹혀서 죽는다. n초후의 경우의 수는 2의 n제곱가지가 있을것인데, 그 중 생존할 경우의 수를 구하는 문제이다.
처음부터 생존할 경우의 수를 구하려는 것 보다 죽는 경우(수면에 도달하는 경우)의 수를 구해서 전체 경우의 수에서 빼는 것이 나아보인다.
좀 더 생각해보면 k<=n인데,
k==n인 경우는 수면 k센티미터 아래에서 시작해서 n초뒤에 수면에 도달하려면 계속 위로 올라가야 한다. k==n인 경우는 수면에 도달하는 경우의 수는 1가지이다.
k<n인 경우는 어떨까? 일단 한 번 수면에 도달하면 그 이후로는 의미가 없다. 즉, 그 이후는 볼 필요가 없다. 그 이후는 2^(남은 시간) 의 경우의 수 일 것이다. 그리고 현재 위치보다 남은 시간이 더 작으면 수면에 도달할 수 없다.
음...dp로 접근해보면, d[pos][rsec] = 현재 위치 pos, 남은 시간 rsec일 때의 수면에 도달할 수 있는 경우의 수.(벼룩이 죽는 경우의 수)
한 번 구현해 봐야겠다.
오.. AC를 받았다. 다른 분들을 보니 나처럼 죽는 경우를 전체에서 뺀 경우도 있지만 바로 생존할 경우의 수를 구한 분들이 더 많아 보인다.
처음에는 dp로 생각하기 힘들었는데, 차근 차근 적고 정리해보다 보니 운좋게 생각이 떠오른 것 같다. 감사합니다.
처음부터 생존할 경우의 수를 구하려는 것 보다 죽는 경우(수면에 도달하는 경우)의 수를 구해서 전체 경우의 수에서 빼는 것이 나아보인다.
좀 더 생각해보면 k<=n인데,
k==n인 경우는 수면 k센티미터 아래에서 시작해서 n초뒤에 수면에 도달하려면 계속 위로 올라가야 한다. k==n인 경우는 수면에 도달하는 경우의 수는 1가지이다.
k<n인 경우는 어떨까? 일단 한 번 수면에 도달하면 그 이후로는 의미가 없다. 즉, 그 이후는 볼 필요가 없다. 그 이후는 2^(남은 시간) 의 경우의 수 일 것이다. 그리고 현재 위치보다 남은 시간이 더 작으면 수면에 도달할 수 없다.
음...dp로 접근해보면, d[pos][rsec] = 현재 위치 pos, 남은 시간 rsec일 때의 수면에 도달할 수 있는 경우의 수.(벼룩이 죽는 경우의 수)
한 번 구현해 봐야겠다.
오.. AC를 받았다. 다른 분들을 보니 나처럼 죽는 경우를 전체에서 뺀 경우도 있지만 바로 생존할 경우의 수를 구한 분들이 더 많아 보인다.
처음에는 dp로 생각하기 힘들었는데, 차근 차근 적고 정리해보다 보니 운좋게 생각이 떠오른 것 같다. 감사합니다.
BOJ 13702 이상한 술집을 풀다가...
이 문제는 이분 탐색으로 풀 수 있는 문제이다.
이분 탐색으로 나눠줄 수 있는 막걸리 용량을 정해보면서 검사하고 최대가 되도록 조절해 나가면 된다.
그런데 이분 탐색을 할 때, 헷갈리는 것이, l, r중 어느 것에 정답이 들어가냐이다.
그냥 ans 변수를 따로 쓰면 쉽긴하지만, 이분 탐색을 좀 더 이해하고 싶어서(?) l, r중에 어디에 정답이 들어갈지 생각해보는 중이다.
이번에 구현할 때는 생각해보니 r에 들어가서 r을 출력했는데,
예전에 다른 문제를 풀 때는 l에 들어가는 경우가 많았는데.. 그렇다면 l에 정답이 들어가게 하려면 어떻게 해야할까? 다른 고수분의 코드를 보고 깨달은 것인데, 여러 방식이 있겠지만,
check(mid)>=k인 경우 mid가 정답일 수도 있으므로 l=mid+1을 할 게 아니라, l=mid를 해주면 된다. else에 해당하는 check(mid)<k인 경우는 mid가 답이 될 수 없으니 r=mid-1을 해줘야 한다. 그런데 이렇게 할 경우 무한루프에 빠질 수 있다. while(l<=r)이기 때문이다.
l=3, r=5이고 정답이 4라면, l=4에서 멈출것이다... mid= (4+5)/2 = 4가 되므로..
while(l<r)로 고친다해도 l=4, r=5이므로 무한 루프일 것 같은데.. 음...
다른 분의 코드를 보니 while(r-l>1) 처럼 하신 분도 있는데, 그 분은 r=mid-1이 아니라 r=mid로 하셨다.
일단 생각해보니 그냥 내 방식대로 하면서 그 때 그 때 l이냐 r이냐를 생각해서 찾거나, ans변수를 따로 사용해서 하는 것이 좋을 것 같다.
이분 탐색으로 나눠줄 수 있는 막걸리 용량을 정해보면서 검사하고 최대가 되도록 조절해 나가면 된다.
그런데 이분 탐색을 할 때, 헷갈리는 것이, l, r중 어느 것에 정답이 들어가냐이다.
그냥 ans 변수를 따로 쓰면 쉽긴하지만, 이분 탐색을 좀 더 이해하고 싶어서(?) l, r중에 어디에 정답이 들어갈지 생각해보는 중이다.
이번에 구현할 때는 생각해보니 r에 들어가서 r을 출력했는데,
예전에 다른 문제를 풀 때는 l에 들어가는 경우가 많았는데.. 그렇다면 l에 정답이 들어가게 하려면 어떻게 해야할까? 다른 고수분의 코드를 보고 깨달은 것인데, 여러 방식이 있겠지만,
check(mid)>=k인 경우 mid가 정답일 수도 있으므로 l=mid+1을 할 게 아니라, l=mid를 해주면 된다. else에 해당하는 check(mid)<k인 경우는 mid가 답이 될 수 없으니 r=mid-1을 해줘야 한다. 그런데 이렇게 할 경우 무한루프에 빠질 수 있다. while(l<=r)이기 때문이다.
l=3, r=5이고 정답이 4라면, l=4에서 멈출것이다... mid= (4+5)/2 = 4가 되므로..
while(l<r)로 고친다해도 l=4, r=5이므로 무한 루프일 것 같은데.. 음...
다른 분의 코드를 보니 while(r-l>1) 처럼 하신 분도 있는데, 그 분은 r=mid-1이 아니라 r=mid로 하셨다.
일단 생각해보니 그냥 내 방식대로 하면서 그 때 그 때 l이냐 r이냐를 생각해서 찾거나, ans변수를 따로 사용해서 하는 것이 좋을 것 같다.
BOJ 13701 중복 제거
이 문제는 N개의 정수가 주어지면, 이들 중 중복되는 것을 제거하고 주어진 순서대로 출력하는 문제인데, N은 최대 500만이고, 주어지는 정수의 크기는 최대 2^25 - 1 이다.
일단 바로 먼저 떠올리는 것이 boolean배열로 체크하는 것인데, 정수의 크기가 너무 커서 어림도 없다. 그렇다면 500만개니까 map을 쓰면 어떨까? map이 메모리를 얼마나 차지 하는지는 모르지만, 그냥 int형 배열만써도 500만개면 메모리 제한이 8MB를 초과할 것이다.
이거 참.. 그냥 int형 배열이라도 쓸 수 있으면 sorting이라고 해서 해볼텐데..(다행히 시간제한은 5초) 어떻게 해야할지 고민이다. 혹시 map으로 되는건가?
스택 오버플로우 맵 메모리 사용량 관련 사이트를 보니 int자료가 들어간 map을 쓰면 int형 배열보다 메모리를 더 많이 쓴다는 것을 알 수 있다.
맞은 사람 목록을 보니 코드가 매우 짧다... 그래서 혹시나해서 map을 썼는데 역시나 메모리 초과.
질문 게시판을 보니 https://www.acmicpc.net/board/view/10692
오.. 그래서 위의 힌트에 따라 좀 더 생각해 보기로 했다....
일단 int 형은 4byte.. boolean형도 1byte인데, 1bit면.. bit연산을 이용해야 하나...
확실히 이 숫자가 존재하는지 아닌지만 판단하면 되므로 0 or 1만 있으면 될 것 같긴한데, 어떻게 그런 자료구조를 써야할지...
일단 3000만 비트를 사용한다고 하면 대략 4MB가 든다. 오..
http://www.cplusplus.com/reference/bitset/bitset/ 을 보니 bitset의 각 요소는 1bit만 차지하고, 그래서 char보다 8배 작다고 나와있다.
사용법도 http://www.cplusplus.com/reference/bitset/bitset/operator[]/ 을 보면 배열과 비슷해 보인다...그리고 처음에는 0으로 초기화가 돼있어 보인다.
한 번 구현해 봐야겠다.
AC를 받고 다른 분들의 코드를 봤는데...bitset이 없어도 가능하다...!!! 와...!!
int형 배열은 32 bit, char형 배열은 8bit...
int형 배열을 쓴다고 할 때, 만약 어떤 수 num이 들어오면, num은 arr[num/32]의 num%32번째 비트에 기록해두면 되는 것이다!!! 아 이런 방법이.. 분명 처음 보는 방법은 아니지만.. 멋지다. 아름답다.
char형 배열을 쓴다면 num/8번째 배열의 수의 num%8번째 비트가 num에 해당하는 비트!
아 그리고 혹시 맨 끝의 비트 하나는 부호를 가리키는 비트 아니냐..니까 unsigned로 해야되지 않나 생각할 수 있는데 전혀 상관없는 것이 signed이든 unsigned이든 배열안에 저장되는(표현되는) int(또는 char)값만 달라지는 것이지 결국 비트를 사용하는 것은 똑같다.
정말 놀라운 방법이다. 구현해 봐야겠다.
AC를 받았다. 좋은 문제였다.
일단 바로 먼저 떠올리는 것이 boolean배열로 체크하는 것인데, 정수의 크기가 너무 커서 어림도 없다. 그렇다면 500만개니까 map을 쓰면 어떨까? map이 메모리를 얼마나 차지 하는지는 모르지만, 그냥 int형 배열만써도 500만개면 메모리 제한이 8MB를 초과할 것이다.
이거 참.. 그냥 int형 배열이라도 쓸 수 있으면 sorting이라고 해서 해볼텐데..(다행히 시간제한은 5초) 어떻게 해야할지 고민이다. 혹시 map으로 되는건가?
스택 오버플로우 맵 메모리 사용량 관련 사이트를 보니 int자료가 들어간 map을 쓰면 int형 배열보다 메모리를 더 많이 쓴다는 것을 알 수 있다.
맞은 사람 목록을 보니 코드가 매우 짧다... 그래서 혹시나해서 map을 썼는데 역시나 메모리 초과.
질문 게시판을 보니 https://www.acmicpc.net/board/view/10692
오.. 그래서 위의 힌트에 따라 좀 더 생각해 보기로 했다....
일단 int 형은 4byte.. boolean형도 1byte인데, 1bit면.. bit연산을 이용해야 하나...
확실히 이 숫자가 존재하는지 아닌지만 판단하면 되므로 0 or 1만 있으면 될 것 같긴한데, 어떻게 그런 자료구조를 써야할지...
일단 3000만 비트를 사용한다고 하면 대략 4MB가 든다. 오..
http://www.cplusplus.com/reference/bitset/bitset/ 을 보니 bitset의 각 요소는 1bit만 차지하고, 그래서 char보다 8배 작다고 나와있다.
사용법도 http://www.cplusplus.com/reference/bitset/bitset/operator[]/ 을 보면 배열과 비슷해 보인다...그리고 처음에는 0으로 초기화가 돼있어 보인다.
한 번 구현해 봐야겠다.
AC를 받고 다른 분들의 코드를 봤는데...bitset이 없어도 가능하다...!!! 와...!!
int형 배열은 32 bit, char형 배열은 8bit...
int형 배열을 쓴다고 할 때, 만약 어떤 수 num이 들어오면, num은 arr[num/32]의 num%32번째 비트에 기록해두면 되는 것이다!!! 아 이런 방법이.. 분명 처음 보는 방법은 아니지만.. 멋지다. 아름답다.
char형 배열을 쓴다면 num/8번째 배열의 수의 num%8번째 비트가 num에 해당하는 비트!
아 그리고 혹시 맨 끝의 비트 하나는 부호를 가리키는 비트 아니냐..니까 unsigned로 해야되지 않나 생각할 수 있는데 전혀 상관없는 것이 signed이든 unsigned이든 배열안에 저장되는(표현되는) int(또는 char)값만 달라지는 것이지 결국 비트를 사용하는 것은 똑같다.
정말 놀라운 방법이다. 구현해 봐야겠다.
AC를 받았다. 좋은 문제였다.
2016년 11월 16일 수요일
BOJ 12874 괄호 문자열
"(" 와 ")" 로만 이루어진 문자열이 주어지면 그 문자열의 부분 문자열(연속될 필요 없음, 문자열에서 일부 문자를 지워서 만들 수 있는 문자열) 중에서 서로 다른 올바른 괄호 문자열의 개수를 구하는 문제이다.
백준님의 풀이를 봤다.
그래도 어렵다. 이해가 잘 안된다.
겨우겨우 이해한 것을 정리해 보겠다.
올바른 괄호 문자열을 찾긴 해야하는데, 그 중에서 중복되지 않는 즉 서로 다른 것들의 개수를 찾아야 한다.
()() 가 주어지면 여기서는 ()와 ()()로 2개이다.
일단 올바른 괄호 문자열의 최소 단위는 ()이고, 항상 "("와 ")"가 왼쪽 오른쪽에 같은 개수로 존재해야 한다. 즉, "("가 하나 있으면 ")"도 하나 있어야 한다.
어떤 것은 그리고 ()()()()나 (())(())처럼..올바른 문자열이 합쳐진 것도 올바른 문자열이다. 여튼 결국은 "("가 반드시 먼저 나와야하고, 그 이후에 같은 개수의 ")"가 필요하다.
먼저 가장 앞에 있는 "("를 찾는다. "("가 없을 때는 ")"가 아무리 많아도 의미 없는 문자열이다. "("를 찾았으면, 그 이후에 오는 가장 앞에 있는 "(", ")"을 둘 다 찾아본다.
만약 "("뒤에 ")"가 바로 오면 ()가 만들어져서 1개이다.
만약 "("뒤에 "("가 오면 뒤에 ")"가 2개 오기를 기다리게 된다. 이렇게 보면서 "("의 개수와 ")"의 개수가 같아지면 1개의 올바른 문자열을 만든 것이 된다.
"("나 ")"을 찾을 때, 가장 앞에 있는(가까운) 것부터 처리하고 계속해서 누적해가기 때문에 중복이 발생할 수 없다. ()가 한 번 만들어지면 그 이후로는 ()의 뒤에 덧붙여진 것이 만들어질 것이고 ((가 만들어지면 그 이후에도 ((뒤에 덧 붙여진 것이 만들어지므로 중복되지 않는다.
그리고 가장 앞에 있는(가까운) 것부터 처리하면서 뒤에 "("가 오는 경우, ")"가 오는 경우를 모두 보기 때문에 "("와 ")"를 최대한 많이 붙여볼 수 있어서, 즉 올바른 문자열은 뒤에 "("나 ")"가 오는 경우밖에 없고 가장 앞에 있는 것부터 처리해서 누적해 나감으로써 최대한 많이(모든 경우를) 보게 되어 모든 경우를 다 커버할 수 있다.
그래서 d[xth][open] = xth번째 문자를 볼 때(보기 시작할 때), 그 때까지 누적된 열린 괄호가 open개일 때의 서로 다른 올바른 부분 문자열의 개수.
d[xth][open] = d[next_open_xth][open+1] + d[next_close_xth][open-1]
(next_open_xth와 next_close_xth는 바로 다음에 오는 "(", ")" 의 위치)
그리고 open이 0이 되면 즉, "("와 ")"의 개수가 같아지면 count +1
구현해 보자.
구현하면서 dp구현의 편의를 위해 char str[102]로 놓고 str+1부터 채웠는데, char배열을 전역변수로 선언해놓으면 '\0' (NULL)로 초기화되는 것 같다. 그래서인지 답이 항상 0이 나왔다. 그래서 그냥 str[0]위치에 'x'를 채우고 했다.
출처 : BOJ 캠프 백준님 강의 자료 및 풀이
백준님의 풀이를 봤다.
그래도 어렵다. 이해가 잘 안된다.
겨우겨우 이해한 것을 정리해 보겠다.
올바른 괄호 문자열을 찾긴 해야하는데, 그 중에서 중복되지 않는 즉 서로 다른 것들의 개수를 찾아야 한다.
()() 가 주어지면 여기서는 ()와 ()()로 2개이다.
일단 올바른 괄호 문자열의 최소 단위는 ()이고, 항상 "("와 ")"가 왼쪽 오른쪽에 같은 개수로 존재해야 한다. 즉, "("가 하나 있으면 ")"도 하나 있어야 한다.
어떤 것은 그리고 ()()()()나 (())(())처럼..올바른 문자열이 합쳐진 것도 올바른 문자열이다. 여튼 결국은 "("가 반드시 먼저 나와야하고, 그 이후에 같은 개수의 ")"가 필요하다.
먼저 가장 앞에 있는 "("를 찾는다. "("가 없을 때는 ")"가 아무리 많아도 의미 없는 문자열이다. "("를 찾았으면, 그 이후에 오는 가장 앞에 있는 "(", ")"을 둘 다 찾아본다.
만약 "("뒤에 ")"가 바로 오면 ()가 만들어져서 1개이다.
만약 "("뒤에 "("가 오면 뒤에 ")"가 2개 오기를 기다리게 된다. 이렇게 보면서 "("의 개수와 ")"의 개수가 같아지면 1개의 올바른 문자열을 만든 것이 된다.
"("나 ")"을 찾을 때, 가장 앞에 있는(가까운) 것부터 처리하고 계속해서 누적해가기 때문에 중복이 발생할 수 없다. ()가 한 번 만들어지면 그 이후로는 ()의 뒤에 덧붙여진 것이 만들어질 것이고 ((가 만들어지면 그 이후에도 ((뒤에 덧 붙여진 것이 만들어지므로 중복되지 않는다.
그리고 가장 앞에 있는(가까운) 것부터 처리하면서 뒤에 "("가 오는 경우, ")"가 오는 경우를 모두 보기 때문에 "("와 ")"를 최대한 많이 붙여볼 수 있어서, 즉 올바른 문자열은 뒤에 "("나 ")"가 오는 경우밖에 없고 가장 앞에 있는 것부터 처리해서 누적해 나감으로써 최대한 많이(모든 경우를) 보게 되어 모든 경우를 다 커버할 수 있다.
그래서 d[xth][open] = xth번째 문자를 볼 때(보기 시작할 때), 그 때까지 누적된 열린 괄호가 open개일 때의 서로 다른 올바른 부분 문자열의 개수.
d[xth][open] = d[next_open_xth][open+1] + d[next_close_xth][open-1]
(next_open_xth와 next_close_xth는 바로 다음에 오는 "(", ")" 의 위치)
그리고 open이 0이 되면 즉, "("와 ")"의 개수가 같아지면 count +1
구현해 보자.
구현하면서 dp구현의 편의를 위해 char str[102]로 놓고 str+1부터 채웠는데, char배열을 전역변수로 선언해놓으면 '\0' (NULL)로 초기화되는 것 같다. 그래서인지 답이 항상 0이 나왔다. 그래서 그냥 str[0]위치에 'x'를 채우고 했다.
출처 : BOJ 캠프 백준님 강의 자료 및 풀이
2016년 11월 15일 화요일
코드 그라운드 Rectangles문제를 풀면서...
음 이 문제는 종만북의 트리단원에 나와있는 요새라는 문제처럼 풀려고 했다.
먼저 여유있게 가장 큰 네모로 둘러싸고 그 네모를 root로 하는 트리를 만들되, 어떤 부모 노드의 자식이 되려면 자식 네모가 부모 네모가 둘러싼 다른 네모들에 포함되지 않고, 부모 네모에 포함될 경우 부모 노드의 자식으로 해서... 트리를 만들면 만들어진다.
처음에는 양방향으로 트리를 만들다 보니... 원래 종만북의 문제나 BOJ 어린왕자 문제같은 경우는 양방향으로 만들어도 괜찮은 것이, 원끼리 겹치는 것이 없기 때문에 한 노드는 부모를 하나만 가지는데, 이 문제의 경우 겹치는 것이 있어서 한 노드가 부모를 여러개 가질 수 있다. 그래서 양방향으로 하면 런타임 에러를 받는 것 같다. 그래서 부모가 자식만 가리키도록 트리를 만들었더니 런타임 에러는 안나고 TLE를 받았다. 아 그리고 참고로 부모가 자식만 가리키게 단방향으로 해도 이 문제는 트리를 만들고 트리의 높이를 구하면 되는 문제이기 때문에 괜찮다.
시간초과... 일단 k가 50개 이하일 때, 즉 사각형이 50개 이하로 입력으로 들어올 때는 통과하는데, 그보다 큰 데이터에 대해서는 시간초과였다.
그래서 풀이도 좀 찾아보고, 공유된 코드를 봤다. 대부분 dp로 풀었는데, 공유된 코드를 보니, 굳이 트리를 만들 필요가 없었다는 걸 깨달았다. 난 종만북의 코드처럼 트리를 만들고, 트리를 탐색했는데, 그냥 트리를 만드는 과정에서 높이를 구하면 된다...(종만북에도 그런 말이 있었는데, 그 때는 이해를 못했지만 지금 깨달았다...) 그래서 그렇게 했는데 역시 시간초과... 근데 내가 높이를 구하는 과정도 결국은 dp랑 비슷해 보였다. 아니 정확히 말하면 높이를 구할 때, dp를 쓰면 더 빨라질 것 같았다. 음 근데 나는 dp랑은 좀 다른 것이, 어떤 노드의 자식이 될 수 있는 노드만 O(n)만큼 시간을 들여서 선별하기 때문에 괜찮지 않을까...(dp로 하는 경우 직계자식이 될 수 있는 경우만 보는 것이 아니라 모든 경우를 다 본다) 하고 생각했지만...
아까 위에서 말했듯이, 내 방식대로 하면 트리가 만들어짐에도 그렇게 느린 이유는 바로 겹치는 사각형들이 있고 그 겹친 사각형들에 공통으로 포함된 사각형들이 존재해서 서로 다른 노드가 같은 노드를 자식으로 가질 수 있게되고 트리의 노드 개수가 k개가 아니라 훨씬 커질 수 있는 것이다... 결국 내 방식대로 하더라도 memoization을 이용하는 게 도움이 된다.
그래서 memoization을 적용해봤는데, 그래도 시간초과...
근데 시간복잡도를 계산해보면 난 직계자식인지 아닌지 판단하기 위해 isChild함수를 호출해서 O(n)이긴 하지만 좀 복잡하게 확인하는데 결국 O(n)이고 모든 노드에 대해 isChild함수를 호출하다 보니 d배열의 크기는 n이고.. 그러니까 결국 O(n세제곱)의 시간복잡도가 되는 것이었다...!!! 헉...
그렇다. memoization을 쓸것이므로 포함되는지만 살펴보는 enclose함수만 써주면 O(n제곱)만에 가능하다... 결국 어쩌다 보니 공유코드에 있는 분들의 코드와 똑같은 코드가 되어가고 있었다. 조금 다른 점이라면 난 매우 큰 네모를 만들어서 root로 놓고 거기서부터 시작해서 좀 편하게 한 것 정도...?..
그런데 또 시간초과.. 혹시나 해서 max를 없애고 그냥 < 비교를 통해 최대값을 갱신해봤는데, 아슬아슬하게 통과했다... 아 STL이 느리네... 음 혹시나 해서 enclose함수를 지우고 그냥 그 안의 내용을 직접 if문에 옮겼더니 0.1초 정도 더 빨라졌다.. 여유있게 통과.. 아...
enclose함수에 parameter가 복사되고 그러느라.. 시간이 좀 더 걸린건가..
어쨌든 공유코드를 보고 맞긴 맞았는데... 나름 깨달음을 얻게해준 문제였다.
이 문제는 종만북 처럼 트리의 지름을 구하는 문제가 아니기 때문에.. 굳이 트리를 쓸 필요도 없을 뿐더러, 특히 겹치는 부분이 나오기 때문에.. 트리를 만들더라도 노드의 수가 매우 늘어나서 시간초과가 난다!! 그래서 memoization을 이용해야 하고 O(n제곱)으로 구현할 수 있다.
그리고 좀 뒷통수 맞은 기분이기 한데 dp로 보면 별거 아닌 것이..
d[parent]= parent사각형부터 시작해서 겹치지 않고 포함되는 사각형의 개수 라고 하면,
d[parent]= MAX(d[child]+1) 이 될 것이다. child는 parent에 완전히 포함되는 사각형일 것이고... child사각형이 포함하는 사각형은 결국 parent사각형에도 포함될 것이므로...
아 생각도 못했었는데...여튼 공부가 많이 된 좋은 문제였다.
먼저 여유있게 가장 큰 네모로 둘러싸고 그 네모를 root로 하는 트리를 만들되, 어떤 부모 노드의 자식이 되려면 자식 네모가 부모 네모가 둘러싼 다른 네모들에 포함되지 않고, 부모 네모에 포함될 경우 부모 노드의 자식으로 해서... 트리를 만들면 만들어진다.
처음에는 양방향으로 트리를 만들다 보니... 원래 종만북의 문제나 BOJ 어린왕자 문제같은 경우는 양방향으로 만들어도 괜찮은 것이, 원끼리 겹치는 것이 없기 때문에 한 노드는 부모를 하나만 가지는데, 이 문제의 경우 겹치는 것이 있어서 한 노드가 부모를 여러개 가질 수 있다. 그래서 양방향으로 하면 런타임 에러를 받는 것 같다. 그래서 부모가 자식만 가리키도록 트리를 만들었더니 런타임 에러는 안나고 TLE를 받았다. 아 그리고 참고로 부모가 자식만 가리키게 단방향으로 해도 이 문제는 트리를 만들고 트리의 높이를 구하면 되는 문제이기 때문에 괜찮다.
시간초과... 일단 k가 50개 이하일 때, 즉 사각형이 50개 이하로 입력으로 들어올 때는 통과하는데, 그보다 큰 데이터에 대해서는 시간초과였다.
그래서 풀이도 좀 찾아보고, 공유된 코드를 봤다. 대부분 dp로 풀었는데, 공유된 코드를 보니, 굳이 트리를 만들 필요가 없었다는 걸 깨달았다. 난 종만북의 코드처럼 트리를 만들고, 트리를 탐색했는데, 그냥 트리를 만드는 과정에서 높이를 구하면 된다...(종만북에도 그런 말이 있었는데, 그 때는 이해를 못했지만 지금 깨달았다...) 그래서 그렇게 했는데 역시 시간초과... 근데 내가 높이를 구하는 과정도 결국은 dp랑 비슷해 보였다. 아니 정확히 말하면 높이를 구할 때, dp를 쓰면 더 빨라질 것 같았다. 음 근데 나는 dp랑은 좀 다른 것이, 어떤 노드의 자식이 될 수 있는 노드만 O(n)만큼 시간을 들여서 선별하기 때문에 괜찮지 않을까...(dp로 하는 경우 직계자식이 될 수 있는 경우만 보는 것이 아니라 모든 경우를 다 본다) 하고 생각했지만...
아까 위에서 말했듯이, 내 방식대로 하면 트리가 만들어짐에도 그렇게 느린 이유는 바로 겹치는 사각형들이 있고 그 겹친 사각형들에 공통으로 포함된 사각형들이 존재해서 서로 다른 노드가 같은 노드를 자식으로 가질 수 있게되고 트리의 노드 개수가 k개가 아니라 훨씬 커질 수 있는 것이다... 결국 내 방식대로 하더라도 memoization을 이용하는 게 도움이 된다.
그래서 memoization을 적용해봤는데, 그래도 시간초과...
근데 시간복잡도를 계산해보면 난 직계자식인지 아닌지 판단하기 위해 isChild함수를 호출해서 O(n)이긴 하지만 좀 복잡하게 확인하는데 결국 O(n)이고 모든 노드에 대해 isChild함수를 호출하다 보니 d배열의 크기는 n이고.. 그러니까 결국 O(n세제곱)의 시간복잡도가 되는 것이었다...!!! 헉...
그렇다. memoization을 쓸것이므로 포함되는지만 살펴보는 enclose함수만 써주면 O(n제곱)만에 가능하다... 결국 어쩌다 보니 공유코드에 있는 분들의 코드와 똑같은 코드가 되어가고 있었다. 조금 다른 점이라면 난 매우 큰 네모를 만들어서 root로 놓고 거기서부터 시작해서 좀 편하게 한 것 정도...?..
그런데 또 시간초과.. 혹시나 해서 max를 없애고 그냥 < 비교를 통해 최대값을 갱신해봤는데, 아슬아슬하게 통과했다... 아 STL이 느리네... 음 혹시나 해서 enclose함수를 지우고 그냥 그 안의 내용을 직접 if문에 옮겼더니 0.1초 정도 더 빨라졌다.. 여유있게 통과.. 아...
enclose함수에 parameter가 복사되고 그러느라.. 시간이 좀 더 걸린건가..
어쨌든 공유코드를 보고 맞긴 맞았는데... 나름 깨달음을 얻게해준 문제였다.
이 문제는 종만북 처럼 트리의 지름을 구하는 문제가 아니기 때문에.. 굳이 트리를 쓸 필요도 없을 뿐더러, 특히 겹치는 부분이 나오기 때문에.. 트리를 만들더라도 노드의 수가 매우 늘어나서 시간초과가 난다!! 그래서 memoization을 이용해야 하고 O(n제곱)으로 구현할 수 있다.
그리고 좀 뒷통수 맞은 기분이기 한데 dp로 보면 별거 아닌 것이..
d[parent]= parent사각형부터 시작해서 겹치지 않고 포함되는 사각형의 개수 라고 하면,
d[parent]= MAX(d[child]+1) 이 될 것이다. child는 parent에 완전히 포함되는 사각형일 것이고... child사각형이 포함하는 사각형은 결국 parent사각형에도 포함될 것이므로...
아 생각도 못했었는데...여튼 공부가 많이 된 좋은 문제였다.
Baekjoon Online Judge Blog(백준 온라인 저지 블로그) 피보나치 수 특집
https://www.acmicpc.net/blog/view/28
위의 링크에 나와있는 Baekjoon Online Judge Blog의 피보나치 수를 구하는 여러가지 방법에 대해 공부해 보겠다.
BOJ 2749 피보나치 수 3 부터 좀 어렵다.
수가 매우 크지만 다행히 피보나치 수를 M으로 나눈 나머지를 구하는 것인데, 왜 다행이냐면 피보나치 수의 특성 상 피보나치 수를 M으로 나눈 나머지들은 주기를 가지게 된다. 일정 주기로 똑같은 나머지가 반복된다는 것이다. 이 것을 피사노 주기(Pisano Period)라고 한다.
BOJ Blog의 백준님 설명을 보면 피사노 주기를 구하는 공식도 소개 되어있는데, 나는 한 번 직접 주기를 구해서 풀어보고자 한다. 음 근데 직접 주기를 어떻게 구할지 모르겠다...
일단 피사노 주기를 구하는 공식으로 풀어야 겠다. 그리고 BOJ 9471 피사노 주기 문제도 있는데 이 문제도 어려운 것 같다... 일단 BOJ 9471 피사노 주기 문제부터 공부해야겠다.
BOJ 9471을 통해서 피사노 주기 구하는 방법을 알아내고 따로 정리해 놨다.
이제 BOJ 2749 피보나치 수 3 을 풀어야 겠다.
좀 헷갈리는 부분이 이 문제에서 피보나치 수가 0, 1, .. 이렇게 시작한다는 것이고 0번째 피보나치 수부터 시작한다. 그렇기 때문에 n번째 피보나치 수를 구할 때 n을 주기로 나눈 값을 pp라고 하면 0번째 수 부터 시작해서 pp번째 뒤에 있는 수로 생각하면 될 것 같다...
아 그리고 이 문제는 행렬을 이용해서도 풀 수 있다고 한다. 나중에 풀어 봐야겠다.
다음 문제는 BOJ 11444 피보나치 수 6 이다.
이 문제는 앞의 문제와 달리 무려 10억7로 나머지 연산을 해야하는데, 이 경우 피사노 주기가 매우 커지니까 피사노 주기로는 시간 내에 풀기 힘들어 보인다.(현재 내 역량으로 보기에는 그렇다..) 백준님의 설명에는 행렬을 이용한 방법으로 풀어야 한다고 나와있다.
1629번 곱셈문제를 풀었다면,
바로 위의 식을 정리해 아래의 식으로만 나타낼 수 있으면 행렬 제곱을 빠르게 계산해서 풀 수 있다. 무려 O(logN)만에... 곱셈을 빠르게 하는 것도 엄청나지만 이 피보나치 수열을 이렇게 행렬로 나타낼 생각을 했다는 것도 대단한 것 같다.
근데 첫번째 식은 이해가 되는데..(그냥 피보나치 수열 식을 옮겨 놓은 것이므로) 그 식을 정리해 아래와 같이 나타낼 수 있는지 이해를 못했었다. 그래서
이 블로그를 좀 참조 했다. 저 블로그에 나와있는 그대로 한 것은 아니고 좀 보면서 도움을 받았는데, 나는 피보나치 수를 행렬로 나타낸 식을 정리해 아래와 같이 나타내는 것에 집중해서 위의 식을 1번식, 그 아래의 식을 2번식이라고 하면 1번식의 양변에 (1 1 1 0)의 역행렬을 곱해보는 방식으로 그 블로그의 2번식 유도 과정을 따라가다보니 정말 역행렬을 이리저리 잘 곱해주면서 조작해 보면 2번식이 나옴을 알 수 있다.
그리고 이제 이 문제의 핵심중 하나는 행렬 곱셈을 구현하는 것인데, 내가 생각한 건 아니지만 백준님의 코드를 보고 이해했다.
그리고 마지막으로 소개된 방법은 피보나치 수를 더 작은 피보나치 수의 합 또는 곱으로 구할 수 있음을 이용해서 memoization을 이용하는 방법이다.
근데 n이 매우 큰데, memoization할 배열을 할당할 때 메모리 초과가 나지 않을까? 라는 걱정이 드는데, 백준님의 코드를 보면 dp처럼 배열을 미리 잡는 것이 아니라, map을 이용해서 memoization을 구현하고 있다. map으로 구현한 것과, 메모리 초과가 나지 않는다고 할 때, 아마 n번째 피보나치 수를 구할 때, d[1]부터 d[n]까지 모두 필요한 것이 아닌 것 같다. 위의 식을 보면 짝수든 홀수든 간에 대략 자기 자신의 2분의 1에 해당하는 값들의 합 또는 곱으로 구할 수 있으므로, 대충 짐작해보면 d[n]을 알기 위해 d[n/2]가 필요한 셈이므로 시간 복잡도 뿐 아니라 memoization에 쓰이는 배열 역시 O(logN)만큼만 필요할 것이다.
그래서 map으로 구현한 것이고, 메모리 초과가 나지 않을 것이다.
참 멋진 풀이다. 그리고 map을 사용해서 memoization을 이렇게 재귀로 구현하므로서 필요한 것만 쓰게 되고 결국 시간과 메모리에서 문제 없이 된다는 것이 매우 멋지다.
일단 위의 식이 맞는지 이해한 후에 memoization으로 구현해 봐야겠다. 음 근데 위의 식이 왜 저렇게 나오는지.. 아니 맞는지조차 증명을 못하겠다... 검색해봐도 잘 나오지 않는 것 같고... 그래서 일단 구현만 해보고 나중에 정수론 같은 것도 공부해 봐야겠다.
참고 및 출처 :
백준 온라인 저지 블로그 - 피보나치 수를 구하는 여러가지 방법
어떤 수학(정수론)관련 블로그
위의 링크에 나와있는 Baekjoon Online Judge Blog의 피보나치 수를 구하는 여러가지 방법에 대해 공부해 보겠다.
BOJ 2749 피보나치 수 3 부터 좀 어렵다.
수가 매우 크지만 다행히 피보나치 수를 M으로 나눈 나머지를 구하는 것인데, 왜 다행이냐면 피보나치 수의 특성 상 피보나치 수를 M으로 나눈 나머지들은 주기를 가지게 된다. 일정 주기로 똑같은 나머지가 반복된다는 것이다. 이 것을 피사노 주기(Pisano Period)라고 한다.
BOJ Blog의 백준님 설명을 보면 피사노 주기를 구하는 공식도 소개 되어있는데, 나는 한 번 직접 주기를 구해서 풀어보고자 한다. 음 근데 직접 주기를 어떻게 구할지 모르겠다...
일단 피사노 주기를 구하는 공식으로 풀어야 겠다. 그리고 BOJ 9471 피사노 주기 문제도 있는데 이 문제도 어려운 것 같다... 일단 BOJ 9471 피사노 주기 문제부터 공부해야겠다.
BOJ 9471을 통해서 피사노 주기 구하는 방법을 알아내고 따로 정리해 놨다.
이제 BOJ 2749 피보나치 수 3 을 풀어야 겠다.
좀 헷갈리는 부분이 이 문제에서 피보나치 수가 0, 1, .. 이렇게 시작한다는 것이고 0번째 피보나치 수부터 시작한다. 그렇기 때문에 n번째 피보나치 수를 구할 때 n을 주기로 나눈 값을 pp라고 하면 0번째 수 부터 시작해서 pp번째 뒤에 있는 수로 생각하면 될 것 같다...
아 그리고 이 문제는 행렬을 이용해서도 풀 수 있다고 한다. 나중에 풀어 봐야겠다.
다음 문제는 BOJ 11444 피보나치 수 6 이다.
이 문제는 앞의 문제와 달리 무려 10억7로 나머지 연산을 해야하는데, 이 경우 피사노 주기가 매우 커지니까 피사노 주기로는 시간 내에 풀기 힘들어 보인다.(현재 내 역량으로 보기에는 그렇다..) 백준님의 설명에는 행렬을 이용한 방법으로 풀어야 한다고 나와있다.
1629번 곱셈문제를 풀었다면,
바로 위의 식을 정리해 아래의 식으로만 나타낼 수 있으면 행렬 제곱을 빠르게 계산해서 풀 수 있다. 무려 O(logN)만에... 곱셈을 빠르게 하는 것도 엄청나지만 이 피보나치 수열을 이렇게 행렬로 나타낼 생각을 했다는 것도 대단한 것 같다.
근데 첫번째 식은 이해가 되는데..(그냥 피보나치 수열 식을 옮겨 놓은 것이므로) 그 식을 정리해 아래와 같이 나타낼 수 있는지 이해를 못했었다. 그래서
이 블로그를 좀 참조 했다. 저 블로그에 나와있는 그대로 한 것은 아니고 좀 보면서 도움을 받았는데, 나는 피보나치 수를 행렬로 나타낸 식을 정리해 아래와 같이 나타내는 것에 집중해서 위의 식을 1번식, 그 아래의 식을 2번식이라고 하면 1번식의 양변에 (1 1 1 0)의 역행렬을 곱해보는 방식으로 그 블로그의 2번식 유도 과정을 따라가다보니 정말 역행렬을 이리저리 잘 곱해주면서 조작해 보면 2번식이 나옴을 알 수 있다.
그리고 이제 이 문제의 핵심중 하나는 행렬 곱셈을 구현하는 것인데, 내가 생각한 건 아니지만 백준님의 코드를 보고 이해했다.
그리고 마지막으로 소개된 방법은 피보나치 수를 더 작은 피보나치 수의 합 또는 곱으로 구할 수 있음을 이용해서 memoization을 이용하는 방법이다.
근데 n이 매우 큰데, memoization할 배열을 할당할 때 메모리 초과가 나지 않을까? 라는 걱정이 드는데, 백준님의 코드를 보면 dp처럼 배열을 미리 잡는 것이 아니라, map을 이용해서 memoization을 구현하고 있다. map으로 구현한 것과, 메모리 초과가 나지 않는다고 할 때, 아마 n번째 피보나치 수를 구할 때, d[1]부터 d[n]까지 모두 필요한 것이 아닌 것 같다. 위의 식을 보면 짝수든 홀수든 간에 대략 자기 자신의 2분의 1에 해당하는 값들의 합 또는 곱으로 구할 수 있으므로, 대충 짐작해보면 d[n]을 알기 위해 d[n/2]가 필요한 셈이므로 시간 복잡도 뿐 아니라 memoization에 쓰이는 배열 역시 O(logN)만큼만 필요할 것이다.
그래서 map으로 구현한 것이고, 메모리 초과가 나지 않을 것이다.
참 멋진 풀이다. 그리고 map을 사용해서 memoization을 이렇게 재귀로 구현하므로서 필요한 것만 쓰게 되고 결국 시간과 메모리에서 문제 없이 된다는 것이 매우 멋지다.
일단 위의 식이 맞는지 이해한 후에 memoization으로 구현해 봐야겠다. 음 근데 위의 식이 왜 저렇게 나오는지.. 아니 맞는지조차 증명을 못하겠다... 검색해봐도 잘 나오지 않는 것 같고... 그래서 일단 구현만 해보고 나중에 정수론 같은 것도 공부해 봐야겠다.
참고 및 출처 :
백준 온라인 저지 블로그 - 피보나치 수를 구하는 여러가지 방법
어떤 수학(정수론)관련 블로그
BOJ 1312 소수
a, b, n이 주어지면
a/b의 소수점 n번째 자리의 수를 구하는 문제인데, n이 매우 크기도 하고 또한 소수점 n번째 자리를 어떻게 알아내지? 라는 생각부터.. 나는 정말로 실수끼리 나눗셈을 할 생각부터 하고 있었다.
하지만 slack과 질문게시판을 통해서 놀라운(나는 생각도 못한..) 방법을 알게 되었다.
바로 a/b의 소수점 n번째 자리의 수는 a*(10의 n제곱) / b의 일의 자리수와 같다는 것!!!
그렇다 실제로 예를 들어 4를 7로 나눠서 나오는 소수점 n번째 자리의 수를 구해내는 과정이나, 4의 뒤에 0을 n개 붙여서 7로 나누는 과정이나 똑같다!! 아... 난 이런 것도 생각못하고...
자... 하지만 문제가 있다. 그래도 n이 너무 크다는 것이다. 어떻게 해야할까? 또 전혀 생각도 안나고 해서 질문게시판을 봤는데...
etaehyun4님의 이런 엄청난 답변이 있었다. 좀 생각해보니 아하..!!
4의 뒤에 0을 n개 붙인 수는 너무 커서 만들 수 없다. 하지만 4의 뒤에 0을 n개 붙인 수를 7로 나눠서 그 몫의 일의 자리수를 구하는 것은 꼭 4의 뒤에 0을 n개 붙인 수가 있지 않아도 된다. 위의 힌트대로 생각해보면 그 나눗셈 과정을 구현을 하면 되는 것이다. 4부터 시작해서 0을 하나씩 붙이면서 7로 나누고 그 나머지에 또 0을 붙여서(10을 곱해서) 7로 나눠주고... 이런 식으로 n번 반복하면 답을 구할 수 있을 것이다!
와... 멋있다. 그와 동시에 정말 내 실력의 부족함을 느꼈고.. 생각을 잘 못하면 생각하는 연습도 해보고 무엇보다 많은 문제를 끊임없이 풀어보면서 실력을 키워야겠다.
a/b의 소수점 n번째 자리의 수를 구하는 문제인데, n이 매우 크기도 하고 또한 소수점 n번째 자리를 어떻게 알아내지? 라는 생각부터.. 나는 정말로 실수끼리 나눗셈을 할 생각부터 하고 있었다.
하지만 slack과 질문게시판을 통해서 놀라운(나는 생각도 못한..) 방법을 알게 되었다.
바로 a/b의 소수점 n번째 자리의 수는 a*(10의 n제곱) / b의 일의 자리수와 같다는 것!!!
그렇다 실제로 예를 들어 4를 7로 나눠서 나오는 소수점 n번째 자리의 수를 구해내는 과정이나, 4의 뒤에 0을 n개 붙여서 7로 나누는 과정이나 똑같다!! 아... 난 이런 것도 생각못하고...
자... 하지만 문제가 있다. 그래도 n이 너무 크다는 것이다. 어떻게 해야할까? 또 전혀 생각도 안나고 해서 질문게시판을 봤는데...
etaehyun4님의 이런 엄청난 답변이 있었다. 좀 생각해보니 아하..!!
4의 뒤에 0을 n개 붙인 수는 너무 커서 만들 수 없다. 하지만 4의 뒤에 0을 n개 붙인 수를 7로 나눠서 그 몫의 일의 자리수를 구하는 것은 꼭 4의 뒤에 0을 n개 붙인 수가 있지 않아도 된다. 위의 힌트대로 생각해보면 그 나눗셈 과정을 구현을 하면 되는 것이다. 4부터 시작해서 0을 하나씩 붙이면서 7로 나누고 그 나머지에 또 0을 붙여서(10을 곱해서) 7로 나눠주고... 이런 식으로 n번 반복하면 답을 구할 수 있을 것이다!
와... 멋있다. 그와 동시에 정말 내 실력의 부족함을 느꼈고.. 생각을 잘 못하면 생각하는 연습도 해보고 무엇보다 많은 문제를 끊임없이 풀어보면서 실력을 키워야겠다.
2016년 11월 14일 월요일
BOJ 1004 어린 왕자
이 문제는 알고스팟에서 봤던 문제와 비슷해서 그런지 내가 떠올린 풀이는 주어진 원들을 트리로 만들고 (주어진 두 점도 반지름의 길이가 0인 원으로 만들어 트리에 포함) 트리에서 그 두 원사이의 거리를 구하는 것인데... 이게 분명 쉬운 구현은 아닐텐데 (물론 내 기준으로..) 엄청나게 많은 사람이 풀었길래 맞은 사람 목록을 봤더니 코드가 매우 짧다...
분명 다른 풀이가 있을 것이다....
그 전에 내가 생각한 방법으로 풀어보자. 아.. 막상 풀려고 하니 문제가 되는 것이 root에 해당하는 원을 찾아야하는 것과, 또한 알고스팟 문제 처럼 하나의 트리로 이루어진 것이 아니라 이 문제에서는 여러 개의 트리가 나올 수 있어서 저 방법으로는 쉽지 않을 것 같다.
정말 이제 미련을 버리고 새로운 방법을 생각해 봐야겠다.... 가 아니라 다시 생각해보니 위의 방법으로도 할 수 있다. 한 개의 트리가 나오게 하면 된다. 바로 가장 큰 원으로 전체를 둘러싸면 되는 것이다. 일단 이 방법으로 풀어봐야지...
풀면서 예제조차 제대로 안 나와서 막막했는데, 종만북의 코드를 보니 내가 잘못한 부분이 있었다. 주어진 원들을 트리로 변환할 때, 어떤 원이 어떤 원의 자식이 되는지 판별하는 함수를 그냥 포함되면 무조건 자식으로 판별해서 무분별하게 이어지게 되고.. 그러다보니 dfs를 돌릴 때, 무한루프에 빠지게 되었다.
고쳐서 제출했는데 틀렸다... 반례를 찾기도 힘들고... 그래서 질문게시판도 보고 하다가.. 이 방법말고 좀 더 쉬운 방법으로 구현해 보고 AC를 받은 후에 랜덤 데이터를 돌려서 틀린 이유를 찾아내야 겠다.
방법은 그리 어렵지 않다. (내 스스로 생각한 건 아니지만...)
입력으로 들어오는 원들에 시작점과 끝점이 포함되는지 살펴보면서 포함되면 시작점, 끝점에 대해 각각 카운트를 해주는데, 만약 두 점다 포함된다면 카운트를 하지 않고, 최종적으로 시작점 카운트와 끝점 카운트를 더해주면 답이 될 것같다... AC를 받았다.
이제 원래 코드의 틀린 케이스를 찾아보자...
틀린케이스를 랜덤으로 생성하느라 코드도 짜고.. 이것 저것 실수도 많이하고(예를 들어 랜덤데이터는 100개인데, 배열을 10으로 잡아놔서 이상한 데이터가 생성됐다든지..) 정말 혼돈의 도가니였는데, 그 혼돈을 정리하고 계속 비교를 해봤지만.. 정말 수백번은 해본 것 같다. 그래도 계속 AC코드랑 답이 같게 나와서...진짜 지쳐서 포기할까 했지만 결국 저녁먹고 와서 또 해보다가 하나를 발견했다.
그리고 분석에 들어갔는데 수가 커서 좀 힘들었지만(수가 작으면 웬만해서는 안 나오길래.. 크게 잡았다. 원래의 문제의 범위대로..) 분석해서 이유를 알게되니 정말 허무했지만 한편으로는 왜 이 경우를 찾기가 힘들었는지 알 수 있었고, 기뻤다...일단 내가 트리로 푼 풀이가 틀린게 아니라 다른 데에 문제가 있었기 때문이다.
바로 트리를 만들 때, 이 문제에서 가장 큰 원으로 바깥을 둘러싸야 하는데, 입력으로 주어지는 모든 원을 둘러싸려면 매우 커야하고 다른 원들과 조금이라도 겹치면 안된다.
그래서 (2000, 2000)에 반지름 5000으로 잡았는데 분명 가로 세로만 봣을 때는 입력된 케이스들을 다 커버할만한 크기 같아보이지만 대각선 방향으로 보면 (-1000, 1000) 쯤에 있는 데이터를 완벽히 커버하지 못할 수 있어보였다... 그래서 얼른 (1100, 1100)에 반지름 6000으로 여유있게 해서 제출했더니.. 맞았습니다!!! AC를 받았다!!!
결국 트리를 만들어서 하는 풀이는 맞았지만 이 풀이를 위해 모든 원을 포함하는 큰 원을 설정하는 것에서 실수를...아니 전혀 생각도 못해서.. 매우 부주의했기 때문에 틀린 것이었다. 정말 생각도 못했을 뿐아니라 랜덤 데이터를 생성해도 저 범위를 넘는 데이터는 범위내에서 가장 큰 데이터가 나와야 하고, 처음에는 데이터 분석을 쉽게하려고 크기가 작은 데이터만 생성했기에... 이렇게 오랬동안 찾을 수 없었던 것이다.
어쩌면 그냥 못찾고 포기했을지도 모를 일이다. 정말 감사합니다!
힘내서 열심히 하자.
분명 다른 풀이가 있을 것이다....
그 전에 내가 생각한 방법으로 풀어보자. 아.. 막상 풀려고 하니 문제가 되는 것이 root에 해당하는 원을 찾아야하는 것과, 또한 알고스팟 문제 처럼 하나의 트리로 이루어진 것이 아니라 이 문제에서는 여러 개의 트리가 나올 수 있어서 저 방법으로는 쉽지 않을 것 같다.
정말 이제 미련을 버리고 새로운 방법을 생각해 봐야겠다.... 가 아니라 다시 생각해보니 위의 방법으로도 할 수 있다. 한 개의 트리가 나오게 하면 된다. 바로 가장 큰 원으로 전체를 둘러싸면 되는 것이다. 일단 이 방법으로 풀어봐야지...
풀면서 예제조차 제대로 안 나와서 막막했는데, 종만북의 코드를 보니 내가 잘못한 부분이 있었다. 주어진 원들을 트리로 변환할 때, 어떤 원이 어떤 원의 자식이 되는지 판별하는 함수를 그냥 포함되면 무조건 자식으로 판별해서 무분별하게 이어지게 되고.. 그러다보니 dfs를 돌릴 때, 무한루프에 빠지게 되었다.
고쳐서 제출했는데 틀렸다... 반례를 찾기도 힘들고... 그래서 질문게시판도 보고 하다가.. 이 방법말고 좀 더 쉬운 방법으로 구현해 보고 AC를 받은 후에 랜덤 데이터를 돌려서 틀린 이유를 찾아내야 겠다.
방법은 그리 어렵지 않다. (내 스스로 생각한 건 아니지만...)
입력으로 들어오는 원들에 시작점과 끝점이 포함되는지 살펴보면서 포함되면 시작점, 끝점에 대해 각각 카운트를 해주는데, 만약 두 점다 포함된다면 카운트를 하지 않고, 최종적으로 시작점 카운트와 끝점 카운트를 더해주면 답이 될 것같다... AC를 받았다.
이제 원래 코드의 틀린 케이스를 찾아보자...
틀린케이스를 랜덤으로 생성하느라 코드도 짜고.. 이것 저것 실수도 많이하고(예를 들어 랜덤데이터는 100개인데, 배열을 10으로 잡아놔서 이상한 데이터가 생성됐다든지..) 정말 혼돈의 도가니였는데, 그 혼돈을 정리하고 계속 비교를 해봤지만.. 정말 수백번은 해본 것 같다. 그래도 계속 AC코드랑 답이 같게 나와서...진짜 지쳐서 포기할까 했지만 결국 저녁먹고 와서 또 해보다가 하나를 발견했다.
그리고 분석에 들어갔는데 수가 커서 좀 힘들었지만(수가 작으면 웬만해서는 안 나오길래.. 크게 잡았다. 원래의 문제의 범위대로..) 분석해서 이유를 알게되니 정말 허무했지만 한편으로는 왜 이 경우를 찾기가 힘들었는지 알 수 있었고, 기뻤다...일단 내가 트리로 푼 풀이가 틀린게 아니라 다른 데에 문제가 있었기 때문이다.
바로 트리를 만들 때, 이 문제에서 가장 큰 원으로 바깥을 둘러싸야 하는데, 입력으로 주어지는 모든 원을 둘러싸려면 매우 커야하고 다른 원들과 조금이라도 겹치면 안된다.
그래서 (2000, 2000)에 반지름 5000으로 잡았는데 분명 가로 세로만 봣을 때는 입력된 케이스들을 다 커버할만한 크기 같아보이지만 대각선 방향으로 보면 (-1000, 1000) 쯤에 있는 데이터를 완벽히 커버하지 못할 수 있어보였다... 그래서 얼른 (1100, 1100)에 반지름 6000으로 여유있게 해서 제출했더니.. 맞았습니다!!! AC를 받았다!!!
결국 트리를 만들어서 하는 풀이는 맞았지만 이 풀이를 위해 모든 원을 포함하는 큰 원을 설정하는 것에서 실수를...아니 전혀 생각도 못해서.. 매우 부주의했기 때문에 틀린 것이었다. 정말 생각도 못했을 뿐아니라 랜덤 데이터를 생성해도 저 범위를 넘는 데이터는 범위내에서 가장 큰 데이터가 나와야 하고, 처음에는 데이터 분석을 쉽게하려고 크기가 작은 데이터만 생성했기에... 이렇게 오랬동안 찾을 수 없었던 것이다.
어쩌면 그냥 못찾고 포기했을지도 모를 일이다. 정말 감사합니다!
힘내서 열심히 하자.
2016년 11월 13일 일요일
BOJ 13998 연속합 2
-1000 이상 1000 이하의 수 n개로 이루어진 임의의 수열이 주어지고 이 중 연속된 숫자 몇 개(한 개 이상)를 선택해서 그 합을 최대로 하려고 하는데, 수열에서 수 하나를 제거할 수 있다. 이 때, 최대인 합을 구하는 문제이다.
연속합 문제와 비슷하다. 수열에서 수 하나를 제거할 수 있다는 것이 추가됐다.
연속합 문제에서는 d[n] = n번째 수를 마지막 수로 하는 연속된 숫자들의 합의 최대값
으로 놓고 n번째 수와 d[n-1]의 합이 n번째 수보다 크면 d[n]을 d[n-1]+(n번째 수)로 갱신해주는 식으로 풀었다. 만약 아니라면 d[n]은 n번째 수의 값을 유지하는 식으로...
음수도 포함돼 있어서 d[n-1]과 n번째 수의 합이 n번째 수보다 작아진다면 합하지 않고, n번째 수부터 연속된 수열을 만들어 나가는 것이 이익이다.
자, 그런데 이 문제는 수열에서 하나의 수를 제거할 수 있어서 좀 까다롭다.
n제한이 10만이라 음수를 하나씩 제거 해보고 위의 방법으로 연속된 수열의 합의 최대값을 구하는 방법은 TLE를 받을 것이다.
그렇다면 어떻게 해야할까? 제거는 하나만 할 수 있다.
바로 d[n]에서 d[n][r] = n번째 수를 볼 때, 연속된 숫자들에서 하나의 수를 r번 제거 한 경우의 합의 최대값. (r=0 or 1)
으로 놓고, d[n][0]값은 n번째 수의 값을 가지고 있다고 할 때,
d[n][0] = MAX(d[n][0], d[n-1][0]+arr[n]) //제거하지 않는 경우.
d[n][1] = MAX(d[n-1][0], d[n-1][1]+arr[n]) // 직전까지 제거하지 않은 경우 n번째 수를 제거하고, 직전까지 한 번 제거 했다면 n번째 수는 제거하지 않고 더한다.
그리고 이 것은 그냥 제거를 안 한 수열의 합과, 제거를 한 번 한 수열의 합을 나타내는 변수 2개로 나타낼 수도 있다.
int rmSum; //제거를 한 번만 한 수열의 합
int Sum; //제거를 한 번도 안 한 수열의 합
rmSum = MAX(Sum, rmSum+arr[n])
Sum = MAX(arr[n], Sum+arr[n])
그러면서 각 n에 대하여 rmSum과 Sum 중 최대값을 계속 갱신해주면 된다.
결국 위의 방법과 똑같다고 볼 수 있다.
주의해야 할 점으로 두 가지가 있다.
1. 음수로 구성되어 있을 경우 최대값이 음수가 나올 수 있다는 것.
2. 수열의 수가 한 개밖에 없을 경우, 그 값이 음수라도 선택해야 한다는 것.(문제에서 한 개이상의 수를 선택해야 한다는 조건이 있으므로)
연속합 문제와 비슷하다. 수열에서 수 하나를 제거할 수 있다는 것이 추가됐다.
연속합 문제에서는 d[n] = n번째 수를 마지막 수로 하는 연속된 숫자들의 합의 최대값
으로 놓고 n번째 수와 d[n-1]의 합이 n번째 수보다 크면 d[n]을 d[n-1]+(n번째 수)로 갱신해주는 식으로 풀었다. 만약 아니라면 d[n]은 n번째 수의 값을 유지하는 식으로...
음수도 포함돼 있어서 d[n-1]과 n번째 수의 합이 n번째 수보다 작아진다면 합하지 않고, n번째 수부터 연속된 수열을 만들어 나가는 것이 이익이다.
자, 그런데 이 문제는 수열에서 하나의 수를 제거할 수 있어서 좀 까다롭다.
n제한이 10만이라 음수를 하나씩 제거 해보고 위의 방법으로 연속된 수열의 합의 최대값을 구하는 방법은 TLE를 받을 것이다.
그렇다면 어떻게 해야할까? 제거는 하나만 할 수 있다.
바로 d[n]에서 d[n][r] = n번째 수를 볼 때, 연속된 숫자들에서 하나의 수를 r번 제거 한 경우의 합의 최대값. (r=0 or 1)
으로 놓고, d[n][0]값은 n번째 수의 값을 가지고 있다고 할 때,
d[n][0] = MAX(d[n][0], d[n-1][0]+arr[n]) //제거하지 않는 경우.
d[n][1] = MAX(d[n-1][0], d[n-1][1]+arr[n]) // 직전까지 제거하지 않은 경우 n번째 수를 제거하고, 직전까지 한 번 제거 했다면 n번째 수는 제거하지 않고 더한다.
그리고 이 것은 그냥 제거를 안 한 수열의 합과, 제거를 한 번 한 수열의 합을 나타내는 변수 2개로 나타낼 수도 있다.
int rmSum; //제거를 한 번만 한 수열의 합
int Sum; //제거를 한 번도 안 한 수열의 합
rmSum = MAX(Sum, rmSum+arr[n])
Sum = MAX(arr[n], Sum+arr[n])
그러면서 각 n에 대하여 rmSum과 Sum 중 최대값을 계속 갱신해주면 된다.
결국 위의 방법과 똑같다고 볼 수 있다.
주의해야 할 점으로 두 가지가 있다.
1. 음수로 구성되어 있을 경우 최대값이 음수가 나올 수 있다는 것.
2. 수열의 수가 한 개밖에 없을 경우, 그 값이 음수라도 선택해야 한다는 것.(문제에서 한 개이상의 수를 선택해야 한다는 조건이 있으므로)
2016년 11월 11일 금요일
BOJ 9471 피사노 주기
피보나치 수를 m으로 나눈 수들을 순서대로 나열하면 일정 주기로 반복이 된다고 한다.
그 주기를 피사노 주기(Pisano period)라고 하는데, 피보나치 수열을 구성하는 피보나 치 수들을 각각 어떤 수 m으로 나눠서 그 나머지들로 수열을 만들 때, 반복되는 부분 수열의 길이를 구하는 문제이다.
문제에 보면
바로 질문 검색의 질문과 답변과 어느 분의 블로그를 참고했다.
핵심은
(a + b) mod c = (a mod c + b mod c) mod c
피보나치 수열에서 한 수는 그 수 바로 이전의 두 수의 합으로 결정된다는 것!
일단 m으로 나눈 나머지의 주기를 구해야 하는데 어디까지가 주기일까? 피보나치 수열을 구성하는 피보나치 수는 그 수 바로 이전의 두 피보나치 수의 합으로 결정되어 나가므로 두 개의 수가 같다면 즉 문제에서 주어진 피보나치 수는 1, 1 부터 시작하므로(m으로 나눈 나머지 역시 1, 1) 1, 1, 이 나올 때부터 또 다른 주기가 시작된다고 볼 수 있다!
근데 mod m을 한 값들인데 두 개의 수가 같다고 거기서부터 또 똑같이 반복된다고 볼 수 있을까? 정말 원래 피보나치 수열을 나눈 값으로 계산해도 그렇게 나올까?
피보나치 수 X, Y, Z가 있다고 하자. Z = X+Y일 것이다.
Z mod M = (X+Y) mod M
= (X mod m + Y mod M) mod M
지금 우리가 구하는 것은 피보나치 수를 M으로 나눈 나머지들로 이루어진 수열의 주기를 구하는 것인데, 이렇게 피보나치 수 Z를 M으로 나눈 나머지는 Z를 구성하는 X+Y에서 X를 M으로 나눈 나머지와 Y를 나눈 나머지의 합을 M으로 나눈 것과 같은 것을 볼 수 있다.
즉, 직접 피보나치 수열을 계산해서 M으로 나눈 나머지를 구하는 것이나 처음부터 피보나치 수의 나머지들로 더하고 나눈 나머지를 구하는 것이나 같다는 것이므로 제대로 된 값이 나올까하는 걱정은 안 해도 된다.
그래서 이렇게 나머지들로 이루어진 수열도 1, 1, 로 시작해서 더하고 나누는 식으로 해서 계속 수열을 구해 나가다가 1, 1,을 만나면 거기서부터 또 다른 주기가 반복된다는 것을 알 수 있다.
이렇게 피보나치 수열은 앞의 두 값에 의해 하나 하나 결정되어 나가고, 위의 나머지 연산 법칙에 의하면 피보나치 수를 나눈 나머지 값을 이용해 수열을 만들어도 피보나치 수를 구해서 나눈 나머지와 같으므로, 피보나치 수를 나눈 나머지 값들로 구성된 수열을 만들어 가면서 연속된 두 값만 확인하면 주기를 쉽게 찾을 수 있는데, 나는 그냥 모든 수를 다 비교할 생각을 했으니... 음 정말 좋은 문제이다.
< 참고 및 출처 >
https://www.acmicpc.net/board/view/4501
http://redsalmon.tistory.com/5
그 주기를 피사노 주기(Pisano period)라고 하는데, 피보나치 수열을 구성하는 피보나 치 수들을 각각 어떤 수 m으로 나눠서 그 나머지들로 수열을 만들 때, 반복되는 부분 수열의 길이를 구하는 문제이다.
문제에 보면
- m > 2인 경우에 k(m)은 짝수이다.
- 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
- k(m) ≤ m2 - 1
- k(2n) = 3×2(n-1)
- k(5n) = 4×5n
- k(2×5n) = 6n
- n > 2라면, k(10n) = 15×10(n-1)
바로 질문 검색의 질문과 답변과 어느 분의 블로그를 참고했다.
핵심은
(a + b) mod c = (a mod c + b mod c) mod c
피보나치 수열에서 한 수는 그 수 바로 이전의 두 수의 합으로 결정된다는 것!
일단 m으로 나눈 나머지의 주기를 구해야 하는데 어디까지가 주기일까? 피보나치 수열을 구성하는 피보나치 수는 그 수 바로 이전의 두 피보나치 수의 합으로 결정되어 나가므로 두 개의 수가 같다면 즉 문제에서 주어진 피보나치 수는 1, 1 부터 시작하므로(m으로 나눈 나머지 역시 1, 1) 1, 1, 이 나올 때부터 또 다른 주기가 시작된다고 볼 수 있다!
근데 mod m을 한 값들인데 두 개의 수가 같다고 거기서부터 또 똑같이 반복된다고 볼 수 있을까? 정말 원래 피보나치 수열을 나눈 값으로 계산해도 그렇게 나올까?
피보나치 수 X, Y, Z가 있다고 하자. Z = X+Y일 것이다.
Z mod M = (X+Y) mod M
= (X mod m + Y mod M) mod M
지금 우리가 구하는 것은 피보나치 수를 M으로 나눈 나머지들로 이루어진 수열의 주기를 구하는 것인데, 이렇게 피보나치 수 Z를 M으로 나눈 나머지는 Z를 구성하는 X+Y에서 X를 M으로 나눈 나머지와 Y를 나눈 나머지의 합을 M으로 나눈 것과 같은 것을 볼 수 있다.
즉, 직접 피보나치 수열을 계산해서 M으로 나눈 나머지를 구하는 것이나 처음부터 피보나치 수의 나머지들로 더하고 나눈 나머지를 구하는 것이나 같다는 것이므로 제대로 된 값이 나올까하는 걱정은 안 해도 된다.
그래서 이렇게 나머지들로 이루어진 수열도 1, 1, 로 시작해서 더하고 나누는 식으로 해서 계속 수열을 구해 나가다가 1, 1,을 만나면 거기서부터 또 다른 주기가 반복된다는 것을 알 수 있다.
이렇게 피보나치 수열은 앞의 두 값에 의해 하나 하나 결정되어 나가고, 위의 나머지 연산 법칙에 의하면 피보나치 수를 나눈 나머지 값을 이용해 수열을 만들어도 피보나치 수를 구해서 나눈 나머지와 같으므로, 피보나치 수를 나눈 나머지 값들로 구성된 수열을 만들어 가면서 연속된 두 값만 확인하면 주기를 쉽게 찾을 수 있는데, 나는 그냥 모든 수를 다 비교할 생각을 했으니... 음 정말 좋은 문제이다.
< 참고 및 출처 >
https://www.acmicpc.net/board/view/4501
http://redsalmon.tistory.com/5
BOJ 1652 누울 자리를 찾아라
얼핏 보면 쉬워 보이지만, 난 처음에 이해를 제대로 못해서 틀렸다.
주의가 필요하다. 물건이 없다면 그냥 누울 자리는 길이가 2이상이기만 하면 한 자리겠지만, 만약 막혀있어서 한 줄에 길이가 2이상인 자리가 여러개 생기면 그 만큼 자리가 존재하는 것이다...!
막상 해보니 어렵다... 만약 예제가 내 오류를 잡아주지 못했다면 이 문제를 푸는데 엄청 오래 걸렸을 것 같다.
블록으로 시작해서 블록 없이 끝나는 경우라든지, 블록으로 끝나는 경우라든지.. 음 근데...
AC를 받고 다른 분들의 코드를 보니...내가 좀 불필요한 것까지 쓸데없이 추가한 것 같기도하다... 그냥 자연스럽게 구현하면 될 것 같다.
주의가 필요하다. 물건이 없다면 그냥 누울 자리는 길이가 2이상이기만 하면 한 자리겠지만, 만약 막혀있어서 한 줄에 길이가 2이상인 자리가 여러개 생기면 그 만큼 자리가 존재하는 것이다...!
막상 해보니 어렵다... 만약 예제가 내 오류를 잡아주지 못했다면 이 문제를 푸는데 엄청 오래 걸렸을 것 같다.
블록으로 시작해서 블록 없이 끝나는 경우라든지, 블록으로 끝나는 경우라든지.. 음 근데...
AC를 받고 다른 분들의 코드를 보니...내가 좀 불필요한 것까지 쓸데없이 추가한 것 같기도하다... 그냥 자연스럽게 구현하면 될 것 같다.
BOJ 1146 지그재그 서기
서로 키가 다른 사람 n명이 주어질 때, 문제에 주어진 규칙에 따라 줄을 서게 되면 키가 큰 사람 뒤엔 작은 사람이 작은 사람 뒤엔 큰 사람이 서게 되어 지그 재그 모양으로 서게 된다.
이렇게 설 수 있는 경우의 수를 구하는 문제인데, 어떻게 풀어야 할까?
dp로 접근해보자.
d[n] = n명의 사람을 지그재그 형태로 세울 수 있는 경우의 수...?
근데 앞에서 어떤 키의 사람이 어떻게 서있냐에 따라 뒷 부분이 달라진다...
예를 들어, 1~5까지 있을 때, 5, 4가 먼저 섰다면 뒤에는 4보다 큰 사람이 와야하는데 없다...
그렇다면 필요한 정보는 앞에 두 사람의 정보가 필요할 것 같다.
d[pre1][pre2][n] = 앞에 두 사람이 pre1, pre2일 때 n번째 사람을 결정할 차례일 때, 지그재그 형태로 세울 수 있는 경우의 수...
그리고 하나 더 줄을 서지않고 남아있는 사람의 수도 알아야 한다. 같은 d[pre1][pre2][n]일지라도 앞에 누가 섰냐에 따라 달라지기 때문에... 그렇다고 n이 100인데 그 상태를 갖고 다니기에는 너무 크다...
다르게 접근해야 할 것 같다.
생각해보다가 떠오른 것이 이 문제는 경우의 수 dp문제인데...
구하는 방법 중에 전체 경우에서 아닌 경우를 빼는 방법이 있다. 한 번 이 방법으로 생각을 해보자. 아닌 경우라 하면, 완벽한 지그재그가 아닌 경우의 수인데... 이 것도 그리 쉽게 구할 수 있을 것 같진 않다...
그냥 질문 검색을 보기로 했다.
유카리코(yukariko )님의 친절한 설명이 답변으로 나와있다.
문제가 되는 부분이 앞에 누가 섰느냐에 따라 달라지기 때문에 줄을 서지 않은 사람을 알아야 한다는 것인데, n이 작다면 bitmask를 이용해서 상태dp를 사용할 수 있지만, n이 너무 크다.
하지만 어떤 사람이 서있고, 아직 서지 않은 사람을 아는 대신, 한 사람에 대해서 그 사람보다 작은 사람의 수, 큰 사람의 수만 알고 있어도 된다.
과연 이 정도 정보만으로 모든 경우를 구별해서 memoization이 잘 될까?
생각해보면 어떤 사람보다 작은 사람의 수와 큰 사람의 수가 같은 경우는 여러 경우가 있을 수 있지만, 확실한 것은 어떤 사람보다 작은 사람의 수와 큰 사람의 수가 같은 경우들은 모두 그 경우의 수가 같을 것이라는 것이다. 아 물론 한가지 조건이 더 필요하다. 그 어떤 사람의 다음에 올 사람이 더 작은 사람인지 더 큰 사람인지에 대한 정보만 있으면 그 경우의 수는 같을 것이다.
모든 사람의 키는 다 다르고, 줄을 세울 때, 큰 사람, 작은 사람, 큰, 작은,... 순으로, 즉 단순히 크기의 비교로만 세우는 것이기 때문에 현재 어떤 사람까지 세웠고, 그 사람보다 작은 사람이 몇 명 있는지와 큰 사람이 몇 명 있는지, 그리고 그 사람 다음에 더 큰 사람이 와야하는지 아닌지에 대한 정보만 같다면 그 사람이 누군지에 상관없이 그 사람 뒤로 줄을 세울 수 있는 경우의 수는 같을 것이다.
그리고 또한, 작은 사람의 수, 큰 사람의 수를 알고 있다면 그 사람이 몇 번째로 줄 서는지도 자동으로 알 수 있다.(즉, 몇 번째인지는 안 넣어도 구분이 된다)
와... 정말 기막힌 방법이다. 단순히 크기 비교로 줄을 세우기 때문에, 어떤 사람을 세우고, 그 사람뒤에 큰 사람이 올지 작은 사람이 올지와 그 사람보다 작은 사람의 수와 큰 사람의 수만 알면...구분이 가능하다...전혀 생각도 못했는데, 이렇게 알고나니 생각못할 건 아닌 것 같기도 하면서... 내 부족함을 또 느낀다. 하지만 이제 문제를 많이 풀기로 결심한 만큼 좌절하지 않고 이런 문제를 다음에는 틀리지 않는 것을 목표로 이렇게 정리도 하고 있고, 계속 빠르게 풀어나가야 겠다.
d[small][big][next] = 현재 사람보다 작은 사람이 small명, 큰사람이 big명이고 다음에 올 사람이 현재 사람보다 next(크거나 작은)한 사람이 올 경우 경우의 수
첫번째 위치에 1부터 n까지의 사람이 서는 경우에 대하여 next는 두가지 경우 모두에 대해서 경우의 수를 구해서 합치면 될 것이다.
구현해 봐야겠다.
다음 사람을 고를 때, 어떤 사람을 고르느냐에 따라 다음 사람의 small, big이 달라지게 된다.
제출해서 한 번 틀렸는데, 원인이 n이 1일때는 답이 1이 나와야 하는데 내 코드에서는 2가 나온다. 그래서 n이 1인 경우만 예외처리를 해줘서 AC를 받았다.!
그리고 이와 비슷한데 n이 작아 bitmask dp로 풀 수 있는 문제도 추천해 주셨다.
참고 및 출처 : https://www.acmicpc.net/board/view/3358
이렇게 설 수 있는 경우의 수를 구하는 문제인데, 어떻게 풀어야 할까?
dp로 접근해보자.
근데 앞에서 어떤 키의 사람이 어떻게 서있냐에 따라 뒷 부분이 달라진다...
예를 들어, 1~5까지 있을 때, 5, 4가 먼저 섰다면 뒤에는 4보다 큰 사람이 와야하는데 없다...
그렇다면 필요한 정보는 앞에 두 사람의 정보가 필요할 것 같다.
d[pre1][pre2][n] = 앞에 두 사람이 pre1, pre2일 때 n번째 사람을 결정할 차례일 때, 지그재그 형태로 세울 수 있는 경우의 수...
그리고 하나 더 줄을 서지않고 남아있는 사람의 수도 알아야 한다. 같은 d[pre1][pre2][n]일지라도 앞에 누가 섰냐에 따라 달라지기 때문에... 그렇다고 n이 100인데 그 상태를 갖고 다니기에는 너무 크다...
다르게 접근해야 할 것 같다.
생각해보다가 떠오른 것이 이 문제는 경우의 수 dp문제인데...
구하는 방법 중에 전체 경우에서 아닌 경우를 빼는 방법이 있다. 한 번 이 방법으로 생각을 해보자. 아닌 경우라 하면, 완벽한 지그재그가 아닌 경우의 수인데... 이 것도 그리 쉽게 구할 수 있을 것 같진 않다...
그냥 질문 검색을 보기로 했다.
유카리코(yukariko )님의 친절한 설명이 답변으로 나와있다.
문제가 되는 부분이 앞에 누가 섰느냐에 따라 달라지기 때문에 줄을 서지 않은 사람을 알아야 한다는 것인데, n이 작다면 bitmask를 이용해서 상태dp를 사용할 수 있지만, n이 너무 크다.
하지만 어떤 사람이 서있고, 아직 서지 않은 사람을 아는 대신, 한 사람에 대해서 그 사람보다 작은 사람의 수, 큰 사람의 수만 알고 있어도 된다.
과연 이 정도 정보만으로 모든 경우를 구별해서 memoization이 잘 될까?
생각해보면 어떤 사람보다 작은 사람의 수와 큰 사람의 수가 같은 경우는 여러 경우가 있을 수 있지만, 확실한 것은 어떤 사람보다 작은 사람의 수와 큰 사람의 수가 같은 경우들은 모두 그 경우의 수가 같을 것이라는 것이다. 아 물론 한가지 조건이 더 필요하다. 그 어떤 사람의 다음에 올 사람이 더 작은 사람인지 더 큰 사람인지에 대한 정보만 있으면 그 경우의 수는 같을 것이다.
모든 사람의 키는 다 다르고, 줄을 세울 때, 큰 사람, 작은 사람, 큰, 작은,... 순으로, 즉 단순히 크기의 비교로만 세우는 것이기 때문에 현재 어떤 사람까지 세웠고, 그 사람보다 작은 사람이 몇 명 있는지와 큰 사람이 몇 명 있는지, 그리고 그 사람 다음에 더 큰 사람이 와야하는지 아닌지에 대한 정보만 같다면 그 사람이 누군지에 상관없이 그 사람 뒤로 줄을 세울 수 있는 경우의 수는 같을 것이다.
그리고 또한, 작은 사람의 수, 큰 사람의 수를 알고 있다면 그 사람이 몇 번째로 줄 서는지도 자동으로 알 수 있다.(즉, 몇 번째인지는 안 넣어도 구분이 된다)
와... 정말 기막힌 방법이다. 단순히 크기 비교로 줄을 세우기 때문에, 어떤 사람을 세우고, 그 사람뒤에 큰 사람이 올지 작은 사람이 올지와 그 사람보다 작은 사람의 수와 큰 사람의 수만 알면...구분이 가능하다...전혀 생각도 못했는데, 이렇게 알고나니 생각못할 건 아닌 것 같기도 하면서... 내 부족함을 또 느낀다. 하지만 이제 문제를 많이 풀기로 결심한 만큼 좌절하지 않고 이런 문제를 다음에는 틀리지 않는 것을 목표로 이렇게 정리도 하고 있고, 계속 빠르게 풀어나가야 겠다.
d[small][big][next] = 현재 사람보다 작은 사람이 small명, 큰사람이 big명이고 다음에 올 사람이 현재 사람보다 next(크거나 작은)한 사람이 올 경우 경우의 수
첫번째 위치에 1부터 n까지의 사람이 서는 경우에 대하여 next는 두가지 경우 모두에 대해서 경우의 수를 구해서 합치면 될 것이다.
구현해 봐야겠다.
다음 사람을 고를 때, 어떤 사람을 고르느냐에 따라 다음 사람의 small, big이 달라지게 된다.
제출해서 한 번 틀렸는데, 원인이 n이 1일때는 답이 1이 나와야 하는데 내 코드에서는 2가 나온다. 그래서 n이 1인 경우만 예외처리를 해줘서 AC를 받았다.!
그리고 이와 비슷한데 n이 작아 bitmask dp로 풀 수 있는 문제도 추천해 주셨다.
참고 및 출처 : https://www.acmicpc.net/board/view/3358
피드 구독하기:
글 (Atom)