Slow And Steady Wins The Race

알고리즘 종류 : 매개변수 탐색

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1

15

예제 입력 2

5 20
4 42 40 26 46

예제 출력 2

36

매개변수 탐색이 예외상황이 있다는 것을 간과하지 말자. 항상 OOOXXX 패턴이 아닐 수 있다.

public class Main {
	private int N, M;
	private final int MAX = 1000010;
	private int[] arr = new int[MAX];

	public static void main(String[] args) throws Exception {
		Main main = new Main();
		main.start();
	}

	private void start() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr, 0, N);
		bw.write(parametricSearch(0, arr[N-1]-1) + "\n");
		bw.close();
		br.close();
	}

	private int parametricSearch(int from, int to) {
		// 절단기 높이, 1 ~ arr[len-1]
		// 적어도 M미터의 나무를 가져가기 위한 절단기 높이의 최댓값 반환.
		// O M미터 나무 획득, X M미터 나무미획득 이라고 할때,
		// OOOOXXX -> 절단기 높이가 OX 패턴에서 O에 해당하는 절단기 높이를 구한다.
        
        // 예외 상황, X인 경우가 없는 경우
	    if (isMoreThanM(to)) return to;
        
		int s = from;
		int e = to;
		while (s+1 < e) {
			int mid = (s + e) / 2;
			if (isMoreThanM(mid)) {
				s = mid;
			} else {
				e = mid;
			}
		}
		return s;
	}

	private boolean isMoreThanM(int in) {
		long sum = 0;
		for (int i = 0; i < N; i++) {
			int remainder = arr[i] - in;
			if (remainder > 0)
				sum += remainder;
		}
		return sum >= M;
	}
}

백준 : https://www.acmicpc.net/problem/2805

알고리즘 종류 : 투포인트 알고리즘

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

예제 입력1

5
-2 4 -99 -1 98

예제 출력

-99 98

Scanner 사용시에 시간초과

import java.io.BufferedReader;
import java.io.BufferedWriter;

import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	private int N;
	private final int MAX = 100010;
	private int[] numbers = new int[MAX];
	private int minSum = -2000000000;
	private int[] ans = new int[2];
	
	public static void main(String[] args) throws Exception {
		Main main = new Main();
		main.start();
	}
	private void start() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<N;i++) numbers[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(numbers, 0, N);
		twoPointerAlgorithm();
		bw.write(String.format("%d %d", ans[0], ans[1]));
		bw.close();
		br.close();
	}
	private void twoPointerAlgorithm() {
		int s = 0;
		int e = N-1;
		while(s < e) {
			int sum = update(s, e);
			if(sum > 0) {
				e--;
			} else if(sum < 0){
				s++;
			} else {
				break;
			}
		}
	}
	private int update(int a, int b) {
		int sum = numbers[a] + numbers[b];
		if(sum == 0 || Math.abs(sum) < Math.abs(minSum)) {
			ans[0] = numbers[a];
			ans[1] = numbers[b];
			minSum = sum;	
		}
		return sum;
	}
}

- https://www.acmicpc.net/problem/2470

Raspberry Pi cluster setup

- 3pc 라즈베리파이4B 모델 

- 3pc 16 GB SD card 

- 3pc ethernet cables

- 1pc 공유기

- 3pc C타입 아답터

Cluster Static ip

- master: 192.168.10.3

- worker-01: 192.168.10.4

- worker-02: 192.168.10.5

Infrastructure Setting

1. 고정 IP 설정

- vi /etc/netplan/xxx.yaml

network:
    ethernets:
        eth0:
           addresses: [192.168.10.x/24]
           gateway4: 192.168.10.1
           nameservers:
             addresses: [8.8.8.8]
    version: 2

- sudo netplan apply

2. 호스트네임 변경

# 명령어로 변경
hostnamectl set-hostname xx

3. 계정 생성 및 ssh 접속

- 계정추가

sudo adduser newuser

- 새로운 계정에 sudo 그룹 권한 할당

