문제BOJ 1149번 : RGB거리https://www.acmicpc.net/problem/1149 문제풀이시간 복잡도시간복잡도는 우선 O(N^2lgN) 미만으로 풀면 될 것이라고 생각하였다. 구현 아이디어1. 이전의 집을 색칠한 색은 사용 불가2. 최소 비용으로 색칠하기이 두 조건을 만족시키는 조건문을 작성하는 것이 좀 까다로웠다.DP로 구현을 해야겠다 생각을 하였다.집의 개수에 RGB의 비용을 저장할 배열을 추가하여 dp[1001][3] 배열을 만들고 RGB 별 비용을 넣으면 된다. 코드#include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; i..
문제BOJ 9251번 : LCShttps://www.acmicpc.net/problem/9251 문제풀이시간 복잡도N이 1000 이하 이므로 O(N^2) 풀이가 가능2중 for문으로 순회 가능 구현 아이디어1. 두개의 문자열 비교를 위한 2중 for문 필요2. 분기처리를 할 때 이전의 DP값 사용3. 그렇다면 DP에 어떻게 저장하고 갱신할 것인가?3번에서 계속 막혀서 엑셀에 기록하며 추적해보았다.문자열이 같을 때는 쉽게 생각하여 구현했는데 막상 문자열이 다를때 처리를 하는것이 어려웠다. 그리고 같은 행에서 값들을 지나가면서 업데이트 해줘야 다음 행에서 사용이 가능했기에 이 부분에 대한 처리가 필요했다. 코드#include#includeusing namespace std;int dp[1001][1001]..
문제BOJ 11053번 : 가장 긴 증가하는 부분 수열https://www.acmicpc.net/problem/11053 문제풀이시간 복잡도N이 1000 이하 이므로 O(N^2) 풀이가 가능2중 for문으로 순회 가능 구현 아이디어처음에는 정렬후 다른 수가 등장하면 카운트하면 되는 줄 알고 풀었다가 틀렸다.정렬하지 않고 주어진 수열에서 증가하는 부분수열을 찾는 문제였다.점화식을 세워야하는데 좀처럼 떠오르지 않았다. 코드#include#includeusing namespace std;int main(void) { ios::sync_with_stdio(0); cin.tie(0); int N, ans = 0; int arr[1001] = { 0 }; int dp[1001] = { 0 }; cin >> N; ..
문제BOJ 1003번 : 피보나치 함수https://www.acmicpc.net/problem/1003 문제풀이시간 복잡도N은 40까지로 작지만 피보나치수열이고 시간이 0.25초 이내 이기 때문에 재귀로는 접근할 수 없다.따라서 DP를 사용하여 메모이제이션으로 한번 계산한 결과를 다시 계산하지 않고 접근해야 한다. 구현 아이디어2의 결과는 0과 1의 합이다. 따라서 출력되는 답도 피보나치인 셈이다.N이 40까지 이므로 40까지의 결과를 미리 배열에 저장한다.배열은 0의 개수를 저장하는 배열과 1의 개수를 저장하는 배열이 필요하다.초기 값은 0의 결과와 1의 결과로 프로그램이 실행되자마자 40까지의 연산을 한다.테스트 케이스와 N을 입력받고 배열에서 N번째의 0과 1의 개수를 출력하면 된다. 코드#inc..
문제BOJ 19598번 : 최소 회의실 개수https://www.acmicpc.net/problem/19598 문제풀이시간 복잡도N이 (1 ≤ N ≤ 100,000) 이므로 O(N^2) 미만으로 풀어야 한다.순회를 할 때 O(N^2)가 안되도록 접근해야 한다.따라서 O(NlgN) 이하의 자료구조를 사용해야 한다. 구현 아이디어처음에 아이디어를 바로 떠올리지 못해서 연습장에 테스트 케이스들을 직접 구성하느라 시간을 20~30분 정도 사용하였다.제약 사향- 동시에 진행되는 회의는 다른 회의실에서 진행해야 한다. - 최소 회의실 수를 구해야 한다. 문제 접근1. 회의실을 최대한 재사용을 많이 해야한다.2. 회의가 끝나는 시간을 추적해서 끝나는 시간보다 시작시간이 더 큰 회의들 중 끝나는 시간에 가장 가까운..
문제BOJ 1946번 : 신입 사원https://www.acmicpc.net/problem/1946 문제풀이시간 복잡도N이 (1 ≤ N ≤ 100,000) 이므로 O(N^2) 미만으로 풀어야 한다.순회를 할 때 O(N^2)가 안되도록 접근해야 한다. 구현 아이디어1. 정렬을 사용해 볼까? 했지만 굳이 그럴 필요 없이 바로 배열에 넣었다.2. 배열에서 순회하면서 2중 for문으로 앞의 인덱스들만 비교한다. => 시간 초과 2중 for문에서 최악의 경우 O(N^2)인데 이것을 생각하지 못하고 O(NlgN)인 줄 알고 구현해 버렸다... 재구현1. 기존과 마찬가지로 바로 서류 등수를 arr배열의 인덱스로 사용 => 정렬을 사용하면 O(NlgN)이 걸리지만 이렇게 바로 배열에 입력하게 되면 순회하는 O(N)으..
문제BOJ 17503번 : 맥주 축제https://www.acmicpc.net/problem/17503 문제풀이시간 복잡도N, K가 (1 ≤ N, K ≤ 200,000) 이므로 O(N^2) 미만으로 풀어야 한다.2중 for문 말고 다른 방식으로 접근해야 한다.일단 정렬로 접근하려고 구상하였다. 구현 아이디어시간복잡도를 생각하면서 정렬과 그리디를 잘 사용하면 될 것이라는 생각을 하였다.우선 최소 도수를 구해야 하므로 도수 순으로 정렬을 해야 한다. 하지만 도수와 같이 선호도가 함께 따라다니므로 2개의 자료형을 묶을 Struct가 필요하다. => 이 Struct를 Vector에 넣으면 자동으로 묶여서 다닐 것이다.Vector를 맥주의 도수 오름차순으로 정렬하고 for문을 돌면서 검사해야 한다.도수는 정렬..
문제BOJ 15686번 : ATMhttps://www.acmicpc.net/problem/11399 문제풀이시간 복잡도N(1 ≤ N ≤ 1000) 이므로 O(N^3) 미만으로 풀어야 한다.2중 for문 까지는 여유롭게 가능 구현 아이디어일단 문제를 보고 정렬만 하면 되겠다 생각하였다.왜냐하면 정렬하게 되면 자동으로 처음부터 할 수 있는 최적의 해 이기 때문이다.따라서 vector에 담고 정렬 후 합을 구하면 답이다. 코드#include#include#includeusing namespace std;int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, ans=0; cin >> n; vector v(n,0); for (int i = 0; i > v[..
