분류 전체보기 120

[백준 2805] 나무 자르기

나무 자르기 문제설명 나무의 수, 최소 필요한 나무의 길이, 그리고 각 나무의 길이를 입력 받는다. 그리고 톱의 최대 높이를 설정해서 필요한 나무의 길이를 구할 수 있게 되는 값을 구하자. 알고리즘 값을 각각 입력 받는다. 이때 long long 타입으로 입력 받는다. 나무의 각 길이를 입력 받은 벡터를 정렬하고, 이분 탐색을 하기위해 0부터 나무의 최대 값을 매개변수로 넣는다. 이분 탐색 과정에서 나무를 잘랐을 때 얻을 수 있는 양을 구한다. 얻을 수 있는 양이 최소 조건에 도달 할 수 있는지 확인하고 도달 할 수 있는 경우 max함수로 그 톱의 길이를 갱신한다. 도달할 수 없는 경우는 end-1을 해서 범위를 좁혀준다. 위의 과정을 반복해서 result 변수에 담긴 값을 출력한다. #include #..

Algorithm 2021.07.30

[백준 1735] 분수 합

분수 합 문제설명 두 수를 입력 받는 데 각각 분자, 분모 순으로 입력 받는다. 두 분수의 합을 구해서 기약분수 형태로 구해서 결과 값의 분자와 분모를 출력한다. 알고리즘 두 수의 분자와 분모를 각각 입력 받는다. 통분을 위해서 각각의 분자에 다른 수의 분모 값을 곱하고 두 값을 더한다. 분모는 두 수의 분모를 곱한 값이다. 기약분수 형태로 나타내기 위해서 결과값의 분모와 분자 중에 어떤 값이 더 작은지 판단한다. 더 작은 값을 기준으로 1씩 줄여가면서 분자 분모의 나머지가 모두 0이 되는 값을 찾아 그 수로 나눈다. 결과 값을 출력한다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL..

Algorithm 2021.07.30

[백준 2164] 카드2

분수 합 문제설명 카드의 동작을 수행하고 난 결과를 출력시킨다. 알고리즘 몇 장의 카드가 있는지 입력 받는다. queue에 값을 채워 넣는다. 문제에서 주어진 대로 동작을 하기위해 반복문 내에서 카드가 1장 남을 때 까지 반복한다. 맨 앞의 값을 지우고 그 다음 값을 꺼내서 맨 뒤에 넣는다. 가장 마지막에 1개 남은 카드의 값을 출력시킨다. #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL); int N; cin >> N; queue q; for (int i = 0; i < N; i++)//값 입력 q.push(i + 1); while (q.size() != 1)//값을 ..

Algorithm 2021.07.30

[백준 3184] 양

양 문제설명 행과 열을 입력 받은 다음, #은 울타리 .은 아무것도 없음, o는 양 그리고 v는 늑대를 의미한다. 이때 울타리 공간 안에 양의 수가 늑대의 수보다 많으면 양은 늑대를 밀어 낼 수 있다. 다른 말로는 늑대가 양의 수보다 많거나 같으면 늑대가 양을 처리한다. 따라서 다음 날의 존재하는 늑대와 양의 수를 출력시킨다. 알고리즘 문자열과 행과 열의 값을 입력 받는다. 각 값을 조회하는데, 그 칸을 방문 하지않았고, 울타리가 아닌 경우 DFS 함수로 조회한다. DFS 함수에서는 방문 표시를 하고 늑대, 양의 수를 세며, 울타리는 종료시킨다. 늑대나 양을 센 경우에는 그 구역 내의 다른 칸도 확인하기 위해서 상하좌우로 이동하며 다른 양이나 늑대의 수를 센다. DFS 함수에서 빠져나와서 해당 구역에 늑..

Algorithm 2021.07.30

[백준 1715] 카드 정렬하기

카드 정렬하기 문제설명 총 카드 묶음의 수를 입력 받은 뒤, 각 카드의 수를 입력 받는다. 이때 카드를 확인하는 수를 A+B라고 한다. 가장 적은 수의 카드를 확인하는 경우의 수를 출력시킨다. 알고리즘 카드 묶음의 수와 각 카드 묶음 당 카드의 수를 입력 받는다. priority_queue를 사용하여 수가 입력되면 자동으로 오름차순으로 정렬되도록 한다. 큐에서 가장 앞에있는 (가장 작은 두 값) 두 값을 꺼내서 ans 변수에 더한 값을 넣는다. 다시 더한 값을 queue 에 넣고, 원래의 두 값은 지운다. queue에 남은 수가 1개가 되면 반복을 멈추고 나와서 ans의 값을 출력한다. #include #include #include using namespace std; int main(void) { i..

