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도 이하가 될 지 구하는 문제입니다. 즉, 껍질처럼 감싸게 되면 주어진 점들로 이루어진 선분은 모두 껍질 안에..
https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 로봇 청소기가 움직이면서 더러운 칸을 모두 제거하기 위한 최단 거리를 구하는 문제입니다. 로봇 청소기 시작 위치를 포함하여 더러운 곳의 위치를 노드로 잡고 bfs를 이용하여 각 노드 사이의 최단 거리를 구한 뒤 로봇 청소기 시작 위치를 시작으로 dfs를 돌려 전체 합의 최단 거리를 구하였습니다. (외판원 문제랑 비슷한 느낌으로 dp 추가하면 더 빨리 할 수 있을 것 같다...!!) bfs 과정에서 각 노드..
https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 거울을 설치하여 문 2개를 이을 때 최소 거울 개수를 구하는 문제입니다. 처음에 거울 설치 가능 위치에 따라 해당 경로의 방문 여부를 따로 판단하기에는 (bfs 돌면서 visited 배열 초기화 후 재계산 or 큐에 visited 배열 넣기) 너무 사이즈가 클 거 같아서 우선순위 큐를 이용해 풀어보려했습니다. 하지만 반례가 있었기에 (거울 위치가 계속 돌 수 있음, 그럼 결국 visi..
https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 뭔가 dp를 적용하면 될 거 같은 문제였지만 아이디어를 생각해내는데 좀 시간이 걸렸습니다. (뭔가 비슷한 문제 전에 푼 거 같기도..??) 자식 노드 1명에게만 전화할 수 있으므로, 각 자식 노드가 자식 노드가 루트인 서브트리로 전파하는데 걸리는 시간을 알고있다고 가정하면, 그 결과의 내림차순으로 1씩 더해준 결과의 최댓값이 결국 해당 노드가 루트인 서브트리의 결과입니다. 예를 들어 맨 마지막 리프노드..