https://www.acmicpc.net/problem/2635문제 설명다음과 같은 규칙에 따라 수들을 만들려고 한다. 첫 번째 수로 양의 정수가 주어진다. 두 번째 수는 양의 정수 중에서 하나를 선택한다. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다. 풀이주어지는 첫번..
분류 전체보기
https://www.acmicpc.net/problem/11383문제 분석분류문자열구현문제 설명정우는 "뚊"과 "돌돔"을 의미하는 두 이미지를 받았다. 과연 두 그림이 같은지 검사해보자. 즉 N× M 크기의 이미지와 N ×2 M 크기의 이미지가 주어질 때 첫 번째 이미지를 가로로 두 배로 늘이면 두 번째 이미지가 되는지 검사하는 프로그램을 작성하라.입력입력의 첫 번째 줄에 N, M (1 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄의 각 줄에는 M개의 문자가 주어진다. 다음 N개의 줄의 각 줄에는 2M개의 문자가 주어진다. 모든 문자는 영문 알파벳 대문자 혹은 소문자이다.출력첫 번째로 주어진 이미지를 가로로 두 배로 늘렸을 때 두 번째 이미지가 된다면 "Eyfa"을 출력하고, 되지 않는다면 "No..
https://www.acmicpc.net/problem/8989문제기원이의 방에는 시침과 분침으로 이루어진 아날로그 시계가 있다. 기원이는 시침과 분침이 형성하는 각도 중 작은 각도를 측정하는 것이 취미이며, 이 각도는 0보다 크거나 같고 180보다 작거나 같다. 기원이는 서로 다른 5개의 시간이 hh:mm의 형태로 주어졌을 때, 중간값을 갖는 각도가 몇 시 인지 궁금해져서 이를 알아내는 프로그램을 만들고자 한다. 즉, 주어진 시간들이 이루는 각도를 기준으로 오름차순 정렬했을 때, 세 번째에 위치한 시간을 찾으면 되는 것이다. 만일 동일한 각도를 갖는 시간들이 있으면, 빠른 시간 순서대로 정렬한다. 예를들어 06:05, 07:10, 03:00, 21:00, 12:55 가 주어졌으면, 정렬 결과는 12:..
1719번: 택배 (acmicpc.net)코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)import heapq# 노드200, 경로10000n, m = map(int, input().split()) INF = int(1e9)graph = [[] for _ in range(n+1)]# 간선 정보 입력for _ in range(m): a, b, c = map(int, input().split()) # ab가 c비용 graph[a].append((b, c)) graph[b].append((a,c))def find(target): if target == ans[target]: return targ..
https://www.acmicpc.net/problem/2667코드#include#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;int n;vector graph[900];bool visited[25][25];vector home;int arr[25][25] = { 0, };int homecnt = 0;int complexnum = 0;void dfs(int i,int j) { visited[i][j] = true; homecnt++; if (j-1>=0 && arr[i][j - 1] ..
https://www.acmicpc.net/problem/15808난이도P5유형다익스트라풀이사실 이게 왜 P5인지 모르겠는데 p랑 q중 적은 쪽 모두에서 다익스트라를 돌려주면 된다. p+q는 n보다 작으므로 최댓값은 n/2이다. 시간복잡도는 O(VElogV)이긴 한데 /2가 무시할만한 그건 아니다. 충분히 돌아갈것 같았다. p에서 돌렸으면 q노드들 확인, q에서 돌렸으면 p노드들 확인해주면 된다.정답이 음수가 될 수 있다. (이게 왜..)#include #include #include #define MAX 1001#define INF 1000000001using namespace std;vector> graph[MAX];vector> pp;vector> qq;int dijk(int N,vector> st..
https://www.acmicpc.net/problem/15808알고리즘 분류그래프 이론데이크스트문제영선이는 요즘 여행에 빠져있다. 그래서 짧게나마 여행을 다녀오고 싶었던 영선이는 주말을 활용해 여행 갈 계획을 세우고 있다. 하지만 영선이는 가고 싶은 여행지가 너무 많아 고민 중이며, 숙소 또한 좋은 곳으로 가고 싶기에 여행지와 숙소를 기반으로 계획을 작성하려 한다.영선이는 가고 싶은 여행지 리스트와 숙소 리스트를 미리 조사하여 작성했다. 그리고 각 여행지와 숙소에 조사한 자료를 통해 기대치를 매겼다. 시간이 없기에 영선이는 여행지 한 곳, 숙소 한 곳을 방문할 것이며, 이때 선택된 장소들의 기대치 합이 최대가 되는 여행 계획을 작성할 것이다.또한, 여행지와 숙소 사이의 거리가 멀다면 여행지에서 관광을..
최소비용 구하기 2 스페셜 저지!https://d2gd6pc034wcta.cloudfront.net/tier/13.svg시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB3361912739908636.652%문제n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.입력첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리..
문제 링크https://www.acmicpc.net/problem/1719접근 방법다익스트라 알고리즘은 "어떤 노드까지의 최단거리를 알 때, 그 노드와 연결된 노드들의 최단 거리를 갱신"하며 정답을 구하는 알고리즘이다.그러한 알고리즘의 특징을 이용해서 다음과 같은 접근을 하였다.다익스트라 알고리즘을 진행할 때, 알고리즘의 효율성을 위해 우선순위 큐를 사용한다. 우선순위 큐에는 최단 거리가 갱신된 노드가 담긴다.우선순위 큐에서 어떤 노드 A가 나온다고 가정해보자. (우선순위 큐의 top이 노드 A)노드 A로 향하는 최단 거리는 확정되었다. (큐의 내용과 실제 노드 A의 최단 거리를 비교해야함)A 노드가 다익스트라 알고리즘을 실행한 루트 노드가 아니라면 루트 노드에서 A 노드로 향하는 이전 노드가 있을 것이..
https://www.acmicpc.net/problem/2606 코드from collections import dequen=int(input()) # 컴퓨터 개수v=int(input()) # 연결선 개수graph = [[] for i in range(n+1)] # 그래프 초기화visited=[0]*(n+1) # 방문한 컴퓨터인지 표시for i in range(v): # 그래프 생성 a,b=map(int,input().split()) graph[a]+=[b] graph[b]+=[a]visited[1]=1 Q=deque([1])while Q: c=Q.popleft() for nx in graph[c]: if visited[nx]==0: Q.a..
문제 링크https://www.acmicpc.net/problem/1327접근 방법처음 문제를 읽었을 때 반드시 K 개수의 숫자를 뒤집어야함에 유의하지 않고 생각해서 K = 3이고 초기 순열이 5 4 3 2 1인 경우 숫자 1, 2는 뒤집지 못한다는 점을 놓쳐서 시간을 많이 허비했습니다. 역시 문제는 꼼꼼히 읽어야합니다.해당 문제에서 만들 수 있는 순열을 순열이 아닌 모든 숫자를 이어붙인 하나의 숫자(또는 문자열)라고 생각해보겠습니다.예를들어 5 4 1 2 3이라는 순열이 주어졌을 때 이를 순열로 보는 것이 아닌, 54123이라는 숫자(또는 문자열)로 생각한다면1 ~ N까지의 숫자가 하나씩 존재하고 N이 8로 매우 작기 때문에 러프하게 생각해 봤을때 어떤 순열이 주어져도 주어진 순열에서 만들 수 있는 순..
https://www.acmicpc.net/problem/14490문제n, m이 :을 사이에 두고 주어질 때 두 수를 최대한으로 약분해서 출력한다. (1 풀이두 수의 최대 공약수 x를 구하여 n/x : m/x를 출력한다. 코드#include #include #include using namespace std;string s;int n, m, x = 1;vector v;//최대공약수로 나누기int main() { cin >> s; for (int i = 0; i
