짧은머리 개발자

오늘은 알고리즘 중 Backtracking 기법을 다뤄보려 한다.

Backtracking
- 한정 조건을 가진 문제를 풀려는 전략
- 해를 얻을 때까지 모든 가능성을 시도

출처 https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89

위키피디아의 설명처럼, 해를 얻을 때 까지 모든 가능성을 시도하는데, 완전 탐색과의 다른 점은 "신경쓰지 않아도 되는 수는 배제한다." 는 큰 차이점이 있다.
내가 원하는 답을 찾을 때 까지 탐색하며, 만약 해당 길을 통해 답을 찾을 수 없다면, 가능한 이전 길까지 돌아가서 다음 길을 찾는 방법을 채택하게 된다.

주요 전략

퇴각기법을 풀이 할 때는, 전략이 중요하다. 동적계획법의 경우, 주요 전략이 "1. 점화식을 찾고, 2. 재귀로 표현한다." 2가지 였다면, 퇴각기법에는 총 3가지 주요 전략이 존재한다.

1. Choices, 선택

먼저, 어떤 선택을 할지 결정해야 한다. 본문 상단에 언급한 바와 같이, 해를 얻을 때까지 모든 가능성을 시도하는데, 어떤 시도를 할지 결정해야 한다. 완전탐색은 정말 모든 수를 탐색하지만, 백트래킹은 내가 할 수 있는 모든 가능성만 시도하기 때문에 차이가 있다. 즉, 내가 현재 선택한 답은 유효하다고 가정한다.

2. Constraints, 제약 조건

그 다음으로, 내가 이 선택을 했을 때 어떤 제약이 발생할 지 알아야 한다. 답을 찾기 위해 탐색할 때, 나의 선택을 방해하는 제약조건이 무엇인지를 명확히 정의해야 내 선택으로부터 정답까지 다가갈 수 있다.

3. Goal, 목표

마지막으로 내가 풀고자 하는 문제를 정의해야 한다. 내가 지금 풀고자 하는 문제의 목표가 무엇인지 정의하지 않는다면, 문제를 푸는 의미가 없기 때문이다.

탐색 방법

퇴각기법의 탐색은 보통 재귀로 표현한다. 이 때, 다음과 같은 탐색을 따르는 것이 좋다.

1. 선택
2. 조건 확인
3. 선택 취소

이 때, 1번과 2번의 순서는 바뀌어도 무방하다.

우선, 어떤 답을 선택한 뒤, 해당 답이 제약조건에 위배되는지 확인한다. 위배되지 않는다면, 해당 답은 유효하다 가정하고, 다음 선택을 진행, 풀이를 반복한다.
해당 선택에 대한 풀이가 끝에 도달하면 선택을 취소하는데, 그 이유는 해당 선택이 다른 선택으로부터 도출되는 경로에서는 "정답"이 아닐 수도 있고 따라서 해당 선택을 계속 유효한 상태로 둔다면, 다른 정답이 옳바른 정답을 찾는데 방해될 수 있기 때문이다.

N Queen 예시

N Queen은 N*N체스보드 위에서 퀸 끼리 서로 공격할 수 없는 곳에 위치시켜 각 N열 혹은 N행마다 적어도 하나의 퀸을 위치시키는 문제다. 퀸은 체스보드 위에서 가로, 세로, 대각선 방향으로 이동할 수 있으며, 이 위에 상대 말이 있다면 해당 말을 잡아먹을 수 있다.
다음 그림처럼 4*4 (1~4, 1~4) 체스판이 있다하자.

이 때, 첫 칸에 퀸이 존재한다면, 다른 퀸은 초록색 사각형에 걸쳐진 위치에만 존재할 수 있다. 다음 줄 예를 들어보자.

왼쪽 사진을 보면, (2, 3)의 위치에 퀸을 두게 되면 나머지 3, 4번째 줄에 퀸을 놓을 수 없게 되고, (2, 4)의 위치에 놓았을 때 주황색과 같은 위치에 놓을 수 있게 된다. 하지만, 이 경우 마찬가지로 (3, 2)에 퀸을 위치시키게 되면 4번째 위치에는 퀸을 놓을 수 없으므로 정답을 찾을 수 없다.
이 때, 이전 선택인 (2, 4)로 돌아가 다음 (3, i)를 선택하는데, 다른 선택은 존재하지 않으므로 (1, 1)로 돌아가 (2, i)를 선택한다. 하지만 마찬가지로, (1, 1)에서 할 수 있는 선택은 모두 소모되었으므로, 최종적으로 퀸은 (1, 1)에 놓을 수 없다고 판단하여 (1, 2)에서부터 같은 탐색을 진행한다.

