Minhee Lee

(2021년 1월 14일에 작성한 글입니다.) Standings - Codeforces Round #552 (Div. 3) - Codeforces codeforces.com 200108에 #695를 하고 충격을 받은 채로 있다가 한 시간 뒤인 2:30부터 4:30까지 했다. ​ ​ A. 수들이 순서가 뒤죽박죽인 채로 들어온다는 부분을 처음에 놓쳐서 좀 헤맸다. 정렬 한 다음에 가장 큰 값에서 나머지 세 값들을 하나씩 빼서 출력하면 된다. int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll arr[4]; int i; for (i = 0; i > arr[i]; } sort(arr, arr + 4); cout > ..

(2021년 1월 14일에 작성한 글입니다.) Standings - Codeforces Round #553 (Div. 2) - Codeforces codeforces.com 번개 버추얼을 돌았다 결과는 2솔 ​ ​ A. 그냥 구현하면 된다. 나는 두 알파벳 사이의 거리를 구하는 함수를 만들어서 substring과 ATCG와 비교하여 각각의 거리를 더했고 그 중에 최솟값을 찾았다. int diff(char a, char b) { return min({ abs(a - b), abs(a + 26 - b), abs(b + 26 - a) }); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; string s; int i, j; int..

1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 중간고사 준비하면서 Bash와 친해지기 위해 문제를 풀어봤다. 확실히 이렇게 하고 나니까 확 익숙해졌다! shell script 처음엔 정말.. 답답했는데 계속 하다보니까 재밌다. 나중에 심심할 때 Bash로 쉬운 문제들 풀어봐야겠다. read s1 s2 s1Len=${#s1} s2Len=${#s2} if [ $s1Len -gt $s2Len ]; then tmp=$s1 s1=$s2 s2=$tmp s1Len=${#s1} s2..

20930번: 우주 정거장 첫 번째 줄에는 우주 정거장 개수 $N$과 질문의 개수 $Q$가 주어진다. ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$) 다음 $N$개의 줄에는 $i$번 우주 정거장의 양 끝점을 나타내는 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$ www.acmicpc.net 2021 겨울 신촌연합 알고리즘 캠프 중급 대회에 나왔던 문제다. 대회에서 이 문제를 풀었을 때 계속 맞는 거 같은데 틀렸고 결국 시간 내에 못 풀었다. 대회 끝나고 풀이 방송에서 BOJ 17619-개구리 점프 문제랑 비슷하다고 하셔서 내 로직대로 일단 그 문제부터 풀었는데 맞았다. 그럼 이 문제도 맞아야 한다! 싶어서 아예 처음부터 짰는데 맞았다. 그래서 대회 때 냈..

(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..

(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 ..