sudo usermod -aG sudo newuser

- 새로운 계정으로 ssh 접속하고 업데이트

ssh newuser@192.168.0.10

sudo apt update

4. Kernel Cgroup 설정

sudo vi /boot/firmware/nobtcmd.txt

# 아래내용 append
cgroup_enable=cpuset cgroup_enable=memory cgroup_memory=1

Build k8s cluster through Kubeadm

1. iptables가 브리지된 트래픽을 보게하기

cat <<EOF | sudo tee /etc/modules-load.d/k8s.conf
br_netfilter
EOF

cat <<EOF | sudo tee /etc/sysctl.d/k8s.conf
net.bridge.bridge-nf-call-ip6tables = 1
net.bridge.bridge-nf-call-iptables = 1
EOF
sudo sysctl --system

2. 도커 설치

- Set up the repository

1. Update the apt package index and install packages to allow apt to use a repository over HTTPS:

 sudo apt-get update
 sudo apt-get install \
    ca-certificates \
    curl \
    gnupg \
    lsb-release

2. Add Docker's official GPG key

curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo gpg --dearmor -o /usr/share/keyrings/docker-archive-keyring.gpg

3. Use the following command to set up the stable repository. To add the nightly or test repository, add the word nightly or test (or both) after the word stable in the commands below. 

echo \
  "deb [arch=$(dpkg --print-architecture) signed-by=/usr/share/keyrings/docker-archive-keyring.gpg] https://download.docker.com/linux/ubuntu \
  $(lsb_release -cs) stable" | sudo tee /etc/apt/sources.list.d/docker.list > /dev/null

- Install Docker Engine

sudo apt-get update
sudo apt-get install docker-ce docker-ce-cli containerd.io
sudo usermod -a -G docker $USER # 해당 유저를 도커 그룹에 넣는다.

- systemd를 사용하도록 도커 데몬을 구성

sudo mkdir /etc/docker
cat <<EOF | sudo tee /etc/docker/daemon.json
{
  "exec-opts": ["native.cgroupdriver=systemd"],
  "log-driver": "json-file",
  "log-opts": {
    "max-size": "100m"
  },
  "storage-driver": "overlay2"
}
EOF

sudo systemctl enable docker
sudo systemctl daemon-reload
sudo systemctl restart docker

https://kubernetes.io/ko/docs/setup/production-environment/container-runtimes/#%EB%8F%84%EC%BB%A4

3. kubeadm, kubelet, kubectl 설치

sudo apt-get update
sudo apt-get install -y apt-transport-https ca-certificates curl

sudo curl -fsSLo /usr/share/keyrings/kubernetes-archive-keyring.gpg https://packages.cloud.google.com/apt/doc/apt-key.gpg

echo "deb [signed-by=/usr/share/keyrings/kubernetes-archive-keyring.gpg] https://apt.kubernetes.io/ kubernetes-xenial main" | sudo tee /etc/apt/sources.list.d/kubernetes.list

sudo apt-get update
sudo apt-get install -y kubelet kubeadm kubectl
sudo apt-mark hold kubelet kubeadm kubectl

https://kubernetes.io/ko/docs/setup/production-environment/tools/kubeadm/install-kubeadm/

4. Initialize Master node

- sudo kubeadm init

Your Kubernetes control-plane has initialized successfully!

To start using your cluster, you need to run the following as a regular user:

  mkdir -p $HOME/.kube
  sudo cp -i /etc/kubernetes/admin.conf $HOME/.kube/config
  sudo chown $(id -u):$(id -g) $HOME/.kube/config

Alternatively, if you are the root user, you can run:

  export KUBECONFIG=/etc/kubernetes/admin.conf

You should now deploy a pod network to the cluster.
Run "kubectl apply -f [podnetwork].yaml" with one of the options listed at:
  https://kubernetes.io/docs/concepts/cluster-administration/addons/

Then you can join any number of worker nodes by running the following on each as root:

