Sevity Blog

주 역할

웹서버/캐시/로드밸런서/리버스프록시

SSL Termination

클라이언트와는 https통신을 하면서 백단 서버들과는 http(gRPC포함)통신을 하여, 복호화 부담을 줄이는 기능

실전꿀팁

여기가면 실제로 많이 사용되는 Nginx설정을 보고 적용할 수 있다.

일반적으로 셔플 알고리즘을 떠올리면 다음과 같은 naive solution을 생각하기 쉽다.

void LnNumber::ShuffleArray(long* arr, long count)
{
      for (int i=0;i<count;i++)
      {
            long toInx = rand() % count;
            {//swap
                  long temp = arr[i];
                  arr[toInx] = arr[i];
                  arr[i] = temp;
            }
      }
}

하지만 위 코드는 순진해보이는 겉모습과 다르게 엄청난 바이어스를 포함하고 있는데,

카드 3장의 모든 순열은 3!(=3 x 2 x 1) = 6이지만 위의 toInx를 보면 3 x 3 x 3 = 27로 6으로 나눠떨어지지 않는 경우의 수를 가지고 있다!

따라서 아래처럼 덜 직관적이지만 n!에 맞춘 경우의 수를 가진 코드로 수정해줘야 한다.

이 코드를 Fisher-Yates shuffle이라고 한다.

void LnNumber::ShuffleArray(long* arr, long count) {
    for (int i = count - 1; i > 0; i--) {
        long toInx = rand() % (i + 1); // 0부터 i까지의 랜덤한 인덱스(i포함)
        // swap
        long temp = arr[i];
        arr[i] = arr[toInx];
        arr[toInx] = temp;
    }
}

이코드의 toInx를 보면 카드3장의 예시에서 3 x 2 x 1 = 6 = 3!의 경우의 수를 가진다.

sort

가장 기본적인 sort는 Array.sort()또는 Collections.sort()를 쓰면 된다. (char[] 같은건 전자만 가능한듯?)

struct node 같은걸 쓰면서 특정 필드에 대해 소팅하고 싶으면 다음 기법을 쓰자.

class Tweet {
    Long time;
    int tweetId;
}
List<Tweet> feed;
...

//time에 대해서 sort하고 싶을때
feed.sort((t1, t2) -> t1.time.compareTo(t2.time));  
//역순을 원하면 t1, t2를 바꿔준다.
feed.sort((t1, t2) -> t2.time.compareTo(t1.time));

//약간 올드하게 아래처럼도 가능
Collections.sort(feed, new Comparator<Tweet>() {
    @Override
    public int compare(Tweet t1, Tweet t2) {
        return t1.time.compareTo(t2.time);
    }
});

여러 필드에 대해서 복잡하게 정렬해야하면 아래 방법 사용

feed.sort(Comparator.comparing((Tweet t) -> t.time)
                   .thenComparing(Comparator.comparing((Tweet t) -> t.tweetId).reversed()));

LIS(Longest Increasing Subsequence)는 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.

즉, 주어진 수열에서 일부 숫자를 제거하여 만든 부분 수열 중에서, 오름차순으로 정렬된 가장 긴 수열을 찾는 문제.
예를 들어, 수열 [10, 20, 10, 30, 20, 40]이 있다면, LIS는 [10, 20, 30, 40]이 된다.

예시 백준 문제는 여기 있다.

DP를 연습할때 가장 먼저 나오는 문제이지만, 의외로 2가지 실수하기 쉬운 포인트와. 한가지 인사이트를 제공한다.

2가지 실수하기 쉬운 포인트

아래는 이문제에 대한 정답코드인데, 아래 주석으로 여기라고 되어 있는 부분을 풀때마다 실수했다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// dp[3] = 5 ; 인덱스 3까지 가장 긴 증가하는 부분수열의 길이는 5이다.
int dp[1001]; 
int A[1001];

int main(void)
{
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", A + i),dp[i]=1;  // 여기. dp[i]=1초기화 부분!
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j]) 
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	int ans = 1;
	for (int i = 0; i < N; i++) ans = max(ans, dp[i]);  // 여기. dp[n-1]아니어도 답이 될 수 있음!
	printf("%d\n", ans);
	return 0;
}

한가지 인사이트

이 문제는 놀랍게도 recursive+memoization보다 iterative 방식이 더 생각하기 편하고,

편한 recursive+memoization을 떠올리면 dp[ix][cur_val] 형태가 돼서 냅색DP형태가 나오는데 문제 범위에 따라 메모리초과 오류가 발생하여 해결이 어렵다.

아래는 편한 recursive버전이다.

#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int in[1001];
int n;
int dfs(int ix, int cur_max_val){
    if(ix>=n) return 0;
    if(dp[ix][cur_max_val]) return dp[ix][cur_max_val];
    
    //포함
    int r1 = -1;
    if(cur_max_val < in[ix])
        r1= 1 + dfs(ix+1, in[ix]);
    
    //불포함
    int r2 = dfs(ix+1, cur_max_val);

    return dp[ix][cur_max_val] = max(r1,r2);
}
int main() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", in+i);
    printf("%d\n", dfs(0, 0));

    return 0;
}

자세히 들여다 보면, dp[n]을 1로 초기화 하는 부분도 필요없고, 마지막에 정렬하는 부분도 필요없어서 실수 확률이 확연히 줄어든다.

하지만 위 코드를 dp[ix]로 1차원만 사용하도록 변경하는건 쉽지 않다.

아래처럼 할 수 있긴한데, dfs함수내에 iterative한 부분이 들어 있어 완전한 DFS라고 부를 수 있을지 약간 애매하다.

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i) 
#define REP(i,n) FOR(i,0,n) 
typedef vector<int> VI;

int dp[1001];
int in[1001];
int N;
int go(int n)
{
         if(n==0) return 1;
         if(dp[n]) return dp[n];
 
         int maxR=1;
         REP(i,n){
            if(in[n] >in[i])
                maxR = max(maxR, go(i)+1);                 
         }
         return dp[n] = maxR;
}
 
int main()
{
        scanf("%d\n", &N);
        REP(i, N)scanf("%d",&in[i]); 
        int r=0;
        REP(i,N) r=max(r,go(i));
        cout << r <<endl;
        return 0;
}

실제 시퀀스를 출력하는 방법

아래처럼 prev배열하나를 추가하면 어렵지 않게 구현가능하다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// dp[3] = 5 ; 인덱스 3까지 가장 긴 증가하는 부분수열의 길이는 5이다.
int dp[1001];
int A[1001];
int prv[1001];

int main(void)
{
    fill(prv, prv + 1001, -1);
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)scanf("%d", A + i), dp[i] = 1; // 여기. dp[i]=1초기화 부분!
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (A[i] > A[j])
                if (dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    prv[i] = j;
                }
        }
    }
    int ans = 1;
    int end_ix = 0;
    for (int i = 0; i < N; i++)
    {
        if (ans < dp[i])
        {
            ans = dp[i];
            end_ix = i;
        }
    }
    printf("%d\n", ans);
    vector<int> v;
    v.push_back(A[end_ix]);
    while (prv[end_ix] != -1)
    {
        end_ix = prv[end_ix];
        v.push_back(A[end_ix]);
    }
    reverse(v.begin(), v.end());
    for (auto e : v)
        printf("%d ", e);

    return 0;
}