투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구한다.
start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같으며, end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장한다는 의미이다. 같을 때는 1 증가시키고 end_index를 오른쪽으로 이동한다.
while(end_index != N) 일 때까지 반복
sum > N : sum = sum - start_index; start_index++;
sum < N : end_index++; sum = sum sum + end_index;
sum == N : end_index++; sum = sum + end_index; count++;
2. 2개를 가지고 전체를 탐색하는 투 포인터 이동 원칙
오름차순으로 정렬해야된다.
while( i < j )
A[i] + A[j] > M : j--; -> 번호의 합이 M보다 크므로 큰 번호 index를 내린다.
A[i] + A[j] < M : i++; -> 번호의 합이 M보다 작으므로 작은 번호 index를 올린다.
A[i] + A[j] == M : i++; j--; count++; -> 양쪽 포인터를 모두 이동시키고 count를 증가시킨다.
컨테이너를 종료하지 않은 채 터미널에서 입력을 계속해서 컨테이너로 전달하기 위해 이 두 옵션을 사용합니다.
-it 옵션은 컨테이너의 쉘(shell)이나 CLI 도구로 사용할 때 유용하게 사용된다.
docker run --name web -d -p 80:80 nginx
--name 옵션을 사용해서 컨테이너에 이름을 만들고 해당 이름으로 컨테이너를 식별할 수 있다.
-d 옵션을 사용하면 컨테이너가 detached 모드에서 실행된다. 컨테이너를 백그라운드에서 실행하고 싶을 때 쓰는 명령어이다.
-p 옵션은 호스트와 컨테이너 간의 포트(Port) 배포(publish)/바인드(bind)를 위해 사용된다.
호스트(host) 컴퓨터에서 컨테이너에서 리스닝하고 있는 포트로 접속할 수 있도록 설정해준다.
2. 도커 파일을 만들고 도커 허브에 배포까지
도커 파일이란 도커 이미지를 만들기 위한 설정 파일입니다. 여러 가지 명령어를 사용하여도커 파일을 작성하면 설정된 내용대로 도커 이미지를 만들 수 있습니다.
2-1. 도커 파일의 기본 문법
#
comment를 남길때 사용한다.
FROM
컨테이너의 베이스이미지(운영환경), 기반이 되는 이미지 레이어입니다.
MAINTAINER
이미지를 생성한 사람의 이름 및 정보
LABEL
컨테이너 이미지에 컨테이너의 정보를 저장
RUN
도커이미지가 생성되기 전에 수행할 쉘 명령어
COPY
컨테이너 빌드시 호스트의 파일을 컨테이너로 복사
ADD
컨테이너 빌드시 호스트의 파일을(tar, url포함) 컨테이너로 복사
WORKDIR
컨테이너 빌드시 명령이 실행될 작업 디렉토리 설정
ENV
환경변수 설정
USER
명령 및 컨테이너 실행시 적용할 유저 설정
VOLUME
파일 또는 디렉토리를 컨테이너의 디렉토리로 마운트
디렉터리의 내용을 컨테이너에 저장하지 않고 호스트에 저장하도록 설정합니다.
데이터 볼륨을 호스트의 특정 디렉터리와 연결하려면 docker run 명령에서 -v 옵션을 사용해야 합니다.
ex) -v /root/data:/data
EXPOSE
컨테이너 동작 시 외부에서 사용할 포트 지정
CMD
컨테이너 동작 시 자동으로 실행할 서비스나 스크립트 지정
ENTRYPOINT
CMD와 함께 사용하면서 command 지정 시 사용
2-2. 도커파일 만들고 배포까지
hellojs라는 폴더를 만들고 그 폴더 안에 들어가서 dockerfile을 만들려고 한다.
dockerfile을 만들고 위에 내용을 입력한다.
그리고 hello.js라는 파일을 만든다.
hello.js라는 파일은 node.js파일이며 컨테이너의 os.hostname을 확인하는 파일입니다.
docker build -t hellojs .
dockerfile을 이미지로 만들기 위해 docker build 작업을 해야 된다.
마지막. 은 호스트의 작업 디렉터리 경로 → 컨테이너 이미지가 만들어진 것
빌드가 진행 중인 화면입니다.
다음으로 webserver라는 폴더를 만들고 그 폴더에 도커 파일을 만듭니다.
도커 파일은 우분트로 되어있으며 도커가 실행될 때 아파치를 설치하고
아파치를 설치하면 /var/www/html/index.html을 찾아서 클라이언트에게 서비스해주게 된다.
따라서 /var/www/html/index.html에 TEST WEB이라는 이름의 파일을 저장시켰다.
이 컨테이너가 서비스해주는 포트를 알려주는 EXPOSE에 80번으로 설정했다.
CMD에는 아파치를 설치하고 나면 그 컨테이너 안에는 /usr/sbin/apache2ctl이라는 바이너리가 생긴다.
아파치 웹서버를 동작시켜주는 데몬이 생긴다. 아파치를 실행할 때는 -DFOREGROUND라는 옵션을 써줘야 된다.
docker build 명령어로 webserver를 build 중인 화면이다.
webserver와 hellojs가 정상적으로 이미지로 만들어진 것을 확인하실 수 있습니다.
Hash 맵을 이용 해서 푸는 문제이다. HashMap을 이용해서 <String, String>으로 받아 key와 vlaue를 두 개를 저장을 한다. 하나는 i를 String으로 바꿔서 key, 포켓몬 이름은 value를 넣어주고 다른 하나는 두 개를 바꿔서 저장을 한다. 답의 출력을 받을 때 받은 것이 숫자인지 문자인지 판별하는 메서드를 만들어서 true, false로 반환한다. 그리고 StringBuilder를 이용하여 정답을 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1620 {
static String str;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
HashMap<String, String> map = new HashMap<>();
for(int i = 1; i <= n; i++) {
String ss = br.readLine();
String num = Integer.toString(i);
map.put(num, ss);
map.put(ss, num);
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < m; i++) {
str = br.readLine();
if(isInteger()) {
sb.append(map.get(str) + "\\n");
}
else {
sb.append(map.get(str) + "\\n");
}
}
System.out.println(sb.toString());
}
private static boolean isInteger() {
for(int j = 0; j < str.length(); j++) {
if(Character.isDigit(str.charAt(j))) {
return true;
}
}
return false;
}
}
문제점
실버 4의 문제이고 쉬운 문제라고 생각했다. 문제를 푸는데는 어려움이 없었지만 계속 시간 초과가 발생했다. 숫자인지 판별해주는 메소드를 만들지 않았고 문제를 풀 때 map에 key, value 하나만 저장해 vlaue를 이용해 key값을 가져오려고 하였다. 여기서 시간 초과가 발생했다. 방법이 떠오르지 않아 이를 key, value를 바꿔서 하나 더 저장하는 아이디어를 검색을 해서 찾았습니다.
오늘의 회고
오늘은 쉬운 알고리즘 문제 한문제를 풀고 그동안 풀었던 알고리즘 개념을 다시 정리하면서 블로그에 작성하려고 합니다. 반복적인 복습과 꾸준한 학습으로 점점 더 발전하는 개발자가 되겠습니다.
어제 배운 플로이드-위셜 기본 문제이다. 모든 노드 쌍에 관해 경로가 있는지 여부를 확인하는 방법은 플로이드-위셜 알고리즘을 수행해 결과 배열을 그대로 출력하면 된다. 입력 데이터를 인접 행렬에 저장한다. s와 e가 모든 중간 경로(k) 중 1개라도 연결돼 있다면 s와 e는 연결 노드로 저장한다. 변경된 인접 행렬을 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11403 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int k = 1; k <=n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(arr[i][k] == 1 && arr[k][j] == 1) {
arr[i][j] = 1;
// k를 거치는 모든 경로 중 1개라도 연결돼 있는 경로가 있다면 i와 j는 연결 노드로 취급
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
63번 케빈 베이컨의 6단계 법칙
내가 떠올린 풀이 해설
BFS를 이용해서도 풀 수 있는 문제이다. 이 문제를 풀기 위해 몇가지 아이디어가 필요하다. 1번째로 사람들이 직접적인 친구 관계를 맺은 상태를 비용 1로 계산하는 것이다. 즉 가중치를 1로 정한 후 인접 행렬에 저장한다는 의미이다. 또한 플로이드-위셜은 모든 쌍과 관련된 최단 경로이므로 한 row의 배열 값은 이 row의 index값에서 다른 모든 노드와 관련된 최단 경로를 나타낸다고 볼 수 있다. 즉 i번째 row의 합이 i번째 사람의 케빈 베이컨의 수가 된다는 뜻이다.
먼저 인접 행렬을 생성한 후, 자기 자신이면 0, 아니면 충분히 큰 수로 인접 행렬의 값을 초기화한다. 그리고 친구 관계 정보를 인접 행렬에 저장한다. i와 j가 친구라면 arr[i][j] = 1, arr [j][i] = 1로 값을 업데이트한다. 플로이드-위셜 3중 for문으로 모든 중간 경로를 탐색한다. 케빈 베이컨의 수를 비교해 가장 작은 수가 나온 행 번호를 정답으로 출력한다. 같은 수가 있을 때는 더 작은 행 번호를 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1389 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] arr = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) {
arr[i][j] = 0;
}
else {
arr[i][j] = 1000001;
}
}
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
arr[s][e] = 1;
arr[e][s] = 1;
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
int sum = 0;
int answer = Integer.MAX_VALUE;
int index = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
sum += arr[i][j];
}
if(answer > sum) {
answer = sum;
index = i;
}
sum = 0;
}
System.out.println(index);
}
}
오늘의 회고
오늘은 어제 배운 플로이드-위셜 문제를 풀고 최소 신장 트리(MST) 이론을 학습하였습니다. 최소 신장 트리를 코드로 나타내는 것에 어려움을 많이 느꼈습니다. 주말에는 지금까지 풀었던 문제 복습과 배웠었던 알고리즘 이론들을 까먹지 않고 반복적으로 보기 쉽게 블로그에 정리하려고 합니다. 오늘은 퇴사 후 1달 정도가 되었는데 처음 알고리즘을 공부하였을 때 브론즈 5였는데 오늘은 골드 5를 찍었습니다. 앞으로 더 열심히 하겠습니다.
모든 도시에 쌍과 관련된 최솟값을 찾아야 하는 문제이다. 그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구하는 알고리즘인 플로이드-위셜을 사용해야 된다. 도시의 최대 개수가 100개로 매우 작은 편이므로 O(N^3)인 플로이드-위셜을 사용할 수 있다.
버스 비용 정보를 인접 행렬에 저장한다. 연결 도시가 같으면 0, 아니면 큰 수 값으로 초기화한다. 그리고 주어진 버스 비용 데이터값을 인접 행렬에 저장한다. 플로이드-위셜 알고리즘을 수행한다. 3중 for 문으로 모든 중간 경로를 탐색한다. 알고리즘으로 변경된 인접 행렬을 출력한다. 문제의 요구사항에 따라 두 도시가 도달하지 못할 때는 0, 아닐 때는 배열의 값을 출력한다.
*플로이드 위셜-점화식
Math.min(arr[s][e], arr[s][k] + arr[k][e])
for(k -> n만큼 반복하기) { // 3중 for문의 순서가 중요함 k가 가장 바깥쪽
for(i -> n만큼 반복하기) {
for(j -> n만큼 반복하기) {
arr[i][j]에 arr[i][k] + arr[k][j] 값들 중 최솟값 넣기
i ~ j 사이에 가능한 모든 경로를 탐색하기
}
}
}
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11404 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] arr = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) {
arr[i][j] = 0;
}
else {
arr[i][j] = 10000001;
}
}
}
for(int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(arr[s][e] > v) {
arr[s][e] = v;
}
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <=n; j++) {
if(arr[i][j] == 10000001) {
System.out.print("0 ");
}
else {
System.out.print(arr[i][j] + " ");
}
}
System.out.println();
}
}
}
오늘의 회고
오늘은 플로이드-위셜 알고리즘 개념을 배웠습니다. 플로이드-위셜은 코드가 많이 어렵지 않아 쉽게 이해할 수 있었습니다. 아직 배울 알고리즘이 많이 남았습니다. 천천히 꾸준히 배워 나아가겠습니다.