kubeadm join 192.168.10.3:6443 --token 64xvn4.a7wdy0u0y0iu7cwv \
	--discovery-token-ca-cert-hash sha256:4421c3cc7bd5011d38072d1c365b515dc43f6d3cd501213e12fc0c3f1a559fd0

5. 워커 노드를 클러스터에 조인 시킨다.

kubeadm join 192.168.10.3:6443 --token 64xvn4.a7wdy0u0y0iu7cwv \
	--discovery-token-ca-cert-hash sha256:4421c3cc7bd5011d38072d1c365b515dc43f6d3cd501213e12fc0c3f1a559fd0

6. Settin up Flannel as the container network on the Master node

kubectl apply -f https://raw.githubusercontent.com/coreos/flannel/c5d10c8/Documentation/kube-flannel.yml

각 노드의 podCIDR 이 설정되어 있지 않아 flannel Pod가 정상 동작하지 않는 경우

k logs -f kube-flannel-ds-88nvk -n kube-system
I0119 00:34:14.341794       1 main.go:218] CLI flags config: {etcdEndpoints:http://127.0.0.1:4001,http://127.0.0.1:2379 etcdPrefix:/coreos.com/network etcdKeyfile: etcdCertfile: etcdCAFile: etcdUsername: etcdPassword: help:false version:false autoDetectIPv4:false autoDetectIPv6:false kubeSubnetMgr:true kubeApiUrl: kubeAnnotationPrefix:flannel.alpha.coreos.com kubeConfigFile: iface:[] ifaceRegex:[] ipMasq:true subnetFile:/run/flannel/subnet.env subnetDir: publicIP: publicIPv6: subnetLeaseRenewMargin:60 healthzIP:0.0.0.0 healthzPort:0 charonExecutablePath: charonViciUri: iptablesResyncSeconds:5 iptablesForwardRules:true netConfPath:/etc/kube-flannel/net-conf.json setNodeNetworkUnavailable:true}
W0119 00:34:14.342055       1 client_config.go:608] Neither --kubeconfig nor --master was specified.  Using the inClusterConfig.  This might not work.
I0119 00:34:14.740596       1 kube.go:120] Waiting 10m0s for node controller to sync
I0119 00:34:14.740824       1 kube.go:378] Starting kube subnet manager
I0119 00:34:15.740911       1 kube.go:127] Node controller sync successful
I0119 00:34:15.740978       1 main.go:238] Created subnet manager: Kubernetes Subnet Manager - master-node-01
I0119 00:34:15.741037       1 main.go:241] Installing signal handlers
I0119 00:34:15.741551       1 main.go:460] Found network config - Backend type: vxlan
I0119 00:34:15.741619       1 main.go:652] Determining IP address of default interface
I0119 00:34:15.742772       1 main.go:699] Using interface with name eth0 and address 192.168.10.3
I0119 00:34:15.742871       1 main.go:721] Defaulting external address to interface address (192.168.10.3)
I0119 00:34:15.742890       1 main.go:734] Defaulting external v6 address to interface address (<nil>)
I0119 00:34:15.743068       1 vxlan.go:137] VXLAN config: VNI=1 Port=0 GBP=false Learning=false DirectRouting=false
E0119 00:34:15.744236       1 main.go:326] Error registering network: failed to acquire lease: node "master-node-01" pod cidr not assigned
I0119 00:34:15.744432       1 main.go:440] Stopping shutdownHandler...

아래와 같이 수동으로 설정을 해주어야한다. 기본적으로 클라우드 프로바이더가 이러한 설정을 해주기를 기대하는 것으로 보인다.

master-01@master-node-01:/etc/kubernetes/manifests$ kubectl patch node master-node-01 -p '{"spec":{"podCIDR":"10.244.0.0/24"}}'
node/master-node-01 patched
master-01@master-node-01:/etc/kubernetes/manifests$ kubectl patch node worker-node-01 -p '{"spec":{"podCIDR":"10.244.3.0/24"}}'
node/worker-node-01 patched
master-01@master-node-01:/etc/kubernetes/manifests$ kubectl patch node worker-node-02 -p '{"spec":{"podCIDR":"10.244.4.0/24"}}'
node/worker-node-02 patched

