해당 방법은 깃헙 자체를 clone하는 방식이었고, 오늘은 패키지 매니저를 통해 설치하여 SSL 인증서를 발급받는 방법을 서술하려 한다.
우선 letsencrypt를 설치해주자.
$ apt-get update -y $ apt-get install letsencrypt # certbot 명령어를 작성하여 잘 설치됐나 보자. $ certbot
letsencrypt가 모두 설치되고 나면 certbot을 이용해 인증서를 발급받으면 된다. 다만, 이전글에서 소개한 manual로 작성하게 되면 자동 갱신이 불가하기 때문에, standalone으로 발급받자.
$ certbot certonly --standalone -d [도메인1] -d [도메인2] -d [도메인3] #만약 아래와 같은 에러가 발생하면, 80포트를 사용중인 웹 서버 컨테이너 (응용프로그램)을 모두 종료해주자. Problem binding to port 80: Could not bind to IPv4 or IPv6. $ certbot certonly --standalone -d test2.dev-whoan.xyz Saving debug log to /var/log/letsencrypt/letsencrypt.log Plugins selected: Authenticator standalone, Installer None Obtaining a new certificate Performing the following challenges: http-01 challenge for test2.dev-whoan.xyz Waiting for verification... Cleaning up challenges
..... 사용에 대해 동의해야 LetsEncrypt를 사용할 수 있어! (A)gree, (R)eject:
(A)gree가 뜨면 A를 입력하고, 이후 이메일을 작성하라 하는데,, 이게 난 이미 인증을 해버려서 뭐라떴는지 기억이 안난다. 여튼 이메일 작성하고, 이메일로 기타 안내를 받겠냐는 문구가 나오는데, 이거는 취향따라 Y, N하면 된다.
위키피디아의 설명처럼, 해를 얻을 때 까지 모든 가능성을 시도하는데, 완전 탐색과의 다른 점은 "신경쓰지 않아도 되는 수는 배제한다." 는 큰 차이점이 있다. 내가 원하는 답을 찾을 때 까지 탐색하며, 만약 해당 길을 통해 답을 찾을 수 없다면, 가능한 이전 길까지 돌아가서 다음 길을 찾는 방법을 채택하게 된다.
주요 전략
퇴각기법을 풀이 할 때는, 전략이 중요하다. 동적계획법의 경우, 주요 전략이 "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) 체스판이 있다하자.
4*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
열 = |행|의 값 이해가 안간다면 직접 그려보자.
남은 것은 탐색
이제 탐색을 수행하면 된다. 코드작성의 경우, 알고리즘 문제풀이에서 진행하도록 하겠다. 잊지 말자!
피보나치 수는 앞 선 두 항의 합이 현재 항이 되는 수열을 나타낸다. 다시말해 F(6)을 풀기 위해서는 F(6) = F(5)+F(4)에 대한 연산을 수행해야 한다. 이를 동적계획법을 사용하지 않고 나타낸다면, 다음과 같은 연산이 필요하다.
F(6)에 대한 연산
사람같은 경우에 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과 같은 경우에는, 문제로부터 힌트를 얻을 수 밖에 없다. (하루 건너 일할 때 가장 돈을 많이 버는 경우는 마지막 날에 일을 하냐 안하냐로 판단할 수 있는것 처럼.)
오늘은 백준 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가 반복되는 구조다.
잘 보면, 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); } }
ㅋㅋㅋ 문제만 보고 예제를 제대로 보지도 않고 그냥 '그냥 공백으로 자르면 되는거 아닌가..?' 하고 바로 냈더니 바로 "틀렸습니다" ...
그래서 예제를 살펴봤더니, 예제 입력 2를 보면 다른 녀석들과는 다르게 제일 앞에 공백이 있는거에요! "Maza..." 그래서 아~ 이런~ 하고 제일 앞이 공백일때만 처리해줬더니 또 다시 보기 좋게 "틀렸습니다" ...
아 도대체 이 문제에 어떤 예외를 넣었을까 열심히 또 돌려봤죠. 그러고서 알아냈어요.. 역시 처음부터 쉽게보면 안돼요.. 모든 문제는 이유가 있어요..
서론이 너무 길었어요! 그냥 부끄러워서..
문제는 쉽습니다. 제가 생각했던 것과 마찬가지로 공백으로 자르면 돼요. 하나하나 들어가 볼게요!
... 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다.
우선 단어는 띄어쓰기 한 개로 구분이 되니, 원래 제 시도처럼 공백으로 자르면 됩니다.
1. 띄어쓰기를 통해 문자열을 구분짓는다.
문제는 바로 빨간줄로 표시한 '공백이 연속해서 나오는 경우는 없다.'에요. 공백이 연속해서 나오진 않지만, 바로 그 뒤를 보면 '문자열의 앞과 뒤에는 공백이 있을 수도 있다.' 그냥 말장난인것같긴 한데,,
정리해 보면 다음과 같아요.
1. 띄어쓰기를 통해 문자열을 구분짓는다. - apple banana chocolate 2. 문자열 앞과 뒤에는 공백이 있을 수 있다. - applebananachocolate - apple banana chocolate - ... 3. 공백이 연속해서 나오는 경우는 없다. - applebanana (불가능)
즉 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);
}
}
