욱이의 IT 생존일지

여담 MST (Minimum Spanning Tree, 최소 신장 트리) 공부 중에 MST 문제로 이 문제가 포함되어 있는 것을 보고 풀게 되었습니다. 접근 방식 처음에는 "어 그냥 노드 개수 - 1 아닌가?" 하고 "에이 설마.." 했습니다. 그러곤 MST를 공부하면서 익힌 Kruskal 알고리즘을 적용해서 풀어보고자 했습니다. 그러나 제출한 코드에 오류가 있는지 WA를 받아서 질문을 검색하다가 N-1이 답이라는 사실을 알게 되었습니다... 용어 정리 일반적인 그래프에서 사이클을 제거한 후에 Tree로 만들면, 이를 Spanning Tree라 합니다. 또한 Tree의 특성 상, 간선(edge)의 수는 정점(vertex)의 수가 N 개 일 때, N-1개가 됩니다. 이러한 상황에서 MST는 Spanning..

접근 방식 앞선 포스트에서 소개한 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시간 정도 고민 후에 어쩔 수 없이 참고 자료를 확인했는데요, 앞선 방법을 고민하다가 얼핏 생각했던 방식이 실제 문제를 푸는 점화식인 걸 확인하고,,, ..

접근 방식 이 문제는 직전 문제인 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]은 일치하지 ..

접근 방식 이 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것의 길이를 찾는 문제입니다.. 문제에서 예로 든 것은 ACAYKP와 CAPCAK의 LSC인데요. 이 둘의 LCS는 ACAK가 됩니다. 여담으로, LCS는 Longest Common Subsequence의 약자입니다. Substring과의 다른 점은, Substring은 연속으로 붙어 있어야 한다는 제약이 있는 반면에, Subsequence는 그러한 제약이 없다는 점입니다. 백준 강의를 들어보니, 두 문자열의 LCS는 다음과 같다고 설명하고 있습니다. 두 문자열의 LCS는 다음과 같이 같은 문자가 일치하게 공백을 삽입하는 것과 같다고 볼 수 있다. A = "ACAYKP" B = "CAPCA_K_" 그러나 제가 참고한..

백준 11058 - 크리보드 [Gold/5] - Golang 접근 방식 DP로 접근할 수 있다. 힌트에도 주어져 있지만, 큰 문제를 작은 문제로 잘게 나누어 풀 수 있기 때문이다. 순서 TBD 코드 package main import ( "bufio" "fmt" "os" "strconv" ) var ( w = bufio.NewWriter(os.Stdout) sc = bufio.NewScanner(os.Stdin) ) var ( D [101]int N int ) func init() { sc.Split(bufio.ScanWords) } func main() { defer w.Flush() N = scanInt() D[1], D[2], D[3] = 1, 2, 3 for i := 4; i

백준 1062 - 가르침 [Gold/4] - Golang 사족 훈련소에서 백준 랭킹 1위인 구사과님을 만났습니다. 엄청난 우연이었는데, 이 때 많은걸 배운 것 같습니다. 앞으로는 제가 풀었던 문제들, 한참 생각해보았지만 떠오르지 않아 인터넷을 조금 참조 또는 대다수 참조한 경우 가리지 않고 생각의 흐름과 이해한 내용을 정리해서 포스팅할 계획입니다. 두서가 없고 설명이 어색한 때가 있으면 가감없이 댓글로 남겨주시면 감사하겠습니다 🙂 접근 방식 주어진 N, K, 단어의 길이가 브루트포스한 완전 탐색을 수행할 수 있을 정도의 크기라서 완전 탐색을 사용하기로 했습니다. 처음에는 단어를 순회하면서 가장 최적의 알파벳을 찾아야 하는 것인 줄 알았는데, 알파벳을 사용할 수 있는만큼 뽑고, 해당 알파벳 집합으로 주어진..