7. 검증

- kubectl get nodes

NAME        STATUS   ROLES                  AGE     VERSION
master-node-01      Ready    control-plane,master   8m40s   v1.21.2
worker-node-01   Ready    <none>                 4m17s   v1.21.2
worker-node-02   Ready    <none>                 3m48s   v1.21.2

Optional) NFS test on k8s worker node

1. External NFS 서버 설정

1.1. NFS 서버를 위한 패키지 프로그램 설치

apt-get install nfs-common nfs-kernel-server rpcbind portmap

1.2. 공유할 폴더 생성

mkdir /mnt/data
chmod -R 777 /mnt/data

1.3. NFS 설정 수정

설정 파일은 /etc/exports 파일이다.

아래는 NFS를 걸 폴더는 /mnt/data이고, 172.31.0.0/16에 대해 다 열겠다는 뜻이다.

Kubernetes Node CIDR 대역으로 설정하면됨.

/mnt/data 172.31.0.0/16(rw,sync,no_subtree_check)

• rw: read and write operations
• sync: write any change to the disc before applying it
• no_subtree_check: prevent subtree checking

1.4. 반영

exportfs -a
systemctl restart nfs-kernel-server

2. NFS 클라이언트

2.1. NFS 클라이언트를 위한 패키지 프로그램 설치

모든 Kubernetes Node에 설치를 해야함.

apt-get install nfs-common

2.2. NFS 연결을 위한 PV 생성

apiVersion: v1
kind: PersistentVolume
metadata:
  name: nfs-pc
spec:
  capacity:
    storage: 100Mi
  accessModes:
    - ReadWriteMany
  nfs:
    server: 192.168.10.x
    path: /mnt/k8s

Kubernetes Storage Class - NFS dymanic provisioner도 활용 가능

- https://github.com/kubernetes-sigs/nfs-subdir-external-provisioner

- https://sarc.io/index.php/os/1780-ubuntu-nfs-configuration

Optional) NFS 마운트

- NFS 마운트할 폴더 생성

mkdir /public_data

- 마운트

NFS 서버 IP가 172.31.2.2라고 하면,

mount 172.31.2.2:/mnt/data /public_data

rpi image : https://www.raspberrypi.com/software/

ubunt 18.04.5 image for rasberry pi : https://cdimage.ubuntu.com/ubuntu/releases/18.04.6/release/

알고리즘 종류 : 이진 탐색

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력1

1 0 0 1 1 0 0 1

Scanner를 쓰면 통과를 못하는 문제.

BufferedReader만 써도 통과 못하는 문제.

BufferedReader와 BufferedWriter를 사용해야한다.

import java.util.Arrays;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
	private int N;
	private int M;
	private final int MAX = 500010;
	private int[] numbers = new int[MAX];

	// private int targets[] = new int[MAX];
	public static void main(String[] args) {
		Main main = new Main();
		try {
			main.start();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private void start() throws Exception {
		//System.setIn(new FileInputStream("src/bs/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			numbers[i] = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		
		Arrays.sort(numbers, 0, N);
		for (int i = 0; i < M; i++) {
			int target =  Integer.parseInt(st.nextToken());
			if(binarySearch(target)) bw.write("1 ");
            // 이분 탐색을 해서 해당 숫자가 없는 경우
            else bw.write("0 ");
		}
        br.close();
        bw.close();
	}

	private boolean binarySearch(int target) {
		boolean found = false;
		int s = 0, e = N - 1;
		while (s <= e) {
			int divide = (s + e) / 2;
			if (numbers[divide] == target) {
				found = true;
				break;
			} else if (numbers[divide] < target) {
				s = divide + 1;
			} else {
				e = divide - 1;
			}
		}
		return found;
	}
}

출처

- https://www.acmicpc.net/problem/10815