슈뢰딩거의 진돗개

어떤 한 그래프에서 '모든 정점으로 가는 경로가 존재하고 유일하다' == Tree 이용한 문제들 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 그래프를 빙자한 트리 문제가 나올 때마다 logN 스케일로 원하는 노드에서 노드값을 구해줘야하는 상황이 ..

최소 스패닝 트리 : 간선의 가중치가 있는 그래프의 부분 그래프 중, 사이클이 없으며 가중치의 합이 최소인 부분 그래프 최소 스패닝트리를 만드는데에는 크루스칼이 더 많이 쓰이지만 나는 Priority_queue를 사용하는 프림 알고리즘이 익숙하다. 사이클 체크를 해줄필요도 없이 임의의 노드로 부터 출발하여 그 노드와 인접한 모든 노드를 Priority_queue에 넣어주어서 가장 가까운 위치에 있는 노드를 방문해주면 끝난다. 구현도 간단하고 이름도 이뻐서 애용중,,, 크루스칼과 시간 복잡도도 거의 비슷해서 초록 책에서도 취향대로 가라고 한다. while(!pq.empty()){ long double dist=pq.top().first; int dest=pq.top().second; pq.pop(); if..

20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 아이디어: 매번 DFS돌리며 사이클을 검출하려면 TLE가 발생하니 각 노드를 하나의 집합으로 두고 같은 집합끼리 묶으려 하면 사이클임을 알 수 있다. 결국 DFS가 아닌 Union-find를 쓰는 문제이나, 노드의 숫자인 N= 500,000이며 merge시행 횟수인 M= 1,000,000 이므로 O(N)으로 Union-find를 하면 TLE 따라서 find과정에서 만나는 과정마다 부모를 최상위 노드로 설정해가며 O(logN)으로 만들 필요가 있었다. int ..

2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 아이디어 숫자들을 정점으로 생각하면 뽑은 숫자들의 집합이 일치한다 => 사이클이 있다고 볼 수 있다. 사이클을 검출하는 방법 : DFS DFS를 돌다가 DFS가 아직 다 돌지않은 정점을 만나게 되면 사이클이 있다고 생각할 수 있다. (다만 방문여부와는 별개로 생각해줘야한다. 처음 방문하는 정점도 DFS를 다 돌진 않은 상태니까) DFS를 돌면서 자신이 이전에 방문한 정점을 저장해준다면 DFS가 다 안돈 정점부터 차례대로 자기 자신을 만날 때 까지 정..

사실 그리디 전략자체는 쉽게 떠올릴 수 있는데 구현 한번 꼬이면 디버그가 어려웠던 문제. 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net 배차 요청이 N개, 버스 배차가 M개가 주어진다. (1

오늘 어이없게 시간 날려서 박제용으로 포스트 /* 인수를 넘겨 받을 때 int를 사용하게 되면 중간 계산 결과가 overflow 발생한다 */ int cross(pair v1,pair v2){ long double ans=v1.first*v2.second-v1.second*v2.first; if(ans>0) return 1; else if(ans==0) return 0; else return -1; } /*주의 : 일직선상에 놓이면 a*b==0 && c*d==0이지만 역은 성립 안한다. 이걸 놓쳤다.*/ /* 세 점이 일직선상에 놓이게 되면 a*b==0 && c*d==0 따라서 4점이 일직선상에 놓이게 되는 경우에도 위 사례가 성립하지만 4점이 일직선상에 놓인다고 해서 둘다 0이 되진 않는다.*/ if(..

2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net (이 문제 풀다가 추억 돋아서 BEMANI REMIX 듣다가 살짝 해 멘 문제) DP는 DP인데 재귀를 사용하는 DP입니다. 처음에는 왼발 오른발 위치를 기억하고 i번째 일을 마쳤을 때 값을 기준으로 점화식을 놓으려다가 막혀서 재귀 함수를 돌리되 memozation을 이용하는 것으로 풀었습니다. 가능한 case의 수는 지시사항이 N개 있을 때 2^N개입니다. 이를 다 처리하려면 답이 없습니다. 일단 처음 지시사항을 실시할 때 왼..

https://www.acmicpc.net/problem/1562 생각보다 엉뚱한 곳에서 해멘 문제입니다. 계단수는 문제 조건처럼 45656마냥 인접한 각 자리 숫자들이 1씩 차이나는 숫자입니다. 몰랐는데 이 문제가 쉬운 문제로 N이 주어졌을 때 마지막 자리숫자를 저장해서 푸는 문제가 있었죠. 이 방식이 원본 문제에서는 적용이 안될줄 알고 규칙을 찾아 점화식으로 풀려했는데 네, 원본 문제에서도 적용됩니다. dp배열을 다만 3차원으로 써서 dp[현재 수의 길이][마지막 자리의 숫자][현재 상태] = 숫자의 개수 이런 식으로 저장하는데 이때 현재 상태는 비트 마스킹을 활용하여 모든 숫자가 한번 씩 사용됬는지 표시합니다. 예를 들어 0 0 0 0 0 0 0 1 0 0 이면 숫자 2를 제외하고는 나머지 숫자가 ..