Minhee Lee

(2021년 1월 16일에 작성한 글입니다.) 20543번: 폭탄 던지는 태영이 시험을 망친 태영이가 인하대학교에 폭탄을 던진다! 인하대학교는 N×N 크기의 정사각형 모양의 땅이다. 인하대학교의 모든 땅은 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c) www.acmicpc.net 와... 진짜 신기한 문제다... 처음 풀이는 가장자리부터 값이 남아있는지 확인하고(시계 반대방향으로 돎) 만약 남아있다면 M * M 영역을 돌면서 값을 빼주는 걸 반복했다. 시간 안에 해결할 수 있을 줄 알았는데 역시 어림도 없었다. 그렇게 한참 고민하다 결국 풀이를 봤다 https://altheajang.blogspot.com/2021/01/ps-boj-20543.html 놓친 포인트는 1. 굳이 가장..

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

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 학회 스터디 강의할 때 다룬 문제 이 문제를 잘 설명하고 싶어서... ppt.. 정말 열심히 만들었다. 이분탐색을 접목해 가능한 높이 중 일부만 확인하는 게 포인트. int arr[1000000]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; int left, right, maxH = 0..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 학회 스터디 강의할 때 다룬 문제 이분 탐색을 구현해서 푸는 코드와 STL 사용하는 코드 모두 보여드렸다. int arr[100000]; bool search(int left, int right, int key); int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n; f..

www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 학회 스터디 강의할 때 다룬 문제 우선 N*N 크기의 행렬로 표현되는 종이인지 확인한다. 만약 그렇다면 개수를 업데이트 해주고, 그렇지 않다면 종이를 아홉 등분하여 각각에 대해 또 다시 확인하면 된다. 풀이 자체가 문제를 세 줄로 요약한 거랑 다를 바가 없는데, 결국 이걸 어떻게 구현할 것인지가 관건인 것 같다. #include using namespace std; int arr[7000][7000]..