2021/05 6

[BOJ/9252/Golang] 백준 9252 - LCS 2

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

PS/BOJ 17:40:53

[BOJ/9251/Golang] 백준 9251 - LCS

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

PS/BOJ 2021.05.17

[BOJ/11058/Golang] 백준 11058 - 크리보드

백준 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

PS/BOJ 2021.05.16

[Go/Golang] 정수형 자료를 입력 받을 때, Scanner 사용하기

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

IT/Go 2021.05.13

[Kubernetes] Helm으로 Statefulset의 spec upgrade가 안 되는 경우

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

IT/Kubernetes 2021.05.12

[BOJ/1062/Golang] 백준 1062 - 가르침

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

PS/BOJ 2021.05.01