전략 풀이

1. Choices: 퀸을 놓을 자리
2. 제약조건: 앞으로 놓을 퀸에 대하여, 가로, 세로, 대각선에 대해 위배하는가? 이 때, 가로는 어차피 놓을 수 없기 때문에 제외한다.
3. 목표: 각 N줄 마다 퀸이 존재하도록 위치를 잘 정한다.

1. Chocies

N 보드에 대해, 한 줄 마다 퀸을 놓을것이며, 따라서 다음과 같은 생김새를 갖는다.

FOR i = 1 TO N
board[currentColumn] = i
IF constraints(board, currentColumn) THEN
findNext(board, currentColumn+1)
END IF
board[currentColumn = 0
END FOR

이 때, currentColumn은 현재 내가 찾고 있는 줄이고, constraints는 제약조건을 검사하는 함수, findNext는 답을 찾는 함수다.

2. Constraints

제약조건은 세로, 대각선에 대해 검사하면 되고, 따라서 다음과 같은 생김새를 갖는다.

FOR i = 1 TO col
IF board[i] == board[col] THEN
return FALSE
ELSE IF | col - i | == | board[col] - board[i] | THEN
return FALSE
END FOR

return TRUE

i ~ col 까지 반복하는 이유는, 내 다음 줄에는 퀸이 없고, 따라서 다음줄에 존재하는 퀸으로 하여금 내 이동에 제약이 생기지 않기 때문이다.
세로검사는 이전 줄의 queen이 나와 같은 행에 존재하는지 검사하면 된다.
그 다음으로 대각선의 위치를 검사하는데, col - i는 현재 내 행과 다른 행의 떨어진 거리가 실제 내 퀸이 놓인 위치와 해당 열에서 퀸이 어디에 존재하는지 의 거리를 검사하면 된다.

예를 들어, (3, 4)에 퀸이 위배되는지 검사한다고 가정하자. 이 때 i의 값은 1~4, col의 값은 3이 된다. 내가 대각선에 있는 것을 알기 위해서는 다음 행에 대해, 바로 다음 열(1) + 1 혹은 - 1, 혹은 그 다음 열(2) +2 혹은 -2, ... 의 값에 존재하는지 확인하면 된다.

대각선 구하는 방법
1행: 열에 대해 +1, -1
2행: 열에 대해 +2, -2
3행: 열에 대해 +3, -3

열 = |행|의 값 이해가 안간다면 직접 그려보자.

예를 들어, (3, 4)에 퀸이 위배되는지 검사한다고 가정하자. 이 때 i의 값은 1~4, col의 값은 3이 된다. 내가 대각선에 있는 것을 알기 위해서는 다음 행에 대해, 바로 다음 열(1) + 1 혹은 - 1, 혹은 그 다음 열(2) +2 혹은 -2, ... 의 값에 존재하는지 확인하면 된다.

대각선 구하는 방법
1행: 열에 대해 +1, -1
2행: 열에 대해 +2, -2
3행: 열에 대해 +3, -3

열 = |행|의 값 이해가 안간다면 직접 그려보자.

남은 것은 탐색

이제 탐색을 수행하면 된다. 코드작성의 경우, 알고리즘 문제풀이에서 진행하도록 하겠다.
잊지 말자!

"선택 → 제약 → 목표" 그리고 "선택 → 제약 → 선택취소"

드디어 첫 알고리즘과 관련된 게시글을 작성한다! (짝짝짝)

동적 계획법, 말만 들으면 무슨말인지 모르겠다. 느낌적으로는 뭔가 활발하게(?) 바뀌는 느낌인데, 다음과 같은 프로그래밍을 칭한다.

하나의 문제를 여러 문제로 나누어 푸는 방법

예를 들어서, 우리가 1~10까지의 합을 계산할 때, 하나의 문제는 다음과 같이 존재한다.

1+2+3+...+8+9+10 = 55
- 물론 n*(n+1) / 2 로 풀 수도 있다. 그치만 그게 중요한게 아니니까!

이를 여러 문제로 나누게 되면, 다음과 같이 바뀌게 된다.

1+2 = 3
1+2+3 = 3+3 = 6
1+2+3+4 = 6 + 4 = 10
1+2+3+4+5 = 10 + 5 = 15
1+2+3+4+5+6 = 15 + 6 = 21
...
1+2+3+...+8+9+10 = 45 + 10 = 55

왜?

동적 계획법은 문제를 빠르게 풀 수 있다는 장점이 존재한다. 위에서 예로 든 1~10까지의 합을 계산 할 때, 마지막 합을 계산할 때 이미 앞 단계의 합은 계산되어 있는것을 알 수 있다. 즉 1~N까지의 합을 구하기 위해 O(n)만에 풀 수 있는 것이다.

동적 계획법을 이미 알고 있는 사람이라면, 어? 예시가 잘못 된거 아니야? 원래 1~N까지의 합은 O(n)안에 풀리는데? 라고 생각할 수 있다.

물론 맞는말이다! 하지만, 동적 계획법을 모르는 사람이 공부를 시작한다면, 처음부터 피보나치, 연속 합, 합 만들기, 파도반 수열, 길 찾기, ... 등으로 예시를 든다면, 처음부터 이해가 안갈 것이고, 따라서 정~~말 쉬운 것부터 풀어보고자 위의 예시를 들었다.

N단계를 풀 때, 이미 N-1단계는 계산되어 있다.

피보나치 수열

항: (0) 1 2 3 4 5 6  7   8 ...
수: (0) 1 1 2 3 5 8 13 21 ...
점화식 F
Fn+2​= Fn+1​+ Fn​ = Fn-2 + Fn-1

피보나치 수는 앞 선 두 항의 합이 현재 항이 되는 수열을 나타낸다. 다시말해 F(6)을 풀기 위해서는 F(6) = F(5)+F(4)에 대한 연산을 수행해야 한다. 이를 동적계획법을 사용하지 않고 나타낸다면, 다음과 같은 연산이 필요하다.

사람같은 경우에 F(5) = 5라는 것을 직감적으로 알 수 있지만, 컴퓨터는 모른다. 따라서 매 번 요청 할 때마다 연산을 수행해야 한다.

해당 트리를 잘 보면, 2를 연산하기 위해 1, 0을 호출하고, 3을 연산하기 위해 2, 1을 호출하고, ..., 겹치는 연산이, 재귀적인 호출이 굉장히 많다. 또한 이 연산을 위한 시간 복잡도를 계산해 보면 O(2^n)이라는 큰 복잡도를 가진다.

Tree의 Height = Depth = 5
Tree의 Level이 증가함에 따라(Height가 감소함에 따라) Fib(N)의 N이 하나씩 줄어들고, 결국 N을 계산하기 위해 각 레벨에서 N - 1씩 연속적으로 호출한다.
N => N-1, N-2 => (N-2, N-3), (N-3, N-4) => ( (N-3, N-4), (N-4, N-5) ), ( (N-4, N-5), (N-5, N-6) ) ...
→ N에 대하여 2^n 만큼 증가!

이러한 시간복잡도를 줄이기 위해(문제를 해결하기 위해) 동적 계획법을 사용하면 꽤나 빠른 시간 안에 연산할 수 있다.

동적계획법을 활용하지 않으면, 사라진 노드들에 대해 일일히 모두 계산해줘야 하지만, 동적계획법을 사용함으로써 fib(3)의 값이 2임을 이미 알고있고, 따라서 fib(3)의 연산을 추가적으로 하지 않은 것을 확인할 수 있다.

// fibonacci 연산 값을 저장할 배열
int[] fibonacci;

// fibonacci 값을 연산하는 함수
func setfib(limit)
  fibonacci[0] = 0;
  fibonacci[1] = 1;
  for i -> 2 to limit
    fibonacci[i] = fibonacci[i-2] + fibonacci[i-1];
  end for
end func

// 찾고자 하는 피보나치 수를 반환하는 함수
func getfib(N)
  return fibonacci[N]

시간복잡도는 O(n)안에 풀 수 있다.

그 이유는..위 트리를 보세요..ㅎㅋㅎㅋ

정리하면서,

우선

동적 계획법을 사용하려면, 풀고자하는 문제의 점화식(규칙)을 찾아야한다. 위에서 예로 든 피보나치의 경우, F(N) = F(N-2) + F(N-1)과 같은 식 말이다.

문제마다 식이 다르기 나오기에, 어떻게 해라! 라는게 딱히 없다. 다만, 규칙을 찾을 때 까지 수를 나열해 보거나, 문제로부터 힌트를 얻는 방법 밖에 없다.

피보나치와 같은 문제는 수를 나열하며 규칙을 찾을 수 있을 것이고, Working Days Problem과 같은 경우에는, 문제로부터 힌트를 얻을 수 밖에 없다. (하루 건너 일할 때 가장 돈을 많이 버는 경우는 마지막 날에 일을 하냐 안하냐로 판단할 수 있는것 처럼.)

끝으로

동적 계획법은 다음과 같은 문제를 풀 때 사용하면 좋다.

1. 중복되는 풀이를 할 때
2. 재귀로 풀면 시간 복잡도가 클 때

오늘은 백준 2775번 부녀회장이 될테야 풀이를 할 예정이다. 그간 이런저런 일이 많아서 블로그에 소홀했는데,, 여튼! 시작해보자

바로 본론으로 들어가서,,

a층 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들 수의 합만큼 사람들을 데려와 살야아 한다. 이 때, 0층 N호에는 총 N명이 산다.
→ 0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.
→ 1층 3호에 살려면 6명, 2층 3호에 살려면 10명을 데려와 살아야 한다.

문제에 따르면 1층 3호에 살려면 6명은 다음과 같이 구해진다

(1-1)층 1호~3호까지 사람의 수의 합 = 0층 1호 + 0층 2호 + 0층 3호 = 1 + 2 + 3 = 6명 이다.

마찬가지로, 2층 3호의 사람을 구해보면 (2-1층) 1호~3호까지 사람 수의 합 = 1층 1호 + 1층 2호 + 1층 3호 = 1 + 3 + 6 = 10명

잘 보면, subtree가 반복되는걸 확인할 수 있다. 만약 3층 4호, 5층 6호 ... 로 확장해 나갈수록, k-1, k-2, k-3, ... (k-m >= 0)이 반복되고 이에 대응하는 n호에 대한 사람 수도 subtree에서 반복되어 나타날 것이다. (만약 머리에 안그려진다면, 직접 그려서 확인하는걸 추천한다.)

subtree가 반복될 때 우리는 Dynamic Programming을 통해 쉽게 해당 문제를 풀 수 있다. 층에 대한 사람 수를 결정해 놓고, 해당 호수를 출력하면 문제 풀이는 끝이난다.

→0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.

위 조건에 맞게, 1호~14호 까지는 1~14의 값을 넣어주고, 이후 층 부터 (k-1)층 n호에 대한 사람 수를 불러와 더해주면 된다.

문제 풀이를 위해 1차원 배열을 선언하고, 14개씩 끊어서 하나의 층을 표현할 예정이다.

        for(int i = 14; i < rooms.length; i++){
            int floor = i / 14;
            int number = (i % 14) + 1;
            int underFloor = floor-1;
            int underValue = 0;
            for(int j = 0; j < number; j++){
                underValue += rooms[underFloor * 14 + j];
            }
            rooms[i] = underValue;
        }

따라서 위의 표정을 보면, 층수는 ( i / 14 )의 값을 갖게 되고, 호수(number)는 ( i % 14 ) +1이 된다. 1을 더해준 이유는, 실제 호수는 0~13이 아닌 1~14호기 때문이다.

이후 아래층의 1호~number호 까지의 방에 살고있는 사람수 (underValue)를 계산한다. 이 때, underFloor*14인 경우는 1차원 배열로 선언했기 때문에, 바로 아래층의 위치를 구하기 위해 14를 곱해줘야 하기 때문이다.

최종 코드

public class Number2775 {
    public static void main(String[] args) throws IOException {
        int[] rooms = new int[15*14];
        for(int i = 0; i < 14; i++){
            rooms[i] = i+1;
        }
        for(int i = 14; i < rooms.length; i++){
            int floor = i / 14;
            int number = (i % 14) + 1;
            int underFloor = floor-1;
            int underValue = 0;
            for(int j = 0; j < number; j++){
                underValue += rooms[underFloor * 14 + j];
            }
            rooms[i] = underValue;
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());
            System.out.println(rooms[k * 14 + (n-1)]);
        }

    }
}

