본문 바로가기
반응형

전체 글160

프로그래머스 - 정수 삼각형 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 풀이 간단한 DP 문제이다. 그림에서는 삼각형이지만 실제 배열로 나타내면 [7] [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5] 의 형태이므로 조금 더 점화식을 세우기 쉽다. 누적 값에 현재 값을 더해나가며 DP 배열을 채워나간다 행을 i, 열을 j로 나타내면 [3, 8]에서 3에 더할 수 있는 값은 triangle[i-1][j]에 있는 7이고 8에 더할 수 있는 값은 triangle.. 2022. 3. 6.
BOJ 1654 - 랜선 자르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 이미 갖고 있는 랜선들 k개를 잘라 n개의 랜선을 만들 때, 랜선 하나의 최대 길이를 구하면 된다. 그러기 위해서는 랜선의 길이를 x라 했을 때, 원소들에 대해 (LANlines[i] / x)를 구하여 몇 개의 랜선을 만들 수 있는지 구한 뒤 모두 더해 n개 이상 만들 수 있다면 정답이 될 수 있다. 따라서 0부터 랜선의 최대 길이를 이분 탐색.. 2022. 3. 4.
BOJ 2805 - 나무 자르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 나무들의 높이가 주어지고 절단기의 길이가 x일 때 (trees[i] - x)만큼 집에 나무를 가져갈 수 있다. 적어도 m미터의 나무를 가져가기 위한 절단기의 최대 길이를 구하면 된다. 이를 구하기 위해 이분 탐색을 이용한다. 일반적인 이분 탐색은 원소 값들을 탐색하지만 해당 문제에서는 원소 값들을 탐색해서는 답을 찾을 수 없다. 따라.. 2022. 3. 4.
이진 탐색(Binary Search) 배열이 정렬되어 있을 때, 가운데 값과 비교하여 찾고자하는 값이 더 크면 오른쪽을 작다면 왼쪽을 탐색하는 방식 예시 [2, 5, 7, 9, 14, 19, 20, 24]가 있을 때 만약 2를 찾고 싶다면 가운데 값인 14와 비교를 하면 더 작기 때문에 다시 왼쪽 부분인 [2, 5, 7, 9]에서 같은 방식으로 반복한다. 최종적으로 2를 찾아 인덱스를 리턴하게 된다. 장점 시간복잡도가 log n으로 상당히 빠르다. 완전 탐색을 수행했을 때 시간 초과가 나는 여러 문제에서 활용될 수 있다. 구현 재귀로 구현 int recursive_binarySearch(vector arr, int start, int end, int target){ if(start > end) return -1; int mid = (star.. 2022. 3. 3.
반응형

티스토리툴바