욱이의 IT 생존일지

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열 문제로 이동하기 https://www.acmicpc.net/problem/11053 접근 방식 가장 긴 증가하는 부분 수열은 Longest Increasing Subsequence 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수..

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열 문제로 이동하기 https://www.acmicpc.net/problem/11053 접근 방식 가장 긴 증가하는 부분 수열은 Longest Increasing Subsequence 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수..

문제로 이동하기 https://www.acmicpc.net/problem/16946 여담 아... 처음엔 시간초과로, 이후엔 갈피를 잡지 못하다가, 결국 힌트를 보고 나서야 아 맞네!! 하고 바로 풀어냈습니다 ㅋㅋㅋ 엄청 단순하게 생각했는데.. 어림도 없지! ㅜㅜ 접근 방식 단순하게 생각하면, 매번 벽을 만날 때마다, 주변에 몇 개의 공간이 있는지 일일이 세면서 진행하는 방법도 생각해볼 수 있습니다. 하지만, 이렇게 하는 경우, O((N^3)(M^3)) 이라는 시간 복잡도를 얻게 됩니다. NM이 10만이라는 점을 고려해볼 때, 이 방법으로는 불가능하다는 결론에 이르게 됩니다. 그리고 저는 이를 미리 생각치 않아 시간 초과로 고생을 좀 했습니다.. 반면, 연결된 빈 방의 개수를 그룹별로 미리 한 번에 구해..

문제로 이동하기 https://www.acmicpc.net/problem/12886 여담 Gold 5 문제입니다. BFS에는 나름 자신감이 붙게 만들어준 문제입니다. 이제는 Gold도 두렵지 않다..! 뭐 이런거죠 ㅋㅋㅋ.. 사실 흔한 BFS 문제들과 비슷한 패턴으로 풀리는 문제라서.. 크게 어렵진 않습니다. 접근 방식 우선 상황에 대한 정리가 필요합니다. 현재 주어진 정점은 무엇이고, 가고자 하는 정점은 무엇인지 알아야 합니다. 그리고 현재 주어진 정점에서 이동할 수 있는 방법의 수, 다시 말해 간선의 종류는 어떻게 되는지 정리해볼 필요가 있습니다. 현재 주어진 정점 현재 주어진 정점은 당연하게도 (A, B, C) 입니다. 가고자 하는 정점 모든 그룹에 있는 돌의 개수를 같게 만드는 상황이 목표입니다...

문제로 이동하기 https://www.acmicpc.net/problem/17070 여담 오랜만에 DP를 풀어봤습니다. 솔직히 요즘 BFS만 공부하다보니 DP에 소홀해져서 많이 걱정했는데, 스스로 이 문제를 풀게 돼서 정말 기쁘고 행복(?)했습니다! ㅋㅋㅋ 아.. 진짜 예제 입력들 전부 넣어보고 마지막 답이 정확하게 일치하는 거 보고 현실로 탄성을 질렀습니다 ㅋㅋㅋ... 잡설이지만 정말 기뻤답니다 🙂 접근 방식 우선 점화식을 세워봐야 합니다. 다른 어려운 문제들에 비해선 점화식을 세우기 쉬운 편인 것 같았습니다. 처음에는 너무 단순하게 생각해서 D 배열을 이렇게 정의했습니다. D[i][j] = 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수 이렇게 점화식을 세우고 문제를 접근해보니 일단 ..

문제로 이동하기 https://www.acmicpc.net/problem/16947 접근 방식 큰 순서는 다음과 같습니다. 그래프 내의 모든 사이클과 사이클에 속한 정점을 구한다. 사이클에 속한 정점에 연결된 정점들 중 사이클에 속하지 않은 정점을 방문하며 거리를 구한다. 하지만 이 문제에서 핵심은 사이클을 찾고, 사이클에 속한 정점을 구하는 과정입니다. 위 2번은 그저 찾아낸 정점으로부터 DFS 또는 BFS를 수행하면 쉽게 찾을 수 있습니다. 물론 DFS보다는 BFS로 찾는게 더 효율적입니다. 이유는 후에 설명 드리겠습니다. 트리 N개의 정점과 N-1개의 간선으로 이루어진 그래프는 트리입니다. 트리는 사이클이 없으며, 최단 경로를 DFS와 BFS로 구할 수 있습니다. 만약 이 트리에 간선이 하나 더 추..

문제로 이동하기 https://www.acmicpc.net/problem/13549 접근 방식 앞서 소개 드렸던 이모티콘 문제와 마찬가지로, 이 문제도 BFS와 DP 모두 사용이 가능합니다. 저는 BFS로 해결했는데, 결과를 보니 DP에 비해 시간과 메모리 모든 면에서 처참했습니다 ㅜㅜ 추후 DP로 해결하는 방법도 포스팅하겠습니다. 이 문제에서 중요한 키워드는 "순간이동을 하는 경우에는 '0초' 후에 이동" 입니다. 즉, 가중치가 0인 간선이 존재한다는 것인데요, 지금까지 BFS로 풀 수 있는 중요한 키워드가 되는 말이 가중치가 모두 1이다. 라는 점이었다는 것을 생각해보면, 이 문제를 BFS로 접근할 수 없는 것이 아닌가 싶을 수 있는데요. 두 가지 방법을 생각해볼 수 있습니다. 큐 두 ..

접근 방식 이 문제는 BFS로도 접근이 가능하고, DP로도 가능합니다. DP가 더 빠른 성능을 보여주기 때문에 수행 시간에 민감하다면 DP로 접근하는 것이 바람직합니다. 여기서는 BFS를 연습하기 위해 BFS로 접근해보겠습니다. 이 문제에서 주의해야 하는 점은, 같은 정점에 있다고 해서, 실제 같은 정점이 아니라는 점입니다. 예를 들어, 횟수 등의 조건이 들어가게 되면, 해당 조건으로 인해 이용할 수 있는 간선이 달라지기 때문에 조건이 다른 상황에서의 정점은 같은 정점이라고 할 수 없습니다. 정리하자면, 같은 정점이기 위해서는, 해당 정점에서 이동할 수 있는 간선이 같아야 한다는 것입니다. 그러나 이 문제에서는 클립보드에 들어있는 이모티콘의 개수에 의해 정점마다의 상태가 달라집니다. 따라서 이 문제의 기..

접근 방식 오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다. 이 문제에서는 visited 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다. BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다. 개선 사항 func printRoute(S int) { if P[S] == -1 { fmt.Fprintf(w, "%d ", S) ret..

접근 방식 처음엔 그냥 막 곱하면 되는 줄 알았습니다. 생각해보니 21억번을 제곱하려면, 그냥 곱해서는 안 되고, memoization이라도 해야하나 싶었습니다. 하지만 memoization도 적당히 공간을 잡아야 쓸 수 있지, 21억 개를 모두 배열에 넣는 건 무리수라고 봤습니다. 문제 분류를 보니, 분할정복을 이용한 거듭제곱 이라고 적혀있었습니다. 방법은 굉장히 간단합니다. 재귀함수를 구성해서 연속해서 반씩 쪼개어 분할정복을 하는 겁니다. 이 때 곱셈의 수가 홀수면, 짝수 하나와 홀수 하나로 나눕니다. 이렇게 되면 짝수로 나눠진 거듭제곱은 한 번 구한 값을 두 번 곱하면 되므로, 연산이 줄게 됩니다. 설명 보다는 코드를 보고 이해하시는게 더 빠를 것 같습니다. 코드 package main import..