욱이의 IT 생존일지

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

bufio.Scanner bufio.Scanner는 bufio.Reader를 대신하여 줄 바꿈 등으로 구분되는 텍스트 파일 등의 데이터를 읽는 편리한 인터페이스를 제공합니다. bufio.Reader와 눈에 띄는 가장 큰 차이점이라면, 입력을 받았을 때, 읽어 들인 값이 \n 을 포함하지 않는다는 점입니다. 이 덕분에 strings.TrimSuffix(_, "\n") 등의 작업을 추가로 해줄 필요가 없습니다. bufio.Scanner와 bufio.Reader의 더 많은 비교는 다음 포스트를 참조해주세요. https://wookiist.dev/102 문제 발견 어제 PS를 하다 정상적으로 푼 문제가 Runtime Error (Index out of range)가 발생하였습니다. 같은 코드를 Python으로 ..

접근 방식 이 문제는 직전 문제인 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

[Go/Golang] 정수형 자료를 입력 받을 때, Scanner 사용하기 일반적으로 PS할 때, 저는 bufio 패키지를 사용합니다. 보통 사용하는 fmt.Scanf() 또는 fmt.Printf()는 버퍼링을 수행하지 않아 많은 양의 입력을 받는 경우 매우 느려집니다. 실행 시간이 매우 중요한 PS에 있어선 더더욱 피하게 되는 내장 함수입니다. 한 줄에 여러 개의 입력을 받는 경우, (*bufio.Reader).ReadString('\n)을 이용해 받고, 끝에 들어오는 \n을 Trim하고 Fields()를 이용해 배열로 쪼갭니다. 그리고 나서 strconv.Atoi()로 숫자 변환을 해줍니다. 만약 한 줄에 셀 수 있을 정도의 입력을 받는다면, fmt.Fscanf((*bufio.Reader), ..

[Kubernetes] Helm으로 Statefulset의 spec upgrade가 안 되는 경우 Helm으로 배포한 패키지에 statefulset이 있으면, helm upgrade 명령을 사용했을 때 오류가 날 가능성이 있습니다. 특정 파드의 리소스 제한을 걸지 않아서, 배포 이후에 제한을 걸기 위해 values.yaml을 업데이트 하고 helm upgrade를 수행했는데, statefulset이 지원하지 않는 업데이트라는 에러를 뿜뿜하더군요. 분명 자원은 spec.template.containers.resources에 있으니까, 이걸 수정한다고 해서 statefulset이 업데이트 할 수 없다고 나오는 건 분명히 버그였습니다. 수소문 해보니 저와 같은 현상을 겪었던 분들이 많이들 계셨고, 찾아낸 해법..