rooms의 배열이 14 * 14가 아닌 이유는, 아파트의 층수가 0층~14층까지 존재하기 때문에 총 15개의 층에 대해 연산해야 하기 때문이다.

결과는.. 정답!

오늘은 백준 벌집 문제를 풀거다. 한번에 맞추지 못했다. 배열 써서 풀려 했는데, 이유 모를 OutOfBounds 오류와 배열 사용으로 인한 메모리 초과 오류가 발생했다. 심지어 정답직전에 테스트 출력까지 포함해버려서 (...) 총 6번의 리트만에 정답... OutOfBounds는 도저히 내 컴퓨터에서 재현이 안된다... 1~10억까지 다 넣어봤는데..난 안난다....

벌집 문제

문제를 딱 보면, "... 최소 개수의 방을 지나서 갈 때 ..."로 인해 Shortest Path를 찾는 것인가 싶다.
하지만 그림을 잘 보면, 규칙이 있다.

이 규칙을 찾았으면, 다음 규칙도 보인다.

벌집의 겉에는 원자의 전자껍질과 같은 구조를 발견할 수 있다. 심지어 해당 껍질은 등비수열을 이룬다. 그리고 제일 안쪽 껍질은 무조건 밟아야 함에 착안해서, 두 번째 껍질의 시작을 1로 맞춰주면 문제를 풀기 더 쉽다.
$$ a_n = 6^{(n-1)} $$
벌써 문제를 다 풀어버렸다.