Algorithm 2021.07.30

[백준 2504] 괄호의 값

괄호의 값 문제설명 첫 줄에 식을 입력 받는다. 이때 식은 (),[]로 이루어져 있다. ()는 2이고 []는 3이다. 주어진 식의 값을 알맞게 계산하여 값을 출력한다. 알고리즘 문자열을 입력받는다. 문자열을 각각 read 하고, 여는 괄호일 때는 계산의 편의를 위해서 괄호 그대로 넣지 않고 &#39;(&#39;일 때는 -1을 넣고 &#39;[&#39;일때는 -3을 넣는다 짝이 맞지 않는 경우 바로 0을 리턴하여 종료 시킨다. 닫는 괄호가 들어온 경우 stack의 맨 위값이 짝이 맞는지 확인하고 맞으면 (일 때 2를 넣고 [이면 3을 넣는다. 맨 위가 숫자이면 여는 괄호를 만날때 까지 전부 더한다. 전부 더한 뒤 다음 가장 위의 값이 짝이 맞으면 2나 3을 곱하고 그 값을 stack을 넣는다. 2-6의 과..

Algorithm 2021.07.29

[백준 6198] 옥상 정원 꾸미기

옥상 정원 꾸미기 문제설명 빌딩의 수를 입력 받고, 각 빌딩의 높이를 입력 받은 뒤, 총 관리인이 옥상정원을 확인할 수 있는 수를 출력한다. 이 때 빌딩은 오른쪽으로만 확인 가능하고, 오른쪽의 빌딩의 높이가 같거나 높으면 더이상 빌딩을 확인할 수 없다. 알고리즘 입력 값들을 입력 받는다 stack을 확인하여 비었는지, 현재 top의 크기가 새로 넣으려는 크기보다 같거나 작은지 판단한다. top의 크기가 같거나 작은 경우 오른쪽으로 볼 수 없는 경우를 의미하니까 pop하여 제거해준다. 새로운 값을 stack 에 넣는다. stack의 크기 -1만큼 정답에 더해준다. 시간초과난 코드 -> 벡터로만 풀었을 때 #include #include #include using namespace std; int main(..

Algorithm 2021.07.29

[백준 7562] 나이트의 이동

나이트의 이동 문제설명 테스트 케이스의 수를 입력받고, 체스판의 크기, 시작점과 도착점을 각각 입력받는다. 그리고 시작점에서 도착점까지 나이트가 이동할 때 최소의 이동 수를 구하여라. 이동 가능한 칸은 사진의 그림과 같다. 알고리즘 테스트 케이스의 수를 입력받고, 필요한 입력을 받는다. bfs함수를 실행한다. 시작점을 queue에 넣고 방문여부를 체크한다. queue가 비기전까지 반복하는데, x,y좌표를 꺼낸다. x,y가 도착점과 일치하면 graph의 해당 좌표 값을 출력한다. 나이트가 이동가능한 경우 8개를 각각 배열에서 read해서 체스판의 범위 확인 후 가능하면 방문한다. 4-6의 과정을 반복하여 방문하고 graph를 갱신해서 값을 출력한다. #include #include #include #inc..

Algorithm 2021.07.29

[백준 1929] 소수 구하기

문제설명 M,N을 입력받고, 그 범위내의 소수를 구해서 출력한다. 알고리즘 N,M을 입력 받는다. bool type의 배열을 N+1만큼 만들고, 1로 초기화 시킨다. 0번째와 1번째는 false로 초기화 해준다. 소수를 구하기 위해서 에라토스테네스의 체 알고리즘을 사용한다. #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int M,N; cin >>M>> N; bool *arr = new bool[N+1]; fill_n(arr, N + 1, 1);//초기화 arr[0] = false; arr[1] = false; for (int i= 2; i

Algorithm 2021.07.29

[백준 11279] 최대 힙

최대 힙 문제설명 첫 줄에 연산의 수를 입력하고, 연산의 수만큼 매 줄마다 정수 x가 입력된다. 0이 입력되면 배열안의 가장 큰 수를 출력하고 지운다. 자연수가 입력되면 배열안에 값을 넣는다. 따라서 0이 나올때 마다 그 결과 값을 출력하면 된다. 만약 배열이 빈 경우 0이 입력되면 0을 출력한다. 알고리즘 연산의 수를 입력 받고 priority_queue를 선언한다. 0이 입력 될 때마다 비어있으면 0, 그렇지 않으면 top을 출력하고 pop해준다. 그 외의 자연수가 입력되면 push해준다. #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)..

Algorithm 2021.07.29