https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 그냥 단순하게 bfs를 돌면 무조건 시간초과가 날 문제입니다. (100만 개 탐색을 100만번....) 그렇기 때문에 다음의 과정을 거쳤습니다. 1. 0으로 연결된 애들의 개수를 세준다. ex. 0 0 0 이런 맵이면 해당 위치는 연결된 0이 3개 이므로 3 3 3이 된다. (그리고 이들은 모두 같은 영역이므로 2번 과정에서 카운트 시 중복되서는 안 됨) 2. 1 위치에서 상..
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 주어진 입력을 그래프로 생각하여 SCC를 이용해 풀었습니다. 1,2,3,4,5,6,7 3,1,1,5,5,4,6 과 같은 입력일 때 기존 그래프를 1->3 / 2->1 / 3->1 / 4->5 / 5->5 / 6->4 / 7->6 과 같이 생각할 수 있고, 이 때 permutation을 형성하게 된다면 강연결요소 중 하나이고 이러한 것들을 다 뽑는다면 정답에서 원하는 최대의 경우입니다...
https://www.acmicpc.net/problem/1067 1067번: 이동 N개의 수가 있는 X와 Y가 있다. 이때 X나 Y를 순환 이동시킬 수 있다. 순환 이동이란 마지막 원소를 제거하고 그 수를 맨 앞으로 다시 삽입하는 것을 말한다. 예를 들어, {1, 2, 3}을 순환 이동시키면 www.acmicpc.net FFT를 이용해 Convolution 을 구하는 문제입니다. (단순히 브루트포스로 계산하면 최대 60000 * 60000 번 루프 돌아야하므로 시간초과) FFT를 이용해 입력받은 수들을 적용하여 Convolution을 구하기 위해서는 rotation 시킬 다항식을 2배로 적용하고 (ex. a b c d => a b c d a b c d) 곱할 다항식을 reverse 합니다. (ex. a..
https://www.acmicpc.net/problem/13277 13277번: 큰 수 곱셈 첫째 줄에 정수 A와 B가 주어진다. 두 정수는 0보다 크거나 같은 정수이며, 0을 제외한 정수는 0으로 시작하지 않으며, 수의 앞에 불필요한 0이 있는 경우도 없다. 또한, 수의 길이는 300,000자리를 www.acmicpc.net FFT의 대략적인 개념은 알고 있었지만 (그냥 다항식 곱셈 빨리한다는 정도....) FFT를 이해하고 적용시켜본 문제입니다. FFT 개념은 아래의 글을 참고하였습니다. https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98 고속 푸리에 변환 - 위키백과, 우리 모두..
https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 그라함 스캔 알고리즘을 이용해 볼록 껍질 문제를 해결하였습니다. 처음 접하는 알고리즘이라 아래 글을 참고하였습니다. 참고 : https://www.crocus.co.kr/1288 볼록 껍질 : Convex hull , 주어진 점들 중 어떤 점을 이어야 모든 내각이 180도 이하가 될 지 구하는 문제입니다. 즉, 껍질처럼 감싸게 되면 주어진 점들로 이루어진 선분은 모두 껍질 안에..