입력값으로 N이 주어지고, 해당 N까지의 거리를 구해야 한다. 껍질의 시작을 1로 맞춰주기로 했으니, 입력값 N에서 1을 빼준다.

N = N - 1 ~> 두 번째 껍질의 시작을 1로 맞춰주기 위함

그리고 껍질의 층 수를 나타내는 변수 base와 껍질을 벗겨내는 반복자를 이용하여 한 층 씩 벗겨내면 된다. 벌집의 방 번호는 항상 양수이기 때문에, 현재 껍질이 음수가 되어서는 안된다.
이를 위한 연산을 입력값과 벗겨낼 껍질 층으로 구할 것이다. 입력 값을 N, 반복자를 i라 할 때, 다음과 같다.

입력 값: N
현재 껍질 수: i
현재 껍질 층: base

다음 껍질 수 i = i + 6 * (base+1);
남은 입력 값 N = N - i

위 내용을 바탕으로 수도코드로 정리하면 이렇게 된다.

WHILE ( N - i >= 0) THEN
i = i + 6 * (base);
base += 1;
END WHILE

이후 While문이 종료되면 base는 입력 값 N에 대한 껍질 층이 반환되고, 이 값은 1로부터 얼마나 떨어져있는지가 된다.

최종 코드

import java.util.Scanner; public class Number2292 { public static void main(String[] args){ Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int temp = N-1, base = 1, i = 1; while(temp - i >= 0){ System.out.print("bef: " + i); i += 6 * (base++); System.out.println(", aft: " + i + ", cal: " + temp); } System.out.println(base); } }

