전체 글108

• [2110] 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분탐색 문제다. 공유기를 설치할 때 간격이 최대한 넓어야 한다. 처음엔 c만큼 조합을 구해야 할까 고민했는데 N의 최대 크기가 10^5라 시간초과가 날 것이다. 이렇게 데이터가 많은 경우 이분탐색으로 생각해보야 한다. 공유기 간격이 최대면서 동시에 공유기 개수가 맞아야 하므로 공유기 간격의 범위를 비교해가며 공유기가 설치될 자리를 찍어보며 공유기 간격을 조절하는 것이 핵심이겠다. 특히 간격이 middle일 때.. 코딩테스트 2024. 1. 14.

• 

  [20444] 색종이와 가위 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 수학적 접근이 필요한 이분 탐색 문제다. 색종이를 n번 잘랐을 때 k개가 되는지 여부를 확인하는 문제. 가로로 잘린 횟수 + 1와 세로로 잘린 횟수 + 1의 곱이 잘린 색종이의 개수가 되는데, 이때 가로로 잘린 횟수를 x라 두면, 세로로 잘린 횟수는 n - x가 되므로 둘의 곱은 이차 방정식으로 나타낼 수 있다. 여기서 y = k와의 해가 있는지 확인하기 위해 그래프로 확인할 필요가 있다는 점에서 수학적 접근이 필요하다. 위 그래프는 잘린 종이의 개수 y = (x + 1) * (n - x + 1) 에 대한 그림이다. 보다시피 x = -1, n + 1이며, 우.. 코딩테스트 2024. 1. 13.

• [2470] 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터 문제다. 정렬된 배열의 양 끝 값을 차례대로 움직여가며 원하는 값(0)이 나올 때까지 start와 end 값을 조정해준다. 이분 탐색과 다른 점은 middle값으로 범위를 나누는 것이 아니라 양 끝 값을 +(-) 1로 조절하는 것이다. 산성용액과 알칼리 용액의 합이 0에 가까워야 하므로 매번 양 끝 값을 움직이며 최소값을 구하듯 이전 result과 비교하며 finalL과 finalR에 넣어준다. 그리고 혼합물이 0이 .. 코딩테스트 2024. 1. 11.

• [3079] 입국심사 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 이분 탐색 문제다. 이분 탐색 카테고리가 없었다면 이분 탐색이라는 방법을 쓸 생각을 못 했을 것 같다. 아마 각 줄에 몇 명이 있어야하는지 알고리즘이 딱히 없었기 때문에 모든 시간을 탐색해서 확인하는 방법이 필요했을 것이다. 그 과정에서 시간은 순차적이기 때문에 이분 탐색이어야만 했다. 주어진 시간동안 각각의 줄에서 처리할 수 있는 사람의 수를 구해 그 사람의 수가 M보다 큰지 작은지 확인해 범위를 좁혀나간다. 스케줄 표를 작성하는 게 아니라 시간.. 코딩테스트 2024. 1. 10.

• [22871] 징검다리 건너기 이분탐색 문제다. 가장 왼쪽 돌에서 가장 오른쪽 돌로 건너갈 수 있는 모든 경우의 수 중에서 K의 최솟값을 구하는 문제다. K는 i 에서 j 번째 돌로 이동할 때 걸리는 힘이며, (j - i) * (1 + |Ai - Aj|)로 구할 수 있다. K의 범위는 1부터( j - i = 1 & Ai == Aj ) 최대( j - i = N - 1 & Ai와 Aj가 최대, 최소)일 경우이며 이 범위는 순차적이다. 따라서 K값으로 징검다리를 건널 수 있는지 확인하면서 건널 수 없는 경우 K를 늘려주고, 아니라면 K를 줄여주는 방법으로 K를 이분탐색할 수 있다. #include #include using namespace std; int main() { int N; cin >> N; int rock[5001]; int .. 코딩테스트 2024. 1. 9.

• [1654] 랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분 탐색 문제다. 나무 자르기와 거의 동일한 문제다. 가지고 있는 랜선의 개수 K를 똑같은 길이 M으로 잘라(편의상 M이라고 칭하겠다) 주어진 랜선의 개수 N보다 크거나 같을 때 M의 최대값을 구하는 문제다. 여기서 M의 범위는 1부터 최대 랜선의 길이까지이며, 각 랜선이 M만큼 잘리는 개수는 랜선을 M으로 나눈 몫으로 구하면 된다. M의 범위는 순차적이며, 완전 탐색으로 모두 탐색하기엔 무리가 있으므로 이분 탐색을 사용하여 M의 .. 코딩테스트 2024. 1. 7.

• [2805] 나무 자르기 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색 문제이다. 높이 H만한 절단기로 잘린 나무의 크기의 합이 m과 같거나 클 때 H값이 최대가 될 때를 구하는 문제이다. 절단기 H의 높이를 얼마큼 잡아야할지, 그래서 정해진 m보다 크거나 같을 때 H값을 생각해줘야 하는데 고려해야 할 점은 H값을 구하기 위해 H값의 범위(0 ~ 현재 나무의 최대 높이) 사이를 이분 탐색 해줘야 할 것 이분 탐색 도중 m보다 크거나 같을 때 바로 break를 걸어주면 안 된다는 점 .. 코딩테스트 2024. 1. 7.

• [19637] IF문 좀 대신 써줘 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 이분 탐색 문제다. 칭호의 이름과 칭호에 맞는 전투력을 가지고 M개의 캐릭터에 맞는 칭호를 출력하면 되는 문제로, 캐릭터의 전투력이 어떤 칭호의 전투력의 범위 내에 있는지 확인하면 문제를 풀 수 있다. 범위를 두 번 체크할 필요는 없고 칭호를 비교할 때 작거나 같을 때만 어떤 칭호의 이름을 확인하면 된다.(이때 시간 복잡도는 M x log2N으로 10^8.. 코딩테스트 2024. 1. 6.

• 

  [CORE SESSION] Automating Architecture 정리 용어 정리프로비저닝클라우드 서비스를 시작하고 구성하는 것, Puppet, Ansible 등이 있다.Puppet, Ansible커뮤니티 오픈소스 IT 자동화 툴. 서버/엔드포인트 기기에서 시스템 구성 및 프로비저닝, 소프트웨어 배포, 업데이트 관리와 같은 일상적인 task를 자동화 해서 IT 운영과 DevOps 작업을 간소화 할 수 있다. Ansible은 자동화 대상에 추가 소프트웨어를 설치하지 않아도 되는 유연한 에이전트리스 접근 방식이며, 반면 Puppet은 전통적으로 각 시스템에 주가 소프트웨어를 설치해야 하는 에이전트 기반 접근 방식을 선택한다.배포프로비저닝된 서버를 위해 애플리케이션 버전을 제공하는 작업AWS CodePipline소프트웨어 release에 필요한 단계를 모델링, 시각화 및 자동화하.. AWS 2024. 1. 5.

• [11663] 선분 위의 점 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 이분 탐색 문제다. 실버 3 문제라 쉽겠다 생각하고 아무 생각 없이 각 선분 마다 해당되는 점을 이분 탐색으로 찾았다가 시간초과가 났다. 당연한 얘기겠지만 제한 시간은 1초인데다 N과 M은 최대 100,000이라 N X M만 해도 1억을 훌쩍 넘긴다. (게다가 N X M X log2였다) 선분의 양 끝 값이 주어진 점보다 작은지 큰지 확인만 하면 되는 문제지만 주어진 점이 선분의 양 끝 값 A, B와 일일이 비교한다면 그런 N X M이 .. 코딩테스트 2024. 1. 5.

• [SAA] Associate SAA-C03 5문제 A company collects data for temperature, humidity, and atmospheric pressure in cities across multiple continents. The average volume of data that the company collects from each site daily is 500 GB. Each site has a high-speed Internet connection. The company wants to aggregate the data from all these global sites as quickly as possible in a single Amazon S3 bucket. The solution must minimize ope.. AWS 2023. 12. 23.

• 

  CloudWatch와 x-ray를 통해 관찰 가능성 확보하기 Cloud Watch?Amazon CloudWatch는 AWS, 온프레미스, 하이브리드, 기타 클라우드 애플리케이션 및 인프라 리소스에 대한 데이터와 실행 가능한 인사이트를 제공하는 모니터링 및 관리 서비스입니다. 모든 성능 및 운영 데이터를 사일로(서버, 네트워크 또는 데이터베이스)에서 모니터링하는 대신 단일 플랫폼에서 로그와 지표 형태로 수집하고 액세스할 수 있습니다. CloudWatch는 애플리케이션 성능을 최적화하고, 리소스 사용률을 관리하고, 시스템 전반의 운영 상태를 파악하는 데 도움이 되는 실행 가능한 인사이트를 제공합니다. CloudWatch는 AWS 외에 다른 온프레미스에서도 사용가능한 서비스다. 로그, 지표, 이벤트 등의 운영 데이터를 수집해 시각화 및 처리하며 경보 생성을 통해 자동화.. AWS 2023. 12. 2.