K

그리디 알고리즘을 이용한 문제 # 회의실 배정 # 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. # 첫째 줄에 회의의 수 N, 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어진다. 이는 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. # 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다. n = int(input()) A = [[0, 0] for _ in range(n)] for i in range(n): S, E = map(int, input().split()) A[i][0] = E # 종료시간을 기점으로 정렬해야 하기 때문에 앞에 저장 A[i][1] = S A.sort() cnt = 0 end = -1 for i in range(n):..

워크로드 쿠버네티스 상에서 작동되는 애플리케이션 +) 클라우드 분야에서는 애플리케이션을 실행할 때 필요한 IT 리소스의 집합이라는 의미로 통용됨 파드(Pods) 쿠버네티스의 배포 가능한 가장 작은 컴퓨팅 유닛 그 자체로 하나의 논리적인 호스트 파드에 포함된 항목(도커 컨테이너처럼 파드 내에서 다음 요소들은 격리됨) 하나 이상의 애플리케이션 컨테이너 IP 주소 볼륨과 같은 공유 스토리지 파드를 생성하기 위해 파드를 정의할 때, YAML 파일을 사용할 수 있음 apiVersion: v1 kind: Pod metadata: name: nginx spec: containers: - name: nginx image: nginx:1.14.2 ports: - containerPort: 80 YAML 파일로 정의된 파..

쿠버네티스 아키텍처 클러스터는 하나 이상의 제어판(Control Plane) 컴포넌트와 이와 연결된 몇 개의 워커 노드로 구성됨 워커 노드 kublet이라는 프로세스가 돌가가고 있는데, 이는 다른 노드와 서로 통신하거나 컨테이너를 실행하는 등 태스크를 실행할 수 있게 함 워커 안에는 한 개 이상의 컨테이너가 자리잡고 있음, 즉 워커 노드는 실제로 애플리케이션이 실행되고 있는 곳 컨테이너, 볼륨, 작동 정보 등을 파드(Pod)라고 부름 제어판(Control Palne) 관리를 위해 필요한 프로세스들이 존재하며, 클러스터가 잘 작동할 수 있게 도움 API 서버 모든 클러스터 관리의 입구로서, 명령을 내릴 수 있는 관문 쿠버네티스에서 제공되는 UI, CLI 등에서 클러스터 관리를 위해 명령을 내리면 API가 ..

컨테이너 오케스트레이션 수십~수백 개의 컨테이너를 관리하고자 할 때 사용하는 툴 왜 수십~수백 개의 컨테이너가 필요한가? - 아키텍처의 트랜드: 모놀리식 -> 마이크로서비스 - 컨테이너 개수 증가 - 확장성을 고려한 스케일링 쿠버네티스(Kubernates, k8s) 오픈소스로 만들어진 컨테이너 오케스트레이션 도구 컨테이너화된 애플리케이션을 자동으로 배포, 스케일링하는 등 관리 기능 제공 온프레미스, VM, 클라우드 등 각기 다른 환경에 대응 가능 사용이 적합하지 않은 경우 여러 단계로 나뉘지 않은 모놀리식 아키텍처 마이크로서비스 분해 전략을 세우는 것이 우선 서너 개에 불과한 컨테이너 docker-compose로 충분 비교적 단순한 아키텍처, 스케일링이 필요하지 않은 경우 트래픽이 증가하거나 스케일링이 ..

그리디 알고리즘과 우선순위 큐를 이용한 문제 # 수 묶기 # 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. # 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다. # 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오. # 첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. # 수를 합이 최대가 나..

그리디 알고리즘과 우선순위 큐를 이용한 문제 # 카드 정렬하기 # 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. # N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오. # 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다. # 첫째 줄에 최소 비교 횟수를 출력한다. from queue import PriorityQueue n = int(input()) queue = PriorityQueu..

그리디 알고리즘을 이용한 문제 # 동전 0 # 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. # 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. # 첫째 줄에 N, K가 주어진다. 둘째 줄부터 N개의 줄에 동전의 가치가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) # 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. n, k = map(int, input().split()) A = [] for i in range(n): A.append(int(input())) # 리스트의 뒤부터 탐색하며 k보다 큰 동전..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=8V2zw6Qxarc&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=23 그리디 알고리즘 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 최적의 해를 보장하지는 않음 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

간단하게 푸는 방법 그러나 n^2의 시간 복잡도를 가지기 때문에 실패한다. n = int(input()) k = int(input()) A = [[] for _ in range(n)] B = [] for i in range(n): for j in range(n): A[i].append((i + 1) * (j + 1)) x = (i + 1) * (j + 1) B.append(x) print(B[k]) 이 문제를 푸는 핵심은 이진 탐색을 이용하는 것 이진 탐색을 이용하여 중앙값보다 작은 값의 개수가 k-1개일 때 멈추면 된다. # K번째 수 # 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순..

이진 탐색을 이용한 문제 문제 해석이 너무 어렵다..;; # 기타 레슨 # 첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 블루레이의 개수 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. # 첫째 줄에 가능한 블루레이 크기중 최소를 출력한다. n, m = map(int, input().split()) A = list(map(int, input().split())) start = 0 end = 0 for i in A: if start < i: start = i end += i while start mid: # 블루레이 1개 증가 cnt += 1 sum = 0 sum += A[i] if sum != 0: cnt += 1 i..