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

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

접근 방식 앞선 포스트에서 소개한 14238번 문제인 '출근 기록' 문제와 유사한 문제입니다. 문제의 조건 하루에 한 명씩 출근한다. 문자열의 길이 = 출근 기록의 길이(N) A는 본인 스스로 짝을 이룰 수 없다. B는 A와 짝을 이룰 수 있다. C는 A, B 모두와 짝을 이룰 수 있다. 반드시 필요한 조건만 정리해보면, 문자열의 길이인 i가 필요합니다. 또한 A가 몇 개 있는지, B가 몇 개 있는지, C가 몇 개 있는지 알아야 합니다. 마지막으로 쌍의 개수를 계속 체크해주어야 하므로, 쌍의 개수도 나타나야 합니다. 그런데 여기에서 변수를 하나 줄일 수 있습니다. 바로 C인데요. C의 개수는 전체 문자열의 길이에서 A의 개수와 B의 개수를 빼준 크기입니다. 따라서, 실질적으로 사용하게 되는..

접근 방식 이 문제는 앞으로 정리할 문제인 12969번의 ABC 문제와 유사한 문제입니다. 아무리 생각해도 점화식이 떠오르지 않아 강의를 듣고 이해한 내용을 정리해봅니다. 문제의 조건 하루에 한 명씩 출근한다. 문자열의 길이 = 출근 기록의 길이(N) A는 매일 출근이 가능하다. B는 출근한 다음 날에는 쉬어야 한다. C는 출근한 다음 날과 다다음 날은 쉬어야 한다. 반드시 필요한 조건만 정리해보면, A가 출근한 횟수, B가 출근한 횟수, C가 출근한 횟수가 필요합니다. 또한 B와 C처럼 전날과 전전날의 출근자를 알아야만 상황이 정의되는 사람을 표현하기 위해 전날 출근자(P1)와 전전날 출근자(P2)의 정보도 필요합니다. 참고로 12969번 ABC 문제는 전체 문자열의 길이를 알고 A와 B의 개수가 정해..

접근 방식 이 문제는 직전 문제인 LCS (9251) 문제와 동일합니다. 다만 한 가지 더 출력해야 하는데요. 바로 찾은 LCS의 길이 뿐만 아니라, LCS 부분 수열 자체도 출력해야 합니다. 이 문제를 보고 처음 든 생각은, 아 뭔가 부모를 찾고 찾아서 거꾸로 이동하면서 출력하면 되겠구나.. 였습니다. 하지만 부모를 찾아갈 때 어떤 조건을 기준으로 이동할 것인지 생각하는 부분이 어려웠습니다. 중요한 점은 이전에 LCS의 길이가 증가할 때를 살펴보면, [i] == B[j]인 경우였습니다. 이 경우에 D[i][j] = D[i-1][j-1] + 1을 이용할 수 있었죠. 부분 수열 자체를 찾기 위한 꼬리에 꼬리를 무는 이동 조건도 이와 유사합니다. 이 전에 D[i-1][j] 또는 D[i][j-1]은 일치하지 ..

접근 방식 처음에는 점화식을 어떻게 세워야 할 지 매우 고민했습니다. D[i][j] = (i, j)를 연결할 때 삭제 되어야 할 전선의 최소 개수라고도 세워보고, D[i] = i 번째 전깃줄까지 교차줄이 없게하는 최소 삭제 전깃줄의 개수로도 접근해봤습니다. 아무래도 문제가 풀리지 않아, 처음부터 그림을 그려가며, 그 순서를 살펴봤는데요. 어째 보면 볼수록 가장 긴 증가하는 부분 수열의 길이를 구하는 문제와 비슷해보이는 겁니다. 즉, 없애야 하는 전깃줄의 최소 개수를 구한다는 것은, 전체 전깃줄의 개수에서 남아 있어도 되는 전깃줄의 최대 개수를 뺀 값과 일치한다는 것을 발견한 겁니다! 없애야 하는 전깃줄의 최소 개수 = (전체 전깃줄의 개수) - (교차하지 않고 남아 있어도 괜찮은 전깃줄의 최대 개수) 따..

문제로 바로 가기 : BOJ 5557 - 1학년 접근 방식 백준님의 강의 중 '연습'에 해당하는 DP 마지막 문제입니다. 1학년 문제는 LCS 문제 다음으로 나와서, LCS 풀듯이 푸는 건가 싶었는데, 일단 그건 아니었습니다. 두 번째로 생각했던 건, 일반적인 DP 문제를 풀 때 생각할 수 있는 마지막 수와의 관계를 생각해보았는데요, 여기에서 D[i][j] = i번째 수를 j가 0이면 더하여 현재 sum을 만드는 등식의 수, j가 1이면 빼서 현재 sum을 만드는 등식의 수라고 생각했습니다. 그러나 이 방법도 정답에 도달하지 못했습니다. 1시간 정도 고민 후에 어쩔 수 없이 참고 자료를 확인했는데요, 앞선 방법을 고민하다가 얼핏 생각했던 방식이 실제 문제를 푸는 점화식인 걸 확인하고,,, ..