개발 노트

문제

과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.

입력

입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다.

출력

각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다.

해설

먼저 피타고라스의 정리를 한번 보고 오실까요?

https://ko.wikipedia.org/wiki/%ED%94%BC%ED%83%80%EA%B3%A0%EB%9D%BC%EC%8A%A4_%EC%A0%95%EB%A6%AC

피타고라스 정리는 간단하게 정리하면

a^2+b^2 = c^2

입니다!

따라서 주어신 3개의 변중에 빗변(c)을 찾고,

나머지 두 변의 제곱 값을 더한 값이 빗변의 제곱과 같은지만 확인 하면 되는 간단한 문제입니다!

바로 코드로 넘어갈게요.

코드

https://chunghyup.tistory.com/50

위 게시물과 연결되는 내용입니다.

JS를 이용하여 간다하게 Circuit Breaker를 구현해보았다.

몇번 실패를 하면 Open을 할 것인지, 몇 초 후 halfOpen으로 만들것인지 두가지 기능만 구현을 해 놓았다.

직접 사용하며 추가로 필요한 옵션이 필요하다면 기능을 추가 구현 하면 될 것 같다.

NPM에도 올려놓았는데, 사용 중 ISSUE가 발생해서 리포팅이 들어왔으면 좋겠다....

https://www.npmjs.com/package/super-simple-circuit-breaker

설명

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

해설

 아래와 같이 집1, 집2, 집3인 경우의 R,G,B 페인트를 칠하는 비용이 있다고 가정한다.

Dynamic programming은 이전 계산값을 저장해서 다음 계산에 사용한다고 생각할 수 있다.

아래 그림을 보면 위에서 만든 자료구조를 가지고 같은 모양(열과 행이 같은) 자료구조를 만들어 자료를 업데이트 하는 것을 볼 수 있다.

업데이트를 하는 과정은 아래와 같다.

1. 각 샐은 현재 집을 해당 컬럼(R,G,B)로 칠했을때의 최소 비용이다.

2. 집2에 빨간색을 칠하는 경우 : 집2를 빨간색으로 칠하는 비용 + 최소값(집1을 초록색으로 칠하는 경우, 집 1을 파란색으로 칠하는 경우)

    집2에 파란색을 칠하는 경우 : 집2를 파란색으로 칠하는 비용 + 최소값(집1을 초록색으로 칠하는 경우, 집 1을 빨간색으로 칠하는 경우)

위 2개의 규칙을 따라서 전체 셀을 업데이트 한다.

마지막까지의 최소비용을 구하면 해당 row에서 가장 최소인 값을 출력해주면된다.

코드

문제

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

입력

세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.

출력

직사각형의 네 번째 점의 좌표를 출력한다.

해설

축에 평행한 직사각형을 만들기 위해서는 사실 두개의 점만 알고 있다면 직사각형을 그릴 수 있다.

직사각형의 시작점과 끝점 2개(그림에서 파란색 점 두개)만 안다면 직사각형을 그릴 수 있다.

(x1, y1) (x2,y2) 두개의 점을 안다고 하는 경우 아래와 같이 직사각형이 그려진다.

다시 문제로 넘어가면, 3개의 점을 알고 있다면 x1, y1, x2, y2 4개의 값을 모두 알 수 있다.

점 4개의 좌표값을 모으면 각자 2번씩 등장하기 때문에 우리는

3개의 점의 좌표값 중 1번만 등장하는 값을 찾으면 된다.

코드

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

해설

문제는 재귀적으로 피보나치 수열 문제를 풀었을 때 f(n)은 f(1)과 f(0)을 각각 몇번씩 호출하게 되는가?로 해석이 가능하다.

f(2)는 f(1)을 1번, f(0)을 1번 호출한다.

f(3)은 f(2)를 1번, f(1)을 1번 호출한다. 따라서 f(2)각 f(1)과 f(0)을 각각 1번씩 호출하기 때문에 총 f(1) 2번 f(0) 1번 을 호출한다.

이러한 방식으로 f(1)을 호출하는 회수와  f(0)을 호출하는 회수를 위의 피보나치 코드와 매우 비슷한 형태로 풀 수 있다.

그림이 매우 별로이지만 zero라고 된 부분이 f(0)을 호출하는 회수이고 one 이 f(1)을 호출하는 회수이다.

이 각각은 zreo(n) = zero(n-1) + zero(n-2) 와 같이 풀면서 계속해서 더해간다면 f(n)에서의 f(0), f(1) 호출 회수를 구할 수 있다.

코드

Go에는 내부 encofing 라이브러리로 json을 내장하고 있다.

json.Unmarchal을 이용하면 간단하게 json string 여부를 판별 할 수 있다.

func isJSONString(s string) bool {
    var js string
    err := json.Unmarshal([]byte(s), &js)
    return err == nil
}

만약, API 호출 이후 body가 JSON인지 확인하려면 아래와 같이 사용을 할 수도 있다.

func isJSONString(bytes []byte) bool {
    var js string
    err := json.Unmarshal(bytes, &js)
    return err == nil
}

bodyBytes, err := ioutil.ReadAll(res.Body)

isJSONString(bodyBytes)

네트워크 모듈 관련 테스트 코드를 작성중

*http.Response 의 body에 더미 데이터를 넣어줘야해서 사용하게 됨.

ioutil.NopCloser 를 이용하여 io.ReadCloser를 만들 수 있고, String Reader를 통해 ioReader를 생성하여 파라메터로 넘겨줄 수 있다.

문제

한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 x, y, w, h가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

• 1 ≤ w, h ≤ 1,000
• 1 ≤ x ≤ w-1
• 1 ≤ y ≤ h-1
• x, y, w, h는 정수

해설

문제를 쉽게 풀어서 설명한다면

"직사각형 내부에 있는 점 (x,y)에서 직사각형의 변까지의 최소 거리" 를 구하는 문제이다.

결국 최솟값을 찾으면 되는 문제이다. 무엇중에 최소값을 구하는지만 생각하면 해결된다.

사각형이니까 변이 4개, 우리에게 주어진 점은 1개(x, y)

그렇다면 (x, y)에서 사각형 각 변까지의 거리 총 4개를 구하고 그중에 최솟값을 취하면 된다.

아래 코드는 4개의 거리값을 구하고, 정렬을 이용하여 최솟값을 구하는 코드이다.

코드

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

해설

1은 표현을 하지 않아도 되기 때문에 2부터 시작하며 해당 수를 나누면서 진행하면 소인수를 얻을 수 있다.

나누어서 0이 되는 숫자를 찾게 된다면, 나누어서 소인수를 저장하고 다시 2부터 나누기를 시도하며 진행한다.

작은 숫자에서부터 차례로 검사하며 배열에 넣기 때문에 소수를 오름차순으로 정렬을 하라는 요구조건은 따로 처리를 하지 않아도 만족한다.

코드

golang 1.14

증상

운영중인 서버 상태를 모니터링 하는데 Memery 사용률이 50% 이상인 상태로 2시간이 넘게 지속되는 현상이 발생.

하지만 CPU 사용량은 3% 미만이고 트래픽이 많이 발생하지 않는 상태였음.

로그를 확인해보니 중간에 트래픽이 몰리면서 CPU 사용량이 30% 이상으로 지속되면서 메모리 사용량이 늘어난 것을 확인함.

문제 해결

최초에는 'Memory leak이 있나?' 생각했지만 6개월 이상 정상적으로 동작하던 서버였기 때문에 Memory leak을 찾기 전 관련 Issue를 찾아보기 위하여 Stack overflow와 Golang 커뮤니티를 검색함.

결론

Memory leak이 아님!

golang에서 OS에서 할당받은 메모리를 release해주지 않던것이 해당 증상의 원인이었음.

Memory를 할당 받는 것은 비용이 크기 때문에 반환을 하지 않고, golang에서 해당 메모리를 계속 들고 있게됨.(OS에서 Memory가 필요하면 반납함)

만약 강제로 Memory를 반납하고 싶다면 

debug.FressOSMemory()

를 사용 할 수 있음

추가 사항

Autoscaling 정책에 Memory 점유율도 포함을 시켜놓고 있었는데, 

해당 서버에서는 컨테이너화된 Go 서버만 돌고 있기 때문에 Memory 점유율에 대한 정책을 조절하여 위와 같은 상황에서 Scale-out되는 경우가 덜 발생하도록 함.

Golang 1.16에서는 Memory 계산 방법이 변경되어 위와 같은 증상이 발생하지 않는다고 하는데, Golang 버전 변경을 아직 해보지 않아서 확인해보지 못함.(나중에 해봐야지...)