결과는 정답!

오늘은 백준 1152번 풀거다! 와 이게 쉬운데 함정이 많더라구요.

저처럼 문제 대충 쓱 보고 풀면 틀려요!

ㅋㅋㅋ 문제만 보고 예제를 제대로 보지도 않고 그냥 '그냥 공백으로 자르면 되는거 아닌가..?' 하고 바로 냈더니 바로 "틀렸습니다" ... 

그래서 예제를 살펴봤더니, 예제 입력 2를 보면 다른 녀석들과는 다르게 제일 앞에 공백이 있는거에요! " Maza..." 그래서 아~ 이런~ 하고 제일 앞이 공백일때만 처리해줬더니 또 다시 보기 좋게 "틀렸습니다" ... 

아 도대체 이 문제에 어떤 예외를 넣었을까 열심히 또 돌려봤죠. 그러고서 알아냈어요.. 역시 처음부터 쉽게보면 안돼요.. 모든 문제는 이유가 있어요..

서론이 너무 길었어요! 그냥 부끄러워서..

문제는 쉽습니다. 제가 생각했던 것과 마찬가지로 공백으로 자르면 돼요. 하나하나 들어가 볼게요!

...  단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다.

우선 단어는 띄어쓰기 한 개로 구분이 되니, 원래 제 시도처럼 공백으로 자르면 됩니다.

