고언어 20

[BOJ/2565/Golang] 백준 2565 - 전깃줄

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

PS/BOJ 2021.05.20

[BOJ/5557/Golang] 백준 5557 - 1학년

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

PS/BOJ 2021.05.19

[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 2021.05.18

[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

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

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

PS/BOJ 2021.05.01

[Go/Golang] Zap과 시간 기반 파일 로테이션 로깅 수행하기

본 포스트는 'dhwaneetbhatt'의 Time based log file rotation with zap 글을 번역한 것임을 밝힙니다. Zap과 시간 기반의 파일 로테이션 로깅 zap은 현재까지도 잘 개발되어오고 있고, 성능 측면에서도 훌륭한 Go의 오픈소스 로깅 라이브러리입니다. 유감스럽게도, 원 글쓴이(이하, 필자)의 조직에서 제공하는 모든 앱들이 12-factor 애플리케이션으로 구성되지 않았으며, 이로인해 물리적으로 파일에 로그를 남기는 작업이 여전히 필요했습니다. 이와 같은 이유로 zap을 사용함과 동시에 파일을 로테이션 할 수 있도록 하는 방법이 필요했습니다. 필자는 Java 진영에서 넘어왔기 때문에 log4j의 매우 다양한 파일 로테이션 옵션을 제공하고 있는 것을 알고 있..

IT/Go 2021.03.29

[Go/Golang] Go Application에 Prometheus Exporter 연동하기

Prometheus Prometheus는 CNCF의 오픈 소스 프로젝트로 System과 Service 모니터링 시스템입니다. 특정 주기를 기준으로 사용자가 구성한 target으로부터 metric을 수집합니다. 또한 사용자가 정의한 rule expression을 계산하여 해당 결과를 보여주고 특정 조건을 만족하는 상황에 도달하면 알람을 울리는 등의 기능을 수행합니다. Prometheus는 시계열(time-series) 데이터를 처리하는 데에 특화되어 있습니다. Prometheus Exporter Prometheus는 여러 방법으로 metric을 수집합니다. 특히 Exporter라는 구성 요소를 통해 target 시스템 및 서비스의 Expose된 metric을 수집해올 수 있습니다. Prometheus Ex..

IT/Go 2021.03.16

[Go/Golang] Map 자료형을 Struct로 변환하기(mapstructure)

Map Python에는 Dictionary라는 강력한 자료형이 있습니다. 굉장히 유연하고, 편리한 자료형입니다. 기본적으로 Python의 Dictionary는 다른 언어의 Map 자료형과 동일합니다. Python Dictionary의 특별한 점이라면, 하나의 Dictionary 변수 안에 각기 다른 자료형의 데이터가 보관될 수 있다는 점입니다. 따라서 Python에서 어떤 데이터를 Dictionary로 보관하는 일은 그리 어려운 일이 아닙니다. 특히, JSON 데이터를 별다른 추가 작업 없이 Dictionary에 대응할 수 있다는 점은 정말 엄청난 기능이라고 생각합니다. 그러나 Go 진영에선 상황이 다릅니다. Go에서 특정 데이터를 Dictionary로 보관하기 위해선, Key-Value가 어떤 자료형인..

IT/Go 2021.03.15

[Go/Golang] Go의 HTTP & REST Client 라이브러리 - Resty

Go의 HTTP & REST Client 라이브러리 - Resty API Client 이전 포스팅에서 다뤘던 Echo는 Go의 Web Framework입니다. Echo로 구현한 프로그램은 API Server 등으로 동작할 수 있고, 큰 어려움 없이 Web Server로 사용할 수도 있습니다. 하지만 프로그램이 API Server가 아닌 API Client로 동작해야 한다면 어떨까요? API Client는 API Server에 Request를 보내는 주체로 Echo와는 정반대의 기능을 수행해야 합니다. 이런 기능을 Go에서 사용할 수 있도록 구현해놓은 패키지가 있습니다. 바로 Resty 입니다. Resty Resty는 Ruby의 rest-client에서 영감을 받아 시작된 Go의 HTTP & REST Cl..

IT/Go 2021.03.10