알고리즘47 [Baekjoon] 백준 알고리즘: 1049 - 기타줄 문제 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 내가 생각했던 풀이과정 1. 예제 출력 2로 확인한 결과 꼭 같은 브랜드의 6개묶음과 낱개묶음을 사야하는 것이 아닌 브랜드를 섞어서 구매해도 된다는 것을 알아서, 2. 각 브랜드별로 6개 묶음의 가격과 낱개 가격을 입력받을 때 앞의 입력에는 6개 묶음 배열에, 뒤의 입력에는 낱개 묶음 배열에 추가해준다 3. 필요한 돈의 수를 최소로 하기 때문에 그리디를 생각해서, 6개 묶음 배열에서 가장.. 2021. 5. 20. [Baekjoon] 백준 알고리즘: 1021 - 회전하는 큐 문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 내가 생각했던 풀이과정 1) 데크를 사용한다. 데크란 양방향 큐가 있는데 바로 데크(deque) 자료구조이다. 데크는 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다. 2) deque.rotate(iteration): iteration 횟수만큼 deque의 맨 뒷 값을 맨 앞으로 이동시킨다. deque.rotate(-iteration): iteration 횟수.. 2021. 5. 18. [Baekjoon] 백준 알고리즘: 1010 - 다리놓기 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 내가 생각했던 풀이과정 1) 순서가 없는 조합 문제이다. 조합이란 집합에서 서로 다른 n개의 원소 중에서 순서와 상관없이 r개를 선택하는 것이다. 순서가 없다고 생각한 이유는 어떤 다리를 놓아도, 순서에는 영향을 미치지 않기 때문이다. 2) m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 갯수는 n개이다. m개의 지역에 n개의 다리를 놓을 수 있는 경우를 찾는 것이기 때문에 mCn 문제.. 2021. 5. 17. [Baekjoon] 백준 알고리즘: 1920번 - 수 찾기 문제 www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 내가 생각했던 풀이과정 1) 이진탐색을 사용하려면 정렬되야 하기 때문에, 처음 정렬을 한다 2) 시작을 start, 끝을 end로 index를 설정해주고, 찾아야할 숫자는 in 함수를 통해 반복문을 돈다. 3) 시작이 끝보다 작을 때까지 반복하며 이진 탐색을 위해 중간지점을 찾는다 중간지점이 타겟이라면 1을 return하고 중간지점의 값보다 타겟이 작을 경우.. 2021. 5. 6. 이전 1 2 3 4 5 6 7 ··· 12 다음