1. 띄어쓰기를 통해 문자열을 구분짓는다.

문제는 바로 빨간줄로 표시한 '공백이 연속해서 나오는 경우는 없다.'에요. 공백이 연속해서 나오진 않지만, 바로 그 뒤를 보면 '문자열의 앞과 뒤에는 공백이 있을 수도 있다.' 그냥 말장난인것같긴 한데,,

정리해 보면 다음과 같아요.

1. 띄어쓰기를 통해 문자열을 구분짓는다.
- apple banana chocolate
2. 문자열 앞과 뒤에는 공백이 있을 수 있다.
- apple  banana chocolate
-  apple banana chocolate
- ...
3. 공백이 연속해서 나오는 경우는 없다.
-  apple   banana (불가능)

즉 3번은 안되지만, 2-1번과 같이 문자열 뒤, 그리고 문자열 앞 에 존재하는 각각의 공백은 겹칠 수 있어요!

따라서 우리는 공백으로 문자열을 자를 때, 잘라진 문자열에 대한 배열이 비어있는지 확인해 주면 끝입니다.

2-1번에 대하여 우리가 공백으로 문자열을 자르면, 다음과 같은 형상이기 때문입니다.

[0]: apple
[1]: 
[2]: banana
[3]: chocolate

최종코드

import java.util.Scanner;

public class Number1152 {
    public static void main(String[] args){
        String[] str = new Scanner(System.in).nextLine().split(" ");
        int count = 0;
        for(int i = 0; i < str.length; i++)
            if(!str[i].isEmpty())
                count++;
        System.out.println(count);
    }
}

끝!

갤럭시 Z Flip LTE 화면이 깨져서 고치고 왔다.

코로나때문에 액정 재고가 없어서, 7월 20일즈음 재고 예약을 했고, 오늘 도착했다는 연락이 와서 다녀왔다.

내가 수리한 부품은 액정, 메인보드, 카메라 글라스, 뒷판 글라스 2개 이렇게 5개다. 그런데 액정에는 테두리, 배터리, 힌지가 일체형이라 같이 교체된다.

메인보드도 수리하겠다고 말하니, 기사님께서 "메인보드는 증상이 어떠시길래 고치시나요?" 라고 물어보셨고, 너무 뜨겁다 했더니 원래 뜨겁다더라. 그래서 "혹시 수리 안된다 하면 물에 빠트려서 다시 갖고올거에요! 지금 물에 적셔올까요?"했더니 놀라셔서 아니라고 수리 해주겠다 하시더라.

문제가 있었는데 삼성케어플러스를 구독중인데, 삼성서비스센터에서 가입조회가 안된다더라.. (...)

그래서 내 계정으로 로그인 하고 결제 내역과 가입 사실을 보여주니, 고객님이 가입되어 있는건 사실이니 수리하고, 해당 사실을 관련 부서에 연락해서 알아보도록 하겠다더라.

뭐.. 어쩌겠나.. ㅋㅋ

전준태를 갖추고, 알았다고 답변한 뒤 수리를 기다렸다. 나중에 여쭤보니 중간에 누락된것같다고 죄송하다고 말씀주셨다.

와 ㅋㅋ 삼케플 없었으면 77만원 내고 고쳐야 했다..ㅋㅋㅋㅋ

여튼 새로 태어난 내 플립을 받아들고, 집에왔다.

태생적으로 이 아이는 약하고 여리고 여러모로 정말 별로인 아이라, 일단 기스가 잘 안나게 외부 필름을 붙여줬다. 예쁜걸로..

이건 못참지 ㅋㅋㅋㅋㅋㅋㅋㅋ

스티커 붙였더니 칙칙한 그 검정이 아니라, 좀 상큼(?)해졌다! 붙이는 난이도는 있었지만, 그래도 뭐 재밌으면 됐다.

