본문 바로가기

전체 글

 (146)
트리와 띄엄띄엄쿼리 & 루트가 많은 트리? https://jungol.co.kr/problem/8663 트리와 띄엄띄엄쿼리 · Silver IISilver II · 22 solved users · 58 submissionsjungol.co.kr 트리에서 한 정점으로 부터 거리가 홀수, 또는 짝수인 정점에 특정 작업을 해주어야 하는 문제 유형이다.처음에는 하나의 노드에서 매번 dfs를 돌려서 거리가 짝수인 곳에만 작업을 수행하도록 할 계획이었다. 하지만, 노드 개수 30만에쿼리 개수 30만이라는 것을 보고 완전탐색은 아니라는 것을 그제야 깨달았다. 그렇다면 한 정점으로 부터 거리가 짝수 또는 홀수인 정점들에 작업을 한꺼번에 수행하는 것이 O(1) 밖에 안걸린다는건데...어떻게 하지?? 이 생각을 하고 그대로 막혀버렸다. 정올반 선생님의 해설을 듣..
Boj 7267 c++ 이탈리아어 문제 https://www.acmicpc.net/problem/7267 문제8개의 수영장 레인이 있다. N명이 사람의 수영 실력이 주어질 때, N명의 사람들을 a 명 이상 b 명 이하로 이루어진 팀으로 나눌 수 있다. 팀 내에서 사람들 간의 실력 차이가 최소화되도록 팀을 구성할 때, 차이의 최솟값을 구하시오. 접근 & 풀이우선 각 사람들을 정렬 시켜 놓은 후, 연속한 a ~ b명을 고르는 것이 유리하다는 것을 알 수 있다.그리고 앞서 구성한 팀의 최소 차이와 현재 팀의 최소 차이 중에서 큰 것을 참조하고, 현재 dp 값의 최솟값을 유지해야 하기 때문에초기값을 inf로 둔 후, min과 max를 동시에 사용하여 점화식을 구성해주면 된다. 정답코드#include #define fastio ios_base :..
Boj 2666 벽장문의 이동 / 11570 환상의 듀엣 c++ https://www.acmicpc.net/problem/2666 벽장문의 이동문제길이가 n인 벽장이 있고, 이중에서 2개의 벽장만 열려있다. 이웃한 벽장이 열려있으면 그 칸으로 문을 옮길 수 있다.문을 옮기는데에는 1만큼의 시간이 걸린다. 벽장을 열고 싶은 순서가 주어질 때 모든 벽장을 열기 위해 걸리는 최소 시간을 구해야 하는 문제이다. (3 관찰 & 풀이 현재 열어야 하는 칸이 arr[num] 이라고 하자. 현재 칸을 열기 위해서는 열려있는 두개의 벽장문 중에서 하나를 현재 칸 쪽으로 끌어오면 된다.직접 그려보면 벽장문이 열려있는 두개의 칸이 a, b라고 하고 현재 칸을 arr[num] 이라고 하면 1. abs(arr[num] - a)2. abs(arr[num] - b) 둘 중 하나 만큼 시간이..
Boj 33879 c++ 러시아어 문제 https://www.acmicpc.net/problem/33879 나는 많은 조건 분기 문제에 정말 약한 것 같다. 문제 0과 1로 이루어진 문자열이 있다. 1이 2개 이상 연속한 경우에만 1의 개수를 세어준다고 한다.0을 x개만큼 1로 바꿀 수 있을 때 1의 개수의 최댓값을 val[x] 라고 하자. 길이 n인 문자열과 q가 주어지고, q개의 질문(x)이 있을 때, 각 질문마다 val[x]의 값을 출력하면 되는 문제이다 관찰 처음에는 이상한 관찰을 했었다."1과 0 사이의 간격이 짧을 수록 좋다"하지만 당연하게도 수많은 반례들이 쏟아져 나왔다. 이 문제에서 했어야 하는 가장 핵심적인 관찰은 0을 1로 바꿀 때 늘어나는 1의 개수가 3, 2, 1인 행동이 있다는 것이다. 01010의 가운데 값을 채우는..
Boj 2529 c++ 부등호 https://www.acmicpc.net/problem/2529 문제 길이 10 이하인 부등호 문자열이 주어질 때, 주어진 부등호를 만족시키는 가장 큰 정수와 가장 작은 정수를 구해야하는 문제이다.단, 숫자를 중복해서 사용해서는 안된다. ex) min : 0 2 1max : 8 9 7 구현n 제한이 매우 작기 때문에, dfs로 큰 것 부터 하나 찾아주고, 작은 것 부터 하나 찾아주는 식으로 풀 수 있다.방문 처리, 처음 시작할 때 예외처리 등, 조금 신경써줘야 할 것이 있다. 가장 작은 수를 구할 때에는 첫번째 수 0에서 시작하여 불가능한 경우, 숫자를 1씩 늘려주면 된다.가장 큰 수를 구할 때에도 비슷하게 9에서 시작하여 불가능한 경우 숫자를 1씩 줄여나가면 된다. 이후 로직은 부등호에 맞춰서 인..
Boj 5626 c++ 제단 https://www.acmicpc.net/problem/5626 정올반 문제이다.문제길이가 n인 제단이 주어진다. 제단을 이루는 숫자는 제단의 높이를 뜻한다. 제단이란, 처음과 끝이 0이고, 연속한 두 수의 차이가 1이하인 수열을 뜻한다. 도둑이 훔쳐간 제단열의 높이는 -1로 표시된다. 도둑이 훔쳐가 불완전한 제단의 정보가 주어질 때, 가능한 제단의 모양의 경우의 수를 구해야 한다. 단, 제단의 길이는 최대 10000이며, 제단열의 높이 또한 최대 10000이다.관찰&풀이 우선 이 문제가 왜 dp로 풀이가 가능한지 생각해보자.우선 현재 칸의 인덱스가 idx이고 도둑이 훔쳐가 -1로 표시된다고 생각해보면 현재 칸으로 가능한 높이는 총 idx-1개이다. ex) ....................-1(7번..
Boj 33579 디미그래프 c++ https://www.acmicpc.net/problem/33579문제주어진 그래프가 다음 조건을 만족시키는지 확인해야 한다.임의의 서로 다른 두 정점을 연결하는 경로가 하나 이상 존재한다.사이클이 오직 하나 존재한다.사이클에 포함되는 정점과 사이클에 포함되지 않는 정점을 연결하는 간선은 정확히 하나 존재한다.사이클에 포함되지 않는 정점의 차수는 2 이하이다. 즉, 사이클이 하나 있고 여기에 꼬리가 하나 달린 올챙이 모양 그래프인지 판별하라는 것이다. 접근 & 풀이처음에는 3번 조건을 간과한 채로 막연하게 "아하, 올챙이 모양이니까 차수가 3인 정점이 1개, 차수가 1인 정점이 한개, 그리고 나머지가 차수가 2라면 조건을 만족하겠구나!"라는 생각으로 구현했다가 80% 언저리에서 틀리고 왜 틀렸는지 고민했..
Boj 12864 c++ 사서왕 준서 https://www.acmicpc.net/problem/12864 문제 책의 번호가 나열된 길이 n의 실수 수열과 각 책을 옮기는데에 드는 비용이 주어진다.나열된 책들을 번호가 오름차순이 되도록 책을 옮길 때, 최소 비용을 구해야한다.(1 접근책을 옮기는 위치에 관계 없이 항상 옮기는 비용이 일정하다면, 최대한 비용이 작은 책들을 옮기는 것이 좋을 것이다.이를 반대로 생각하면 우리는 비용의 합이 가장 큰 증가하는 부분수열을 구한 후, 전체 비용합에서 이를 제외해주면책을 정렬하는데 드는 최소 비용을 구할 수 있을 것이다. 전체코드 #include using namespace std;int dp[5050], cost[5050], ans, sum, N;double arr[5050];int main()..
Boj 10451 c++ 순열 사이클 https://www.acmicpc.net/problem/10451 *순열 사이클이란?1234567832781456 과 같은 순열을 그래프로 나타내면그림과 같은 그래프가 만들어진다.이 문제에서는 순열이 주어졌을 때 순열 사이클의 개수를 구해야 한다. 입력이 주어질 때 순열 그래프를 생성한 후,여기서 자기 자신으로 돌아올 때 까지 방문 처리한 후, 한 사이클이 끝날 때마다 cnt를 증가시키면 풀 수 있다. #include using namespace std;int main() { int t; cin >> t; while(t--) { int n, cnt = 0; cin >> n; vector arr(n+1); vector connected(n+1); vector visited(n+1, fals..
32073 c++ XOR 최대 https://www.acmicpc.net/problem/32073 이진수로 이루어진 문자열 s가 주어질 때, 해당 수의 부분문자열 s1, s2을 XOR 연산한 값 중에서 최댓값을 구해야 하는 문제이다. 우선 가장 중요한 관찰은 가장 왼쪽에 있는 비트가 1이어야 하기 때문에 두 부분 문자열 중에서 한개는 반드시 그 문자열 자체라는 것. 그리고 해당 문자열의 길이와 가장 왼쪽에 있는 1의 위치가 일치하지 않을 수도 있기 때문에 시작점을 찾아줘야 한다는 것. 그리고 가장 핵심적인 관찰! 원래 문자열에서 1이 처음 시작된 시점부터 끝나는 지점까지를 s-e라고 했을 때, 그 후 0이 연속적으로 나오는 부분이 있을 것이다.우리는 이 부분을 1로 만들면 된다.그리고, 0이 연속적으로 나오는 것의 길이를 l이라고 했..

티스토리툴바