본문 바로가기

전체 글411

[C++] 백준 12865번 : 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 배열 DP[i][j]는 가방이 j 무게 일 때 i 번째 물건까지 확인했을 때의 최대 가치이다. 예를 들어서 DP[3][5]는 무게 5인 가방에 대해서 3번째 물건까지 확인했을 때의 최대가치이다. 경우는 단순하게 2가지로 i번째 물건을 담았을 때와 담지 않았을 때로 나뉜다. 표를 통해서 이해하면 매우 쉽다. (문제 참고!).. 2021. 6. 25.
[C++] 백준 1912번 : 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 연속합을 구하는 문제이기 때문에 경우는 단순하게 2가지 경우로 나뉜다. 1. i번째 더한 값이 최대인 경우 2. i-1번째까지 더한 값보다 i번째 값이 더 큰 경우 배열 DP[i]는 i번째 연속합을 저장한다. DP[i]는 2가지 경우에 따라 DP[i-1] + arr[i]값과 arr[i]값만 비교해주면 된다. 느낀 점 처음에 DP[i]의 값에 대해서 잘못 생각해서 많이 헤매었다. i번째까지 존재하는.. 2021. 6. 25.
[C++] 백준 9251번 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 10844번:쉬운 계단 수와 문제와 비슷한 문제이다. 2차원 배열 DP[i][j]는 첫 번째 문자(str1)의 i번째와 두 번째 문자(str2)의 j번째까지 가장 긴 부분 수열의 길이를 저장한다. 즉, DP[2][3]은 AC와 CAP를 비교했을 때의 LCS의 길이가 1이라는 것이다. (ex. DP[4][5] == 2) 배열 DP의 원소를 채우.. 2021. 6. 25.
[C++] 프로그래머스 : 폰켓몬 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 문제 풀이 폰켓몬들의 개수만 따지면 되는 문제이다. 따라서, 중복되는 요소들을 제거하고 그 중에서 N/2개 만큼만 가져가면 된다. N/2보다 중복요소가 제거된 배열의 사이즈가 작다면 배열의 사이즈가 정답이 되고, 아니라면 N/2가 정답이다. 느낀 점 처음에 DPS로 풀으려고 했다가 코드가 너무 길어지는 것 같아서 의구심을 가지고 다른 분들의 코드를 살펴봤다. .. 2021. 6. 24.
[알고리즘] 가장 긴 증가하는 부분수열(LIS) ※ 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)이란? 부분 수열 중에서 각 원소가 이전 원소보다 큰 부분 수열 중에서 가장 긴 것! 예를 들어서, { 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 때, 증가하는 부분 수열은 { 2, 5 }, { 1, 4, 3} 등이 있지만 LIS는 { 2, 5, 7, 8 } 이다! 알고리즘은 시간복잡도에 따라서 2가지가 있다. ( O(N^2)과 O(N log N) ) 첫 번째 방법은 다이나믹 프로그래밍을 통한 방법이다. 시간 복잡도는 O(N^2) code#1 1 2 3 4 5 6 7 for (int i = 0; i arr[i]; } dp[0] = arr[0]; int idx = 0; for (int i = 1; i 2021. 6. 23.
[C++] 백준 2565번 : 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 전깃줄이 교차하지 않으려면 선들이 평행을 이뤄야 한다. 전깃줄의 각 꼭짓점은 위에서 아래로 내림차순을 이루고 있어서 LIS를 접목시키면 쉽게 풀 수 있다. 전깃줄을 이루는 각 꼭짓점의 숫자들이 LIS를 이룬다면 교차하지 않는 전깃줄들이 최대가 된다. 한쪽이 정렬되어있을 때 반대쪽의 LIS를 따지면 해결된다. 정렬은 STL에서 제공하는 sort 함수로 정렬하고 반대쪽 전봇대(B)의 값들의 LIS.. 2021. 6. 23.

티스토리툴바