빨리 플립을 처분하고, 다른 폰 쓰고싶다.. 너무 뜨겁고,, 배터리도 너무 빨리닳고,,, 여러모로 정말 별로인 아이.... 이 폰을 쓰고 처음으로,, 아이폰이 쓰고싶어졌다....(?)..

MkAuthToken을 개발하긴 했는데,, Node와는 너무 다른 그것이기 때문에 살짝 사용법을 정립하기가 어려웠다.

JWT 특성상 서버에서는 단지 토큰 생성, 검증만 수행하기 때문에 모든 관리를 클라이언트가 해야하는 부담이 있고, MkWeb은 프론트 개발자가 최대한 이러한 활동에 집중하지 않게 하자는 목표가 있었기 때문에 더욱 그러했다.

하지만, JWT를 사용하기로 결정했고, 따라서 "클라이언트에서 이를 관리할 필요가 있다." 고 결론을 내렸다.

그럼 어떻게 Client에서 사용하게 할 것인가를 고민해 봤는데, html에서 지원하는 cookie를 이용하여 저장할 예정이다.

먼저 토큰을 생성하자.

JWT를 저장하려면 우선 JWT가 생성되어 있어야 한다. 로그인과 같은 행위를 통해 JWT를 발급받아고, 해당 토큰 값을 내가 알고 있어야 한다.

서버를 배포할 때 설정한 mkweb.auth.uri를 통해 (ajax를 사용하든 어떤 방법이 되었든...) token을 생성하자. (이 때, 모든 처리는 method: POST, Cotent-Type: application/json 이어야 한다.)

$("#login").click(function(){
	$.ajax({
		type : "POST", 
		url : "/auth/login",
		dataType : "json",
		data : {
        	"user_id" : $("#userid").val(),
			"user_pw" : $("#userpw").val()
		},
		success : function(rd){
			if(rd.token){
				...
			}
		}     
	});
});

토큰생성에 성공했다면, ajax결과로 다음과 같은 형식의 데이터를 전달받는다.

{"code": 200, "token":"your_token"}

이 후, document.cookie를 통해 토큰 값을 저장한다.

$("#login").click(function(){
	$.ajax({
		...
		success : function(rd){
			if(rd.token){
				document.cookie = createCookie(token);
			}
		}     
	});
});

let __MK_TOKEN_LIFETIME__ = 600;
let __MK_TOKEN_NAME__ = 'mkauthtoken';

function createCookie(token){
    var date = new Date();
    date.setTime(date.getTime() + __MK_TOKEN_LIFETIME__ * 1000);
    let cookieInfo = __MK_TOKEN_NAME__ + '=' + token + ';expires=' + date.toUTCString() + ';path=/';
    return cookieInfo;
}

토큰의 사용

토큰을 구하고, 삭제하는 방법은 다음과 같다.

function getToken(cookieInfo){
    var value = document.cookie.match('(^|;) ?' + __MK_TOKEN_NAME__ + '=([^;]*)(;|$)');
    return value ? value[2] : null;
}

function removeTokenCookie(cookieInfo) {
    var date = new Date();
    document.cookie = __MK_TOKEN_NAME__ + "= ; expires=" + date.toUTCString() + "; path=/";
}

주의사항

let __MK_TOKEN_LIFETIME__ = 600;
let __MK_TOKEN_NAME__ = 'mkauthtoken';

자바스크립트에 작성된 위 두 옵션은 MkWeb.conf에 설정된 mkweb.auth.lifetime, mkweb.auth.controller.name 두 속성과 일치하는 값을 가져야 한다.

꼭 JSP / HTML일 필요는 없다!

React 등 프론트 개발을 위해 다른 프레임워크 / 라이브러리를 사용해도 서버를 MkWeb을 이용할 때, 단지 프론트에서 토큰을 잘 가지고 있기만 하면 된다! 나는 프론트 개발은 HTML + Javascript + Css 밖에 안해봤기 때문에,, ㅎㅎ

GET, HEAD, OPTIONS only allow URI options
PUT allow URI options for condition, body parameter for update
DELETE allow body parameter for deleting
POST allow body parameter

기타 pretty, paging 등 : QueryString

키는 기본적으로 Authorization에 포함되어야 하지만, HTTP조회일 경우도 있기 때문에 query string을 예외적으로 허용.

Content-Type이 application/json이 아닐 경우, 거부