본문 바로가기

Algorithm197

[백준 1026] 보물 1026번: 보물 (acmicpc.net) 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 내 풀이 #include using namespace std; int a[105], b[105]; int n; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i > a[i]; for (int i = 0; i > b[i]; sort(a, a + n); sort(b, .. 2022. 10. 11.
[백준 2217] 로프 2217번: 로프 (acmicpc.net) 내 풀이 #include using namespace std; int n; int w[100005]; int maxW=0; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0;i>w[i]; } sort(w,w+n); int sum=0; for(int i=0;i> w[i]; sort(w, w+n); int ans = 0; for(int i = 1; i 2022. 10. 11.
[백준 1931] 회의실 배정 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정답 풀이 #include using namespace std; int n; pair s[100005]; // schedule, 정렬의 편의를 위해 {끝 시간, 시작 시간}으로 저장 int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i > s[i].second >> s[i].first; sort(s,s+n); // 먼저 끝나는 시간을 비교하고, 끝나는 시간이 동일하면 시작 시간 순으로 정렬 int ans = 0; .. 2022. 10. 11.
[백준 11047] 동전 0 11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 내 코드 #include using namespace std; int n, k; int a[15]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int cnt=0; cin>>n>>k; for(int i=0;i>a[i]; } while(k>0) { if(k==0) break; for(int i=n-1;i>.. 2022. 10. 10.
[실전 알고리즘] 다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming, DP) 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘 ex. 피보나치 ex. DP 피보나치 문제를 DP로 해결하면 미리 배열을 만들어두고 0번째 인덱스부터 하나씩 채워가는 방식으로 해결할 수 있고 N+1칸을 채우고 나면 답을 알 수 있으니 O(N)에 답을 알아낼 수 있다. 중간 결과를 저장해서 이용하는지 그렇지 않은지에 따라 극적인 시간복잡도의 차이가 발생 DP를 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 연습 문제 BOJ 1463: 1로 만들기 [백준 1463] 1로 만들기 (tistory.com) BOJ 9095: 1,2,3 더하기 [백준 9095] 1,2,3 더하기 (tis.. 2022. 10. 10.
[넥토리얼 2기] 코테 4시간 보호되어 있는 글 입니다. 2022. 10. 7.

티스토리툴바