Minhee Lee

(2021년 1월 13일에 작성한 글입니다.) 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 우수마을 문제(1949번)랑 비슷하다 차이점이 있다면 독립집합을 찾아줘야 한다는 거. ​ 경찰차 문제(2618번)에서 처럼 dp값이 채워지는 경로를 찾아 가면 된다. 함수 print(int cur, bool flag)를 만들었고 cur 변수는 현재 확인중인 노드 번호, flag는 이 노드가 독립집합에 속해 있는 친구인지를 저장해줬다. ​ 현재 노드를 독립집합에 포함시킨 상태라면 (fl..

(2021년 1월 13일에 작성한 글입니다.) 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 신기하도다 정말 신기하다 ​ 처음에는 dp[1][i]는 i번째 사건을 1번 차가 처리, dp[2][i]는 i번째 사건을 2번 차가 처리... 이렇게 해서 점화식을 세우면 될 줄 알았는데 말이 안 되는 풀이였다.. 그래서 결국 여러가지 풀이를 찾아봤고 재귀를 사용한 dp였다... ​ 그리고 2차원 dp 배열은 1번 차가 i번째 사건, 2번 차가 j번째 사건을 처리했을 때 최소 이동거리를 저장하고 있다. 진..

(2021년 1월 12일에 작성한 글입니다.) 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리DP! 예전에 DP 몰아서 공부할 때 충격받았던 함수의 재귀를 이용한 방식이다. 겨울 ​신촌연합 알고리즘 캠프 중급 스터디에서 다뤘다. ​ 3번째 조건을 어떻게 처리하면 되는지가 까다로운데 강사님께서 3번 조건은 무시하면 된다고 하셨다. 그렇다. 무시하면 된다. ​ 내가 이해한 방법은 두 번째 조건 때문에 일단 우수마을끼리는 인접할 수 없는 상황이다 만약 n번째 마을이 우수마을이 아니고, 인접한 우수 마..

(2021년 1월 12일에 작성한 글입니다.) 주의할 점: LCS를 복원할 때, dp 값이 왼쪽이나 위쪽과 같은지를 먼저 체크하고 그것에 해당하는 처리를 한 후에 그 둘을 만족하지 않고, dp값이 대각선 위쪽 값 + 1과 같을 때 그것이 LCS 문자열의 구성 요소가 된다. 처음에 대각선 위쪽값+1인지를 먼저 체크했더니 복원이 제대로 안 된다. ​ 그리고 나는 dp 파트에서 인덱스랑 string 파트 인덱스가 다른게 싫어서 string s1, s2의 맨 앞에 ' '를 추가했다. 이렇게 처리하고 나면 코드를 이해하기 쉬워져서 좋다. int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s1, s2; int len1, len2; int i..

(2021년 1월 9일에 작성한 글입니다.) Dashboard - Codeforces Round #695 (Div. 2) - Codeforces codeforces.com A. 처음에는 9876543210987... 이렇게 출력하는 건 줄 알았다 근데 웃긴건 내가 잘못 해서 첫 번째 제출에 if(num == 0) num = 9; 이렇게 해서 9876543219876... 이렇게 출력되게 됐고 이거 때문에 틀린 줄 알고 수정해서 다시 냈는데 또 틀렸다. 그래서 생각해보니까... 앞에서 두 번째 숫자가 8이 될 때 break 해서 9890123456789012345... 이렇게 되는게 최대다.. 깨닫는데 시간이 좀 걸렸다 다 비슷한 상황이었다...ㅎ int main() { ios::sync_with_stdi..

(2021년 1월 5일에 작성한 글입니다.) 2021년 1월 4일 내 첫 강의,,, 스터디,,,!!! 진짜 너무 떨렸다... 이건 강의 영상! 조금 봤는데.. 들어보면 목소리 엄청 떨리는거 느껴진다..ㅋㅋ 우와 수고했어... 다음 강의는 STL인데 이거보다 쉽고 재밌으니까 더 잘 할수 있을 거 같다..ㅎㅎ

(2020년 12월 21일에 작성한 글입니다.) Dashboard - Codeforces Round #692 (Div. 2, based on Technocup 2021 Elimination Round 3) - Codeforces codeforces.com A. 그냥 구현. string 입력받고 뒤에서부터 세주면 된다 int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; int N; string s; int i; int cnt; cin >> T; while (T--) { cin >> N; cin >> s; cnt = 0; for (i = N - 1; i >= 0; i--) { if (s[i] == ')') { cnt++; } else ..

(2020년 12월 20일에 작성한 글입니다.) Dashboard - Codeforces Round #691 (Div. 2) - Codeforces codeforces.com A. 카드 중에서 R > B인거, R B인것의 개수가 더 많으면 RED, R > T; while (T--) { cin >> N; vector R(N + 5), B(N+5); for (i = 0; i ..

(2020년 12월 18일에 작성한 글입니다.) Dashboard - Educational Codeforces Round 100 (Rated for Div. 2) - Codeforces codeforces.com A. 7의 배수번째에 올킬하기 때문에 7번의 작업에서 총 9를 죽이게 된다. 그래서 총 합이 9의 배수이면 YES, 아니면 NO 하려 했으나 ​ 총 합이 9의 배수라는 건 올킬을 sum / 9번 한다는건데 그러면 모든 값이 최소 sum / 9가 되어야 한다. ​ 그래서 총 합이 9의 배수라도 min_element < sum / 9면 NO, 이것도 만족하면 YES다.​ int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; in..

(2020년 12월 18일에 작성한 글입니다.) Dashboard - Codeforces Round #690 (Div. 3) - Codeforces codeforces.com A. 그냥.. 잘 출력하면 된다 N이 홀수일 때는 마지막에 중앙에 있는 값 출력해줘야되고 int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; int N; int i; cin >> T; while (T--) { cin >> N; vector arr(N + 5); for (i = 0; i > arr[i]; } for (i = 0; i N; if (N > 45) { cout 0; i--) { i..