욱이의 IT 생존일지

문제로 이동하기 https://www.acmicpc.net/problem/13549 접근 방식 앞서 소개 드렸던 이모티콘 문제와 마찬가지로, 이 문제도 BFS와 DP 모두 사용이 가능합니다. 저는 BFS로 해결했는데, 결과를 보니 DP에 비해 시간과 메모리 모든 면에서 처참했습니다 ㅜㅜ 추후 DP로 해결하는 방법도 포스팅하겠습니다. 이 문제에서 중요한 키워드는 "순간이동을 하는 경우에는 '0초' 후에 이동" 입니다. 즉, 가중치가 0인 간선이 존재한다는 것인데요, 지금까지 BFS로 풀 수 있는 중요한 키워드가 되는 말이 가중치가 모두 1이다. 라는 점이었다는 것을 생각해보면, 이 문제를 BFS로 접근할 수 없는 것이 아닌가 싶을 수 있는데요. 두 가지 방법을 생각해볼 수 있습니다. 큐 두 ..

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

접근 방식 오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다. 이 문제에서는 visited 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다. BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다. 개선 사항 func printRoute(S int) { if P[S] == -1 { fmt.Fprintf(w, "%d ", S) ret..

접근 방식 처음엔 그냥 막 곱하면 되는 줄 알았습니다. 생각해보니 21억번을 제곱하려면, 그냥 곱해서는 안 되고, memoization이라도 해야하나 싶었습니다. 하지만 memoization도 적당히 공간을 잡아야 쓸 수 있지, 21억 개를 모두 배열에 넣는 건 무리수라고 봤습니다. 문제 분류를 보니, 분할정복을 이용한 거듭제곱 이라고 적혀있었습니다. 방법은 굉장히 간단합니다. 재귀함수를 구성해서 연속해서 반씩 쪼개어 분할정복을 하는 겁니다. 이 때 곱셈의 수가 홀수면, 짝수 하나와 홀수 하나로 나눕니다. 이렇게 되면 짝수로 나눠진 거듭제곱은 한 번 구한 값을 두 번 곱하면 되므로, 연산이 줄게 됩니다. 설명 보다는 코드를 보고 이해하시는게 더 빠를 것 같습니다. 코드 package main import..

Prologue 그동안 사내에서 Private Registry를 구축해서 사용하다보니, HTTPS 인증 때문에 인증서 파일을 업데이트하고 도커 데몬을 재시작해주어야 하는 경우가 종종 있었습니다. 만약에 도커 데몬을 재시작하지 않은 상태로 Login을 시도하면 아래와 같은 에러가 발생합니다. Error response from daemon: Get https://192.168.1.1/v1/users/: x509: certificate signed by unknown authority하지만 매우 중요한 프로세스가 운용되고 있는 노드에 대해선 도커 데몬을 재시작하는 것이 상당히 부담이 되었습니다. 경험상 도커를 재시작하고나서 정상적으로 실행되지 않는 프로세스들이 몇몇 있었기 때문입니다. 때문에 Private ..

Prologue Go에서 오브젝트를 JSON으로 변환하려면, 해당 오브젝트를 기술하는 구조체가 선언되어 있어야 합니다. 예를 들자면 다음과 같습니다. type Score struct { Korean uint `json:"korean,omitempty"` Math uint `json:"math,omitempty"` English uint `json:"english,omitempty"` } type UserV1 struct { UserName string `json:"username"` Name string `json:"name"` Email string `json:"email"` Age uint64 `json:"age"` Score Score `json:"score,omitempty"` } 위 구조체의 필..

Prologue 사내에서 자체적으로 운용할 Private Container Registry가 필요해서 초기에는 간단하게 Docker에 docker-registry 이미지를 이용해 아주 간단한 형태로 배포해서 사용하고 있었는데요. UI를 붙여보았지만, 너무 심하게 단순한 정보만을 제공하고 있었고, 무엇보다도 유저 관리가 불가능했습니다. 이렇다 보니, 외부 개발자 분들과 소통할 때, Registry 접근을 위해 사내에서만 사용하는 계정 정보가 쉽게 노출되는 등의 문제가 많았습니다. 이런 불편함을 해소하기 위해 이것 저것 조사하다, 가장 활발하게 발전하고 있는 이 프로젝트를 발견했습니다. Harbor Harbor는 기존 docker-registry와는 달리 policy와 role 기반으로 access를 제어(..

문제 상황 새로운 Private Registry (Harbor)를 구축하고 CA 인증서를 호스트에 등록 및 config.toml 파일까지 업데이트 해주었음에도 불구하고 Image Pull 작업을 요청하면 401 에러가 발생하였습니다. config.toml 파일을 어떻게 업데이트하여야 하는지는 추후 포스트에서 다루겠습니다. 임시 해결 방법 아래 명령어처럼 image를 가져올 때 --user USERID:PASSWORD 인자를 추가로 넘겨 주면, 정상적으로 이미지를 가져옵니다. 하지만 근본적인 해결책은 될 수 없으므로 해당 문제를 완전히 해결할 수 있는 방법을 찾으면 업데이트 하도록 하겠습니다. $ sudo ctr images pull --user USERID:PASSWORD IMAGE_PATH 마무리 여기..

여담 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의 개수를 빼준 크기입니다. 따라서, 실질적으로 사용하게 되는..