Minhee Lee

학교 과제로 MST를 STL 없이 짜야 했다. 그래서 이전에 짜놨던 min_heap을 사용해서 짰다. 그때 다형성을 사용하고, 메소드 이름을 STL이랑 동일하게 짜 놓은 덕분에 이번 과제는 금방 했다. C++는 정말 재밌다. 다른 언어들도 배워야지. #include #include #include #include #include #define kEndl '\n' typedef long long ll; typedef unsigned long long ull; using namespace std; template class Heap { public: Heap() { end = 1; tree.resize(1); } virtual void push(T value) = 0; virtual void pop() = ..

학교 과제 하면서 짰다 C++ 클래스, 상속 사용하면서 짜니까 재밌다 처음에 min heap의 pop 메소드를 짤 때 왼쪽 자식부터 확인하면서 자식에 부모보다 큰 값이 저장되어 있으면 값을 바꾸고 바로 다음 level로 넘어갔는데 그렇게 하니까 틀렸다. 만약 3 -> {2, 1}이 저장되어 있을 때 왼쪽 자식이랑만 값을 비교하면 2 -> {3, 1} 상태가 된다. (a -> {b, c}는 부모노드, 왼쪽 자식, 오른족 자식에 저장된 값이 각각 a, b, c라는 의미이다) 이는 부모 노드의 값은 자식 노드의 값보다 작거나 같아야 한다는 원칙을 위반한다. 위와 같은 상황에서 두 자식 노드에 대해 모두 비교하면 되지 않을까? 라는 생각을 했지만 만약 그렇게 한다면 3 -> {2, 1} 상태에서 2 -> {3,..

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

class KMP { public: string str, pat; vector table; vector ans; void getTable() { table.resize(pat.length()); int left = 0; for (int i = 1; i 0 && pat[left] != pat[i]) { left = table[left - 1]; } if (pat[left] == pat[i]) { table[i] = left + 1; left++; } } } void getAns() { getTable(); int patIdx = 0; for (int strIdx = 0; strIdx < str.length(); strIdx++) { whil..

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