본문 바로가기

개발/알고리즘

 (30)
거듭제곱 구하기 문제 정수 a와 m이 주어 졌을때, a의 m 거듭제곱을 1,000,000,007 로 나눈 나머지를 출력하는 문제이다. 입력 두 정수 a와 m이 주어진다. 1 a >> m; long long res = pow(a, m); cout
나누기 문제 아래와 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 0으로 칠해져 있거나 1로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 0 또는 1로 칠해진 색종이를 만들려고 한다. 11000011 11000011 00001100 00001100 10001111 01001111 00111111 00111111 전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 ..
cow party 문제 N 개 농장의 (편의상 1 ,2 .. , N) 의 대표 암소 한 마리가, X ( 1 c; pathV[a].push_back({ a,b,c }); } int MAX = 0; for (int i = 1; i MAX) { MAX = res1 + res2; } } cout
가장 먼 두 도시 문제 N개의 도시가 있고, 임의의 두 도시 사이에는 항상 도로가 있다. 도시는 1번부터 N번까지 차례대로 번호가 매겨져있다. a번 도시에서 b번 도시로 가는 도로의 길이와 b번 도시에서 a번 도시로 가는 도로의 길이가 다를 수 있다. 어떤 도시에서 다른 도시로 가는데, 직접 연결된 도로를 통해 가는 것보다, 다른 도시들을 거쳐가는 것이 좋을 때가 있다. a번 도시에서 b번 도시로 가는 거리란, a번 도시에서 하나 혹은 여러 도로를 거쳐 b번 도시로 가는 최단 거리를 의미한다. 마찬가지로 a번 도시에서 b번 도시로 가는 거리와 b번 도시에서 a번 도시로 가는 거리가 다를 수 있음에 유의하라. 도시의 도로 정보가 주어졌을 때, 거리가 가장 먼 두 도시 사이의 거리를 구하는 프로그램을 작성하시오. 입력 입력의..
보물섬 문제 강희는 악마의 바다에 어마어마한 보물이 숨겨져 있는 보물섬이 있다는 정보를 입수했다. 하지만 악마의 바다에는 해류가 매우 복잡하게 흐르고 있기 때문에 강희는 좀처럼 보물을 얻고 돌아올 길을 찾기가 힘들어 여러분에게 도움을 요청했다. 강희가 악마의 바다에서 보물을 찾아올 수 있는 최단 시간을 계산하자. 악마의 바다에는 1번부터 N번까지 섬이 N개가 있으며, 서로 다른 섬들을 연결하는 해류가 M개 존재한다. 해류는 한 방향으로만 흐르며 어떤 두 쌍을 잇는 해류가 여러개 존재할 수도 있다. 강희는 현재 1번 섬에 있으며, 보물섬에 들렀다가 다시 1번 섬으로 돌아와 악마의 바다를 탈출하려고 한다. 입력 첫 번째 줄에 줄에는 섬의 개수 N과 섬들을 잇는 해류의 개수 M이 공백으로 분리되어 주어진다. (2 ≤..
피크닉 문제 소들은 피크닉을 갈 예정이다! 각 존의 K(1 cow[k];//소의 위치 } int s, e; for (int m = 1; m > s >> e; pathV[s].push_back(e); } for (int k = 1; k
유령선 문제 강희는 정신을 차려보니 낯선 유령선에 납치당해 있었다. 강희는 유령들이 자고 있는 낮 시간에 몰래 유령선에 있는 구명보트를 이용해 탈출하려고 한다. 유령선의 갑판은 동일한 크기의 정사각형 모양 판자가 가로로 W개, 세로로 H개 이어진 모양으로 되어 있다. 강희는 현재 서 있는 위치에서 상하좌우로 움직일 수 있다. 유령선은 매우 낡았기 때문에 강희가 딛고 있는 판자를 벗어나면 판자가 부서지고 만다. 심지어 이미 부서져 있는 판자도 존재한다. 물론 강희는 유령이 아니기 때문에 부서진 판자는 걸어서 지나갈 수 없다. 판자가 너무 많이 부서지면 유령들이 화를 내기 때문에 강희는 가장 작은 개수의 판자를 파괴하면서 유령선에서 탈출하려고 한다. 강희가 유령선에서 탈출하는 것을 돕는 프로그램을 작성하자. 시간제..
위상 정렬 문제 DAG(Directed Acyclic Graph)는 방항셩이 있는 간선으로 이루어진 그래프 중, 사이클이 없는 그래프를 의미한다. DAG에서는 위상 정렬을 항상 할 수 있다. DAG가 주어질 때, 위상 정렬을 하는 프로그램을 작성하시오. 입력 첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E가 공백으로 분리되어 주어진다. (1 ≤ V ≤ 50,000, 1 ≤ E ≤ 100,000) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x에서 출발하여 y에 도착하는 유항 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y) 주어지는 그래프는 항상 DAG이고, 1번으로 들어오는 간선은 없다. 출력 첫 번째 줄에 위상 정렬의 결과를 출..

티스토리툴바