Leta Learns

문제 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 예제는 잘 돌아가는데 시간초과가 나서 며칠동안 고군분투했던 문제.. 그냥 문제가 귀여워서 재밌어 보이길래 시도한 건데 푼 사람도 많이 없어서 구글링해도 시간초과 해결하는 법을 찾을 수 없었다.. 같이 스터디하는 친구도 시간초과 났었는데 해결한 후 본인 알고리즘 설명해준 거 듣고 나도 비슷한 방식으로 접근해봤다. 우선, 당근 맛의 최댓값을 가지려면..

문제 https://www.acmicpc.net/problem/11047 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 회의실 배정 문제를 제외하면 그리디는 처음 풀어본 것 같다. 정해진 틀이 있는 게 아니라 알고리즘 생각하고 구현하는 느낌이라서 풀면서 내가 지금 그리디로 잘 풀고 있는 게 맞나? 의문이 들었다. 가장 큰 동전부터 사용하기 위해서 입력받은 동전의 가치들을 역순으로 정렬한 후 for문을 사용하여 가능한 동전 수를 구하였다. 어쨌든 ..

그리디 알고리즘 공부 2021.06.29 - [HUFS/Algorithm] - Greedy Algorithm (그리디, 욕심쟁이 알고리즘) Greedy Algorithm (그리디, 욕심쟁이 알고리즘) 1. Greedy Algorithm : 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 Greedy 알고리즘은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 letalearns.tistory.com 예제는 맞는데 시간 초과가 난다. 이중 for문을 사용해서 그런 것으로 추정되는데 이중 for문 안 쓰고 푸는 방법이 도무지 생각나지 않는다. 코드 길이라도 줄여보려고 다른 방식으로 코드를 하나 더 작성했으나 이것도 이중 for문을 사용해서인지 시간 초과..

문제 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테이블 직접 그렸다. 앞으로 DP 문제 풀 때는 테이블 구상하는 방법을 생각해서 접근해야지. else 부분 max 비교 대상을 찾는 게 관건이었고 그것만 하면 어렵지 않았다. n..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 학교 수업에서 DP 배울 때 LCS 배웠어서 겁먹지 않고 풀 수 있었다. 수업 때 교수님이 코드까지 주신 줄 알았는데 찾아보니 코드 없이 이론만 있었어서 직접 코드 짜는데 시간이 좀 걸리긴 했다. 처음엔 아무 생각 없이 교수님이 주신 pseudo-code 보고 그냥 짜다가 DP 문제라는 걸 깨닫고 바로 노선 변경ㅋㅋ 자꾸 인덱스 에러가 나서 애 좀..