수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/12869

정답 풀이

주어진 각 scv의 체력을 각각 감소 시키는데 0, 0, 0을 만드는데 최소한의 횟수를 구하는 문제다. 

어떻게 풀어야할지 잘 몰랐는데 블로그를 참고하니 3차 행렬을 이용하면 된다고 한다. 

1. dp[i][j][k]는 각 scv의 체력이 i, j, k일 때의 공격 받은 횟수를 의미한다.

2. 삼중 for문으로 배열을 순회하며 모든 경우의 수([1, 3, 9]의 permutation = 3!)를 고려해 공격한다. 공격하면 인덱스가 줄어든다.

3. 아예 처음인 체력(dp[][][] == 0)이거나 현재 있는 체력 값보다 이전 체력값 + 1이 더 작은 경우에 업데이트 한다.

if dp[ni][nj][nk] == 0 or dp[ni][nj][nk] > dp[i][j][k] + 1:

4. dp[0][0][0]은 모든 체력이 0, 0, 0일 때의 최소 공격 수 이므로, 출력한다. 이때 초기화하느라 1을 추가했으므로 이를 빼주고 출력해줘야 한다.

n = int(input())
scv = list(map(int, input().split())) + [0, 0] # 3개 미만이 들어왔을 때 개수 맞춰주기 위함

# dp[i][j][k] 값은 각 scv 체력이 i, j, k 일 때 공격 받은 횟수를 의미한다
dp = [[[0] * 61 for _ in range(61)] for _ in range(61)] 
dp[scv[0]][scv[1]][scv[2]] = 1 # 1로 초기화, 마지막에 1을 빼줘야 한다

case = [[1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]]
for i in range(60, -1, -1):
    for j in range(60, -1, -1):
        for k in range(60, -1, -1):
            if dp[i][j][k] > 0:
                for c in case:
                    ni = max(i - c[0], 0)
                    nj = max(j - c[1], 0)
                    nk = max(k - c[2], 0)
                    
                    # 처음 도착한 경우 or 더 적은 횟수로 도착하는 경우에만 업데이트
                    if dp[ni][nj][nk] == 0 or dp[ni][nj][nk] > dp[i][j][k] + 1:
                        dp[ni][nj][nk] = dp[i][j][k] + 1
                        
print(dp[0][0][0] - 1)

Reference

https://cme10575.tistory.com/169

- 문제 : https://www.acmicpc.net/problem/21921

정답 풀이 

길이가 x인 구간의 원소합을 누적합으로 푸는 문제이다. (이중 반복문으로 풀면 시간복잡도가 올라갈 것 같다)

그런데 여기서 주의해야할 점이 2가지 있다. 

1. 누적합 계산식

일단 주어진 배열을 누적해서 더한 값을 num_sum이라는 배열에 저장한 뒤 반복문 돌면서 num_sum[i + x -1] - num_sum[i - 1] 계산식으로 각 구간의 합 중 최댓값을 answer에 저장하면된다. 

num_sum[i + x -1] - num_sum[i - 1]

여기서 헤맸던 부분이 위 계산식이다. i를 포함하고 길이가 x가 되려면 오른쪽 끝 인덱스는 i + x - 1이 되는 것 까지는 알았는데, 시작점이 i가 아니다. 누적합이라 i는 0인덱스부터 i인덱스까지의 합이므로 num_sum[i]를 빼는 것이 아니라, i 이전인 i - 1 값을 빼줘야 한다. 왜 그래야 하는지는 아래의 그림으로 쉽게 설명이 가능하다. 그래서 위의 계산식이 나온다.

2. 위 계산식으로는 엔드케이스(0부터 x - 1 까지)를 포함하지 못한다

누적합의 원리를 토대로 계산식은 구했지만 위 계산식으로는 i의 범위가 [1, n - x + 1]이 된다. 이렇게 진행하면 사실상 1부터 x 길이의 구간합을 구하는 것이라 0부터 x - 1까지의 누적합 계산을 하지 못한다. 그래서 num_sum과 arr 가장 왼쪽에 0을 추가해 엔드케이스까지도 포함해 계산할 수 있게 했다. 

arr = [0] + list(map(int, input().split()))

num_sum = [0] * (n + 1)
num_sum[1] = arr[1]
for i in range(2, n + 1):
    num_sum[i] = num_sum[i - 1] + arr[i]

n, x = map(int, input().split())
arr = [0] + list(map(int, input().split()))

num_sum = [0] * (n + 1)
num_sum[1] = arr[1]
for i in range(2, n + 1):
    num_sum[i] = num_sum[i - 1] + arr[i]


answer = 0
for i in range(n - x + 1):
    answer = max(answer, num_sum[i + x] - num_sum[i])


if answer == 0:
    print("SAD")
else:  
    count = 0
    for i in range(n - x + 1):
        result = num_sum[i + x] - num_sum[i]
        if result == answer:
            count += 1

    print(answer)
    print(count)

gRPC란?

구글에서 개발한 어느 환경에서도 실행할 수 있는 최신 오픈 소스 고성능 RPC 프레임워크 

RPC(Remote Procedure Call)

프로세스 간 통신 기술. 별도의 원격 제어를 위한 코딩 없이 다른 주소 공간에서 함수나 프로시저를 실행할 수 있게 해준다.

MSA 구조의 서비스에서 모듈 간의 언어에 구애받지 않고 원격에 있는 프로시저를 호출해 고유 프로그램의 개발에 집중할 수 있게 해주는 기술이다. (MSA의 각 모듈 간 통신을 원활하게 해주는 기술)

gRPC를 이용하면 원격에 있는 애플리케이션의 메서드를 로컬 메서드인 것처럼 직접 호출할 수 있기에 애플리케이션과 서비스를 보다 쉽게 만들 수 있다. 

gRPC 서버(Proto Response), gRPC 클라이언트(Proto Request 전송 부분)

Stub

서버와 클라이언트는 서로 다른 주소 공간을 사용하므로 함수 호출에 사용된 매개변수를 꼭 변환해줘야 한다. 그렇지 않으면 메모리 매개 변수에 대한 포인터가 다른 데이터를 가리키게 된다.

클라이언트 stub : 함수 파라미터 변환 -> 함수 실행 -> 서버 response 변환 담당

서버 stub : 클라이언트가 전달한 매개변수 역변환, 함수 실행 결과 변환 담당

Protocol Buffer

gRPC에서는 IDL(Interface Definition Language)로 protocol buffer를 사용한다. 

protocol buffer : 직렬화 데이터 구조. Json, XML

proto file : 직렬화하려는 데이터 구조 정의. 특정 언어에 대한 종속성이 없는 데이터 타입. 프로토 버퍼는 여러 프로그래밍 언어를 지원하기 때문.

프로토콜 버퍼 데이터는 ‘이름-값’의 쌍을 포함하는 작은 논리적 레코드인 메시지로 구성됨

proto file -> protoc 컴파일로 컴파일 -> 언어에 맞는 데이터 클래스 생성

만들어진 클래스는 각 필드를 위한 접근자 뿐 아니라 

전체 구조 -> 바이트 (직렬화)

바이트 -> 전체 구조 (파싱) 

메서드 제공

gRPC 특징

높은 생산성과 다양한 언어 및 플랫폼 지원

Protocol Buffer의 IDL만 정의하면 서비스와 메시지에 대한 소스코드가 자동으로 생성되고 데이터를 주고 받을 수 있따.

HTTP/2 기반 양방향 스트리밍

성능 이점

gRPC는 HTTP/2 레이어 위에서 Protocol Buffers를 이용해 직렬화된 바이트 스트림으로 통신해 JSON 기반 통신보다 더 가볍고 통신 속도가 빠르고, latency 감소, 더 많은 트래픽 처리 가능

-> 속도 빠르고, 더 많은 트래픽 처리 가능하며, 편리하다

서킷 브레이커란?

서킷 브레이커가 뭔가 하니 두꺼비 집에서 과부하, 단로, 누전으로부터 전기 회로를 보호하는 안전장치다.

서킷 브레이킹은 분산 시스템에서 서비스 간의 의존성과 가용성을 보장하기 위한 패턴 중 하나.

서킷 브레이킹 동작 방식

1. 장애 서비스 일시적으로 엔드포인트에서 제거

서비스 장애 상황 시 호출이 지연/실패할 경우, 서킷 브레이커는 장애 서비스를 일정 기간 동안 엔드포인트에서 제거하고 서비스의 상태가 정상으로 회복되기를 기다린다(모니터링). 

2. 장애 서비스로의 지연/장애 현상 전파 방지

장애 서비스에 대한 호출은 다른 서비스로 라우팅 되게 함으로써, 서비스 간의 지연 또는 장애 현상이 전파되는 것을 방지할 수 있게 해준다. 장애가 전체 시스템에 영향 최소화

서비스 메시

애플리케이션 서비스 간 모든 통신을 처리하는 소프트웨어 계층

애플리케이션이 확장되고, 마이크로서비스의 수가 증가함에 따른 성능 모니터링 문제 해결

서비스 간 연결을 관리하기 위해 모니터링, 로깅, 추적, 트래픽 제어와 같은 기능 제공

인프라 개발자, 서비스 개발자 -> 주로 인프라 개발자에게 서비스 메시는 이점을 준다

플랫폼 레이어(인프라 쪽)에 구성되는 네트워크 제어 방법

애플리케이션 트래픽을 관리, 추적 및 보안성을 강화하기 위해 사용

마이크로서비스 간 통신 문제 해결

대표 기능 -> 애플리케이션 트래픽 관리, 관찰 가능성, 보안

데이터 플레인, 컨트롤 플레인 두 개의 컴포넌트로 구성됨

데이터 플레인 : 애플리케이션 사이에 있는 프록시(envoy 서비스로 구성, 서비스와의 프록시 호출 담당) 네트워크로 구성됨, 서비스 메시의 모든 서비스에 대한 모든 인바운드 및 아웃바운드 트래픽 관장.

컨트롤 플레인 : 프록시에게 수행할 작업을 알려주고 메시를 작동하는 사람을 위한 인터페이스 제공, 서비스 검색(discovery), TLS 인증서 발급, 메트릭 집계 등 데이터 플레인이 작동하는데 필요한 컴포넌트 제공

컨트롤 플레인 <-> 프록시 <-> 애플리케이션

서비스 메시 툴

Istio

문제점

• 프록시 자원은 인프라와 관련해 리소스를 소비하며 네트워크 지연을 발생시킴. 
• 프록시 사용 서비스 개수 증가 -> 메모리, CPU 소비량 증가, 커넥션 풀 수 증가(point of failure도 증가)
• 코드 수정 가능성(http 설정, 라이브러리 변경)
• 트러블 슈팅이 어렵다

대안

서킷 브레이커(Spring Cloud for Kubernetes), Observability의 대안(Jaeger, Zipkin 같은 분산 트레이싱 도구) 

Reference

https://aws.amazon.com/ko/what-is/service-mesh/

https://www.samsungsds.com/kr/insights/service_mesh.html