목록백준 (5)
tlov
풀이이전에 풀었던 2048 (Easy) 문제의 풀이 방법에서는 모든 경우의 수를 탐색하여 답을 도출했다면 2048 (Hard)는 10회의 이동으로 확장되었기 때문에 적절히 가지치기를 하여 시간을 줄여 답을 도출해야 합니다. 그럼, 어떤 경우를 가지치기해주어야 할까요? 블록들을 이동시켰는데 이전과 같은 모습일 경우단순하게 생각해봤을 때 가장 먼저 떠오르는 방법입니다. 어떤 한 경우에 대하여 상하좌우를 모두 구하기 때문에 상하좌우 중 같은 모양을 가진 경우가 발생하면 애초에 탐색할 필요가 없습니다. 중복된 경우를 탐색하기 때문입니다. 구한 최댓값이 이전에 구한 것보다 작을 것이라는 게 예상되는 경우이 경우는 저도 백준 질문 검색에서 얻어낸 해답입니다. 예를 들어 처음에 최대 10회 이동에 대해 탐색하였더..
풀이모든 경우의 수에 대해서 검사를 해봐야 어떤 경우에 가장 큰 수가 만들어지는지 알 수 있는 문제입니다.그래서, 풀이 방법은 ‘백트래킹’을 이용하여 모든 경우의 수를 검사하는 것입니다. 백트래킹 자체의 구현은 어렵지 않지만 각 수들을 move 하는 것에 시간이 좀 걸렸던 문제였습니다.위, 아래 이동은 row를 이동하면서 갱신해야하고왼쪽, 오른쪽 이동은 column을 이동하면서 갱신해야합니다. 각 칸에 대하여 선택된 칸 뒤에 남아있는 칸을 순서대로 검사하면서 남아있는 칸이 0이면 넘어가고, 0이 아니면 선택된 칸(0이 아니면)과 합치거나 혹은 선택된 칸(0이면)에 그 칸의 값을 이동시켰습니다. 선택된 칸과 남아있는 칸이 합쳐졌다면 다음 칸으로 넘어가서 같은 과정을 반복하면 되지만, 만약 선택된 칸이 0이..
* 개인적인 기록용입니다.https://www.acmicpc.net/problem/1541 왜 그리디인가?‘+’와 ‘-‘ 그리고 ‘수’로 구성된 식이 있을 때 그 식을 최소로 만드는 계산법을 찾는 것인데, 만약 식에서 ‘-‘를 빼는 것으로 생각하면 ‘-‘ 식 계산 후에 더하는 식이 또 있다면 필연적으로 결과값이 점점 커지게 됩니다. 그래서 최솟값이 절대 될 수 없습니다. 하지만 ‘-‘를 음수로 바꾸는 것으로 생각한다면 ‘-‘ 뒤의 더하는 식들을 이용하여 최솟값을 만들 수 있게 됩니다! 즉, 음수는 절댓값이 클수록 더 작은 값임을 이용하는 것이죠. 예를 들어, 10+20-30+40+50+60-70과 같은 식이 있다면 다음과 같이 묶어주어 10+20-(30+40+50+60)-70 계산하면 최솟값이 됨을 알 ..
https://www.acmicpc.net/problem/10026 풀이문제 보고 두 가지 해결방안이 떠올랐다.첫 번째는 주어진 입력으로 적록색약이 아닌 사람이 봤을 때 구역 수를 먼저 구한 뒤에 그리드 내의 R 또는 G를 한 가지 색으로 통일시켜 적록색약인 사람의 구역 수를 구하는 방법두 번째는 BFS로 돌리면서 현재 색이 R 또는 G 일 때, 상하좌우도 R 또는 G 면 큐에 넣어 구역 수를 구하는 방법어쨌든 둘 다 적어도 그래프 탐색을 두 번 호출해야 해결할 수 있다. 코드import sys, copyfrom collections import dequesys.setrecursionlimit(10000)input = sys.stdin.readlineN = int(input())grid = [list(..
https://www.acmicpc.net/problem/2206 풀이 처음에 14502번 - 연구소 문제처럼 맵(그래프)을 하나하나 돌면서 벽이 있다면 그 벽을 부수고 bfs 돌려보고 최단거리가 아니면 다시 그 자리에 벽을 세우고 다른 벽을 부수어보는 방식으로 해결하려고 코드를 짰는데, 시간 초과 가 나왔고 두 번째 시도에는 틀렸습니다 가 나왔다. 그래서 다른 방법으로 시도해야겠다는 생각으로 다른 분들의 풀이 방법을 보았고 또, 2206번 문제 FAQ 글이 있길래 봤는데... 일단 이 해결 방식은 정답이 될 수 없다. 이유는 2가지가 있었는데, 첫 번째는 시간 복잡도가 너무 크게 나오는 것이다. 연구소 문제 같은 경우에는 N, M 범위가 작아서 하나하나 방문해도 시간 복잡도가 크지 않았지만 이 문제는 ..