출항사

간단한 그래프 문제이다. 1번 노드를 기준으로 리프 노드까지 탐색하고, 이때 지나갈 수 없는 노드의 번호가 주어진다. 이때 리프 노드까지 정상적으로 탐색할 수 있는가?를 묻고 있다. 1번 노드를 기준으로 BFS or DFS를 돌리고, 리프 노드들을 확인해 하나라도 도달한 케이스가 있는지 확인하면 모든 조건을 만족할 수 있다. 현재 그래프가 유향 그래프로 주어지므로, 리프 노드는 간선의 개수가 0인 노드들이 될 것이다. 이 노드들을 모두 확인했을 때 도달한 적이 있다면 yes를, 하나라도 도달할 수 없다면 Yes를 출력하자. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 100010 #define X..

팀의 초기 순위가 주어진다. 여기서 M개의 팀 쌍의 순위가 바뀌었다는 정보가 주어졌을 때, 가능한 경우인지 가능하다면 최종 순위는 몇 위인지 찾아야 한다. 그리고 가능하더라도 순위의 경우의 수가 1이 아니면?를 출력해야 한다. 순서가 정해져 있고, 이 순서를 기반으로 탐색을 진행해야 하기에 위상정렬을 떠올려볼 수 있다. 각 인덱스를 기준으로 자신보다 높은 순위가 몇개 남았는지를 세주자. M개의 정보가 들어온다. 이때 x, y중 초기 순위가 더 높은 값이 있고 작은 값이 있다. 이 둘을 바꾼다는 것은 이 우위가 바뀐다는 것이고, 간선의 방향을 뒤집어 줘야 한다. 그리고 나보다 높은 순위가 몇 개 남았는지 세는 값도 업데이트를 해줘야 한다. 자 이제 새롭게 만든 그래프를 기반으로 위상정렬을 돌리자. 이때 최..

간단한 탑다운 DP 문제이다. Ai = A[i/P] + A[i/Q]일때, An을 구해야 한다. N이 최대 1e12까지 가능하다. P와 Q는 최소 2부터 시작이다. 따라서 트리 구조로 탐색을 진행한다고 생각해봤을때, 트리의 깊이가 급격히 낮아지는 것을 알 수 있다. 중복되지 않는다고 해도 최대 log2 1e12안에 모든 탐색을 할 수 있다. 이는 깊이 38짜리 트리이다. 방문을 표시하기 위한 배열을 만들 수 없으니, map을 활용하기로 하자. 이제 배열대신 map에 값을 사용해서 재귀 탐색을 수행할 수 있다.이미 구했던 값을 다시 계산할 필요가 없으므로 메모이제이션 기법을 함께 활용하면 아주 간단히 풀린다. #include #define MINF 0x7f7f7f7f #define INF 2000000000..

N개의 u, v가 주어진다. 구하고 싶은 값은 K인데 i uj, vi < vj를 만족하는 K를 구해야 한다. K를 기준으로 생각해보자. K의 왼쪽과 오른쪽을 기준으로 가장 큰값과 가장 작은 값들만 전처리 해놓는다면, O(1)에 K가 조건을 만족하는지 알 수 있을 것이다. 왜냐면 결국 왼쪽에서 가장 큰값이 오른쪽에서 가장 작은값보다 클때 무조건 정답이 될 수 있기 때문이다. 그래서 O(N) 탐색 두번을 통해 왼쪽, 오른쪽을 기준으로 최소 최대값을 전처리하고, 전처리한 값을 기준으로 K를 찾으면 된다. 시간복잡도는 O(N)이 소요된다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #d..

문제를 해석하니 Set + 오프라인 쿼리 + 유니온 파인드 세 가지 기법을 활용하면 무조건 정답을 구할 수 있다는 풀이가 나왔다. 우선 모든 간선을 끊어주자. 그리고 쿼리를 뒤에서부터 수행하면서 노드를 하나씩 연결해 주자. 이때 부모 노드를 찾아줘야 하는데, 부모 노드에서 K개의 색깔을 얻을 수 있다면 해당 집합에 속한 모든 노드는 K개의 색을 얻을 수 있다. 부모 노드를 찾기 위해서는 유니온 파인드 알고리즘을 사용하면 된다. 그리고 색을 중복되지 않게 세줘야 하기 때문에 set으로 관리해 주자. 하지만, 여전히 문제가 있다. 자식 노드와 부모 노드가 merge 될 때, 자식 노드에 들어있는 색을 부모로 모두 옮겨야 하는데, 이 작업을 수행하는 시간 복잡도는 O(NlogN)이고, 최대 N번 수행되므로 최..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N개의 몸무게가 주어지고, 시소가 주어진다. 시소에는 2, 3, 4 칸 중 하나에 앉을 수 있다. 이때 균형을 맞출 수 있도록 앉는 경우의 수를 구해야 한다. N은 10만 이하이므로 O(N^2)에는 안풀린다. 우리가 궁금한 것은 개수다. 그러니 각 몸무게별로 인원 수를 map에 저장하자. 그리고 이 key 값들을 이용해서 짝의 개수를 세면 된다. 앉을 수 있는 자리가 2, 3, 4이므로 2중 for문을 돌려주자. 현재 몸무게를 w라고 할때, 2, 3, 4 모두에 앉혀봐야 한다. 그리고 이때 반대편에 앉을 수 ..

각 노드간의 거리가 주어졌을때, A -> B로 이동하는 최소 시간이 C보다 작거나 같은지 확인하는 문제이다. 노드의 개수가 500개, 쿼리의 개수가 1만개이다. 노드의 개수를 N, 쿼리의 개수를 K라고 하자. 그렇다면 간선의 개수는 N^2개가 되는 것을 알 수 있다. 쿼리가 들어올때마다 다익스트라를 돌리면 O(KN^2 log N)의 시간복잡도가 소요되기에 시간안에 문제를 해결할 수 없다. 따라서 N이 작은 것을 이용하면 되는데, 플로이드 와샬을 사용하면 된다는 것을 눈치챌 수 있다. O(N^3)에 모든 노드간의 거리를 전처리 해놓는다면 쿼리를 해결하는데 O(1)의 시간복잡도가 걸린다. 따라서 O(N^3)에 문제를 해결할 수 있다. #include #define MINF 0x7f7f7f7f #define ..

동전 2개가 주어질때, 하나의 동전만 떨어뜨리도록 적절히 움직이라고 한다. 최대 움직일 수 있는 횟수가 10회인점에 집중해보자. 매번 움직일 수 있는 경우의 수는 최대 4회이다. 따라서 4^10번의 경우의 수를 전부 돌려 동전 중 하나만 밖으로 나가는 경우가 존재하는지 확인하면 된다. 움직인 방향을 vector로 관리하고, 이 vector에 들어있는 방향으로 시뮬레이션을 돌려 움직여보자. 이때 하나의 동전만 밖으로 나가는 값을 찾으면 된다. 4^10번 만큼 경우의 수를 찾고, 시뮬레이션을 돌리는 최대 움직임이 10회이므로, 시간복잡도 O(4^10 * 10)에 문제를 해결할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #define MOD ..