본문 바로가기

전체 글

 (147)
백준 1368: 물대기 https://www.acmicpc.net/problem/1368 이 문제를 읽으면 "최소 스패닝 트리"로 풀어야 할 것 처럼 보인다. 그래서 자주 사용하는 크루스칼 알고리즘을 사용할 것인데, 관건은 논에 직접 우물을 파는 것을 어떻게 구현할 것이냐?이다. 이 문제를 풀기 위해서 떠오른 여러 아이디어를 두서 없이 나열해 보자면- 직접 우물을 파는 것을 자기 자신을 가리키는 그래프로 표현해보자.- Sort할 때, Edge 한쪽을 직접 판 경우도 더해서 Sort한다.- 2번에 이어서, 직접 우물을 파는 경우도 Array에 넣고 직접 우물을 파는 경우에는 Sort를 다시한다.- 최소 스패닝 트리를 미리 만들고, 우물을 파는 경우의 수를 조사하자등등이 있었다. 문득, 재미있는 예제가 하나 떠올랐다. 예제 입력을..
백준 12850: 본대 산책2 https://www.acmicpc.net/problem/12850 이 문제는 보자마자 어떻게 풀어야 할 지 막막했다. 태그는 "분할 정복을 이용한 거듭제곱"인데, 이거를 어떻게 사용해야할 지 감이 전혀 잡히지 않았다. 그럼에도 정답률은 80%를 넘기니, 내가 모르는 테크닉이 있는것 같아서, 결국 구글링을 하였다. 결론부터 말하자면 아니였다. 충분히 내가 알고 있던 지식 내에서 해결할 수 있는 문제였다. 중요한 점은 그래프를 행렬로 나타낼 수 있다는 것이다. 문제에서 주어진 그래프를 인접행렬로 나타내면 다음과 같다.{0, 1, 1, 0, 0, 0, 0, 0},{1, 0, 1, 1, 0, 0, 0, 0},{1, 1, 0, 1, 1, 0, 0, 0},{0, 1, 1, 0, 1, 1, 0, 0},{0, 0, ..
백준 1222: 홍준 프로그래밍 대회 오늘 푼 문제는 백준 1222: 홍준 프로그래밍 대회이다.https://www.acmicpc.net/problem/1222 일단 문제를 보고 처음 떠올린 답안은 1~2000000까지 전부 순회해서 답을 구하는 것이였다.하지만, 배열의 길이가 최대 200,000이 만큼 시간초과는 피할 수 없기에 이 안은 포기하고 다른 안을 모색하였다.문득, 이러한 문제는 에라토스테네스의 체를 변형시켜 사용하는 게 좋을 거란 생각이 들었고, 새로운 안이 떠오르기 시작하였다. 에라토스테네스에서 약수를 구하는 방법이 있는데, 이 방법을 변형시켜서, 각 2,000,000의 최소 약수를 구하고, 입력 배열을 순회하며, 각 값의 최소 약수를 카운팅한다. 그리고 최종적으로 (카운팅 된 값 * 최소 약수)로 값을 구하는 것이 어떠한 가..
백준 17469: 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 이 문제를 풀기 위해서는 우선 https://www.acmicpc.net/problem/13306 이 문제를 푸는 것이 선행되어야한다. 이 문제에 색깔을 추가한 것이 바로 이번에 다룰 문제이다. 13306번 문제는 해결책은 간단하게 언급하자면 쿼리를 바로 처리하지 않고 저장한 후, 쿼리를 뒤에서 순회하며 연결을 끊는 작업을 연결하는 작업으로 바꾸면서 답을 구하는 방식이다.#include #include using namespace std;int N, Q, X, A, C, D, P[200001], p;vector tmp;vector ans;vector>> q;int find(int u){ if (u == P[u]) return u; ret..
백준 2171: 직사각형의 개수 이번에 푼 문제는 백준 2171: 직사각형의 개수이다.https://www.acmicpc.net/problem/2171 처음엔 이차원 Hash_map, 혹은 이차원 Set을 사용해서 풀려고 했다. X좌표들을 두개의 iterator를 활용해서, 하나의 iterator를 기준으로 Y좌표를 돌며, 다른 쪽의 그 Y좌표가 있는지 확인하는 방법이다. 당연하겠지만, 이 방법은 통하지 않았다. 왜냐하면, 동일하게 있더라도 그것은 단 한 쌍의 좌표의 얘기이다. 좌표는 두 쌍이 필요한데, 한 쌍으론 부족하다. #include #include #include #include using namespace std;int N, X, Y, ans = 0;vector P;unordered_map> um;int main(){ ios..
백준 1332: 풀자 이 문제는 2달 전에 풀이를 시도했다가, 틀려서 그냥 내버려두었던 문제이다.https://www.acmicpc.net/problem/1332  풀이가 어려운 것은 아닌데, 내가 이 문제에 붙은 태그로 인해서 되려 더 어려운 길을 걷게 된 것 같다. 그렇기에, 이번에 정리하고자 한다. 나는 이 문제를 보자마자, Bruteforce를 떠올렸다. 하지만 N의 길이가 50이라서 잘못했다간 시간 초과가 되지 않을까 두려워서 혹시나 해서 태그를 보니 Bruteforce가 맞았다. 그래서 일단 이전의 Bruteforce 문제들 처럼 재귀함수를 활용하였다. 나는 solve 함수를 다음과 같이 정의하였다.void solve(int idx, int mn, int mx, int cnt) { if (mx - mn >= V) ..
백준 1469: 숌 사이 수열 시험삼아 적당히 난이도 있는 문제를 풀어보자https://www.acmicpc.net/problem/1469 일단 알고리즘 파악부터 하자. X의 크기가 최대 8이다. 이런 경우는 대게 브루트포스 내지 백트래킹 문제이다. 그러므로 나는 백트래킹으로 풀기를 결정했다. 이제 알고리즘을 결정했으니 문제를 풀자, input을 제외한 필요한 변수엔 무엇이 있을까?우선 정답을 저장할 공간이 필요하다. 백트래킹을 위해 뒤에 원소를 넣고 빼는 것이 가능하고, 정답을 읽기위한 순회가 가능한 자료구조가 적당하다. 그래서 나는 배열이 적합하다고 판단했다. 여기서는 C++의 vector를 사용하기로 하였다. 백트래킹을 위한 함수에 매개변수로 전달하는 것보단 전역변수로 빼는 것이 시간을 덜 소모할것이다. 또 뭐가 있을까? 이전에..
백준 1132: 합 현재 매일매일 알고리즘 문제를 해결 중에 있고, 오늘 기준으로 915일 연속으로 문제를 해결하였다.하지만 가끔 하고 싶은 말이 있는 문제가 더럿 생긴다. 그래서 자주는 아니지만 시간이 되면 글을 적어보려한다. 이번에 다룰 문제는 백준 1132, 합이다.https://www.acmicpc.net/problem/1132 1132번: 합N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로www.acmicpc.net이 문제는 어디서 본 것 같다. 그렇다 백준 1339와 유사하다.https://www.acmicpc.net/problem/1339 1339번: 단어 수학첫째 ..

티스토리툴바