'study' 카테고리의 글 목록 (4 Page)

study

48건

백준 11047 - 동전0

1. 문제 정리 - 동전은 총 N 종류이고 종류당 동전 수는 무한하다. - 동전의 합이 K가 되는 가장 작은 동전의 수를 출력한다. - 동전의 가치값들의 입력값은 오름차순이다. 2. 접근 - 각각의 동전은 독립적이며, 제한된 갯수가 없기 때문에 그리디 알고리즘으로 접근이 가능하다. - 포함시킬 수 있는 가장 큰 값의 동전부터 더해 가면서 K값을 구할 수 있다. 3. 풀이 #include #include #include using namespace std; int n, k; vector a; int ans = 0; void greedy(){ int left = k; while(left != 0){ for(int i =0 ; i = a[i]) { left -= a[i]; ..

백준 11662 - 민호와 강호

1. 문제 정리 - 민호와 강호의 좌표가 각 ax, ay, cx, cy의 형태로 주어진다. - 민호와 강호는 각각 bx, by, dx, dy의 좌표로 나아간다. - 민호와 강호는 같은 시각에 목표 좌표에 도달한다. - 민호와 강호의 거리가 가장 가까울 때의 거리값을 출력한다. - 절대/상대 오차는 1e-6까지 허용한다. - + 예제 출력에서 보이듯 소수점 이하 10째자리까지 출력해보자. 2. 접근 - 처음에 이분탐색으로 풀려다, 검색의 결과 삼분탐색으로 풀 수 있는 문제였다. - 시간에 따른 민호와 상호의 거리를 함수화하여 삼분탐색을 실행한다. - f(t) = t에 따른 민호와 상호 사이의 거리 3. 풀이 #include #include #include using namespace std; struct ..

백준 10816 - 숫자 카드 2

1. 문제 정리 - n개의 숫자 카드가 주어진다. - m개의 정수가 주어진다. - 각 정수는 -10000000 이상, 10000000 이하에 속한다. - m개의 수에 대하여 각 정수값이 n개의 숫자 카드에 몇개씩 있는지 출력한다. 2. 접근 - n개의 숫자 배열에 대해 m개의 정수 중 하나를 target으로 이분탐색을 시행한다. - 이분탐색을 upperBound와 lowerBound 두개로 나누어 진행하고, 각 반환값의 차를 출력하여 배열에 포함된 값의 수를 찾는다. 3. 풀이 #include #include #include using namespace std; int n, m; vector a; vector b; int lo, hi; int lowerBound(long long target){ lo =..

백준 2110 - 공유기 설치

1. 문제 정리 - 집의 수 N개에 공유기의 수는 C개이다. - 각 집의 좌표는 x의 배열이며, 각 좌표는 중복되지 않는다. - 좌표 하나당 공유기 하나를 설치할 수 있다. - 가장 인접한 두 공유기 사이의 거리의 최대값을 구한다. 2. 접근 - 중요한 부분은 두 공유기 사이의 거리의 최대값을 구한다는 점이다. - x 좌표 하나하나가 아닌, 인접한 두 x좌표의 간격을 이용하여 이분탐색을 이용하여 문제를 해결한다. 3. 풀이 #include #include #include using namespace std; int n, c; int lo = 1; int hi = 0; int ans = 0; vector x; void bis(){ int d = 0; while(lo > n >> c; for(int i = ..

백준 10815 - 숫자 카드

1. 문제 정리 - N개의 수와 M개의 수가 주어진다. - M개의 수 각각이 N개의 수 배열에 포함되는지를 검증한다. 2. 접근 - 전형적인 이진탐색 문제라고 생각했다. - N개의 수가 들어있는 배열은 정렬을 하고, M개의 수는 그대로 사용하고자 하였다. - M개의 수를 N개의 배열에 이진탐색을 시도하는 것으로 시간 복잡도는 O(M*logN)이며, 이는 최대값으로 보았을 때, 500000*log(500000) = 약 1100만 이므로 2초 시간제한 안에 들어온다. 3. 풀이 #include #include #include using namespace std; int n, m; vector a; vector comp; bool bis(int target){ int hi, lo; hi = n-1; lo = ..

백준 2805 - 나무 자르기

1. 문제 정리 - 앞에 풀었던 1654번 문제와 유사하다. - 각 나무의 높이 H가 주어진다. 정답인 값을 ans라고 하였을 때, ans 값 이상의 나무는 H-ans만큼 잘려간다. - 각 나무의 H - ans 값의 합이 M이상의 최솟값이 되도록한다.(Upper Bound) 2. 접근 - 이번에도 이분탐색으로 풀고자 하였다. - 가장 큰 H값을 max, 그리고 min 값을 0으로 잡아 이분 탐색을 적용하고자 하였다. 3. 풀이 #include #include using namespace std; long m, n; vector a; long lo = 0; long hi = 0; long ans = -1; void bis(){ while(lo mid) cnt += i-mid; } if(cnt < m) hi..

백준 1654 - 랜선 자르기

1. 문제 정리 - N과 K를 입력 받는다. - K개의 랜선을 잘랐을 때, N개의 랜선을 만드는 가장 긴 길이의 랜선을 구한다. - N개 이상의 랜선 또한 답에 포함한다.(Upper Bound) 2. 접근 - 언뜻 배열이 아니라 그냥 브루트 포스로 풀 수도 있지만, 보면 이분탐색으로 충분히 풀 수 있는 문제이다.\ - 정답을 가정한 값으로 위 조건(N개 이상의 랜선)을 충족하는 지 짚어갈 것이다. 3. 풀이 #include #include using namespace std; long n, k; long lo = 1; long hi; long ans = 0; vector lan; void bis(){ while(lo > k >> n; for(int i = 0; i < k; i++){ long input;..

백준 14395 : 4연산

1. 문제 정리 - 입력받은 s값을 제시 받은 4개의 연산을 이용해 t값으로 변환한다. - 4개의 연산 중 나누기가 포함된 연산은 s가 0일 때는 사용할 수 없다. - s와 t는 1과 10^9 사이의 값이다.(주의하자.) 2. 접근 - 일반적인 bfs 방식으로 풀 수 있다고 생각하였다. - 4가지 연산자를 이동 가능한 범위, 그리고 정답 범위에 포함된 정수값을 이동할 수 있는 node라고 판단한다. - 중복 체크는 bool check 배열로 구현하기에는 검사 범위가 너무 넓기 때문에, set 을 사용하여 해결 - 검사 범위가 크기 때문에(10^9) int 형이 아닌 long 형으로 설정한다. 3. 풀이 #include #include #include using namespace std; struct nu..

10026 적록색약

1. 문제 정리 - 영역 정의 문제이다. 상하좌우로 인접한 값 중 같은 값을 가질 경우 하나의 영역으로 인식한다. - 적록색약의 경우 R 값과 G 값의 경우 같은 취급을 한다. 2. 접근 - 영역 정의 문제인 만큼 bfs로 풀기로 하였다. - 영역을 정의하는 기준이 두개인 만큼 bfs를 두가지로 나누어 하나는 비적록색약, 하나는 적록색약을 기준으로 하는 bfs를 구현하기로 했다. - 적록색약 기준 bfs의 경우 'R'과 'G'의 값을 동일시 하도록 하였다. 3. 풀이 //2021.12.06 #include #include using namespace std; int n; char a[100][100]; bool check[100][100][2]; int ans = 0; int wAns = 0; int d..

1 2 3 4 5 6

티스토리툴바