돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/17167 문제 설명 두 숫자 a,b 가 주어져 있을 때, 5000번 이하의 a+=b, a+=a, b+=b, b+=a의 4가지 행동을 통해서 a와 b를 똑같게 만들 것이다. 이때 걸리는 횟수와 그 방법을 출력하시오. 문제 풀이 일단 범위를 줄이는 데 집중을 해보자. 3,9로 수를 시작하는 것과, 1,3으로 수를 시작하는 것은 다른 결과가 나올까? 라는 질문으로 시작을 하게 되면 아니라는 결론이 나오게 된다. 좀 더 확장시켜서 생각을 해보면 항상 a,b를 같게 만드는 일련의 행동들은 c=gcd(a,b)인 c에 대해서 a/c, b/c를 같게 만들 수 있다. 물론 반대도 성립한다. a+=a는 a를 두 배 시키는 것과 동치이다. 따라서 b가..

Vector C++을 사용하게 되면 정말 많이 사용하게 되는 자료구조(?)인 벡터이다. 배열을 사용하는 만큼 정말 많이 사용한다. 배열에서 가능한 모든 연산을 할 수 있으며 추가로 몇 가지 연산들을 더 할 수 있다. 하지만 1-based index를 사용하는 입장으로써는 몇 가지 상황이 아니면 그냥 배열을 사용한다. 문법 많이 사용하는 문법 vector v ll 형식의 vector v 생성. (아무것도 안 들어있는 상태) vector v[303030] ll 형식의 vector 로 이루어진 배열 v 생성. v[i] v의 i번째 원소 참조. 이때 v의 크기는 i+1이상이어야 한다. v.push_back(x) v의 마지막에 원소 x 삽입 v.emplace_back(a,b,c) 원래는 구조체등의 다 원소 개체를..

문제 링크 : https://www.acmicpc.net/problem/2544 (P1) 문제 태그 더보기 이분 매칭, 파라메트릭 서치 문제 풀이 맨처음에 이 문제를 볼 때는 DP가 생각났다. 상태를 잘 정의해서 풀면 $O(N^3)$에 문제를 해결할 수 있을 것 처럼 보였다. 하지만 다음 상태로 넘어가는 그 관계에 대해서 정의를 하는 것이 힘들어서 다른 방법을 찾았다. 위의 과정에서 생각을 하면서 이 문제를 좀 그리디하게 접근할 수 있다는 것을 깨달았다. 당연히 가장 높은 수를 없애는 방향으로 줄을 지워야 한다. 결국 가장 높은 수부터 k개의 줄을 이용해 어느 수 까지 없앨 수 있는 지를 알아야 한다. 가능한 최소(최대) 를 구하는 문제가 나온 이상, 결정론적으로 문제를 바꿔서 생각을 안해볼 수가 없다...

문제 링크 : https://www.acmicpc.net/problem/2988 (P3) 문제 풀이 2번째 줄에 등장하지 않은 수나, 3번째 줄에 등장하지 않은 수의 값이 첫번째 줄에 쓰여있으면 그 줄은 절대로 선택될 수 없다. 그 줄을 지우게 되면 이로 인해서 또 2번째 줄이나 3번째 줄에 등장하지 않는 수가 생길 것이다. 그러면 또 그 수가 첫번째 줄에 적혀있는 줄을 지운다. 이 과정을 반복하면 된다. 더이상 이 과정을 진행하지 않는다는 것은 첫번째 줄에는 있는데, 두번째 줄이나 세번째 줄에는 없는 수는 없다. 이때 각 줄에 쓰인 수의 갯수는 같으므로, 각 줄에 대해서 쓰여있는 수들의 집합은 셋이 모두 동일할 수 밖에 없게 된다. 이는 문제 해결 조건과 정확히 일치하다. - 코포에 나올법한 문제. 그..

Queue FIFO. First In First Out의 자료구조이다. 즉, 큐에 먼저 들어간 원소가 먼저 빠져 나오게 된다. 즉 아래와 같은 형식으로 자료구조가 원소들을 관리한다는 것이다. 문법 queue q ll 형식의 자료를 담는 큐 q 생성 q.push(x) q의 가장 뒤쪽에 원소 x삽입 q.front() q의 가장 앞에 있는 원소 참조 q.back() q의 가장 뒤에 있는 원소 참조 q.pop() q의 가장 앞에 있는 원소 삭제 q.size() q에 들어있는 원소의 수 반환 q.empty() q에 원소가 없는지(비었는지) 판별 while(!q.empty()) or while(q.size()) q가 빌 때까지. 보통 q의 원소를 하나씩 모두 뺄 때 사용 q1=q2 q1에 그대로 q2를 대입 swa..

서론 STL. Standard Template Library. C++을 위한 라이브러리로 사용자의 편의를 위해서 기본적으로 제공되는 라이브러리이다. 코딩을 함에 있어 STL과는 떼려야 뗄 수 없는 관계이고, STL 사용능력은 곧 코딩 능력과 코딩 속도로 직결되게 된다. 하지만, 나는 STL 활용을 잘 하지 못한다. 일단 제대로 많이 알고 있는 것도 아니고, 별로 익숙하지도 않아서, 사용할 수 있는 각을 잘 보지 못하고, 막상 사용을 한다고 하더라도 기억을 제대로 못해서 꼭 디버깅을 몇 번 해보거나 코딩에 머뭇거림이 굉장히 심해진다. 이는 빠른 속도의 코딩을 요구하는 몇 개의 대회에서의 성적 하락으로 이어졌다. 마침, 조만간 빠른 속도의 코딩을 요구하는 대회가 좀 있고, 한 번쯤은 정리했어야 할 내용이기 ..

※ 이 문제를 풀기 전에는 이 문제 를 미리 풀고 오시는 것을 추천드립니다. ※ 이 포스팅을 보시기 전에는 이 포스팅 을 미리 보고 오시는 것을 추천드립니다. ※ 이 포스팅은 BOJ 14435 놀이기구 2의 풀이를 모두 알고 있다고 가정하고 작성되어 있습니다. 문제 링크 : https://www.acmicpc.net/problem/18473 (R5) 문제 태그 더보기 union & find, smaller to larger 문제 풀이 일단 가장 간단하게 시간복잡도에 상관없이 문제를 푸는 방법에 대해서 생각을 해보자. 1부터 m번까지의 간선을 모두 보고 되는 간선을 체크하자. 당연하게도 우리는 가능한 간선들이 바뀔 때마다 계속해서 번호가 가장 간선을 선택해야하므로, 수를 추가하거나 빼면서 이를 관리하고, ..

문제 링크 : https://www.acmicpc.net/problem/9446 문제 태그 더보기 DP,정렬 문제 소개 모든 물건을 각 가격에 살 수 있다. 하지만, 조합식에 따라서 두 물건을 합쳐 새로운 물건을 만들 수도 있다. 이때 1번물건을 만들기 위해서 필요한 최소가격을 구하자. 문제 풀이 문제를 보고 DP가 생각이 났다. DP table 정의도 바로 DP[i]=i번째 물건을 얻는 데 필요한 최소 비용. 또한 식은 i,j로 k를 만들 때 $DP[k]=min(DP[k],DP[i]+DP[j])$로 업데이트를 할 수 있다. 여기서 DP의 필요조건을 생각해보자. 어떤 DP table을 채울 때 사용되어진 값들이 있다면 그 사용되어진 값들은 확정된 상태여야 한다. 즉, 위의 식으로 따지면 DP[k]의 최종..

이번 Segment Tree 심화는 Euler Tour Tree이다. 난 DFS Ordering Tree라는 이름으로 먼저 접했고, 이쪽이 좀 더 내용을 설명하기에 적합하다고 생각하지만 DFS Ordering Tree라는 이름은 사용을 거의 안하는 것 같다. 그래도 난 일단 DFS Ordering Tree라는 이름을 기반으로 설명을 하려고 한다. 사전 지식 Segment Tree, DFS DFS Ordering Tree 이 테크닉의 전체적인 요점은 트리를 일자로 편다는 것이다. 특히 트리를 일자로 펴서 리프로 만들어 버리고 그 리프들을 이용해 새로 세그먼트 트리를 만드는 것이다. 이때 트리를 일자로 펴는 방식은 이름 그대로 DFS Ordering을 통한 방식을 사용한다. When? 우리는 DFS Orde..

문제 링크 : https://www.acmicpc.net/problem/13557 문제 태그 더보기 Segment Tree 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x1 y1 x2 y2: x1 ≤ i ≤ y1, x2 ≤ j ≤ y2, i ≤ j인 모든 (i, j)에 대해서 Ai + ... + Aj의 최댓값을 출력한다. (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ N, x1 ≤ y1, x2 ≤ y2) 문제 풀이 주어진 구간 내에서 최대 부분합을 구하는 문제는 Segment Tree를 이용해서 풀 수 있음이 잘 알려져 있다. 특히 "금광 세그"라고 불리는 테크닉이다. 이 부분에 대해서는 이 글 을 참조하자. 관찰 1..