https://www.acmicpc.net/problem/16955문제구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 작성하시오. 오목에서 승리했다는 것은 자신의 돌이 5개 이상 연속한다는 것이다. 연속은 가로, 세로, 대각선 방향 모두 가능하다.입력총 10개의 줄에 바둑판의 상태가 주어진다. '.'는 빈 칸, 'X'는 구사과의 돌, 'O'는 큐브러버의 돌이다. 입력으로 주어지는 바둑판에서 구사과의 돌의 개수와 큐브러버의 돌의 개수는 항상 일치하며, 아직 승자가 정해지지 않은 상태만 입력으로 주어진다.출력구사과가 턴을 한 번 가져서 이길 수 있으면 1, 없으면..
Koala - 14기
https://www.acmicpc.net/problem/17266코드#include#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;vector stand;int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n; cin >> m; for (int i = 0; i > x; stand.push_back(x); } int ans = max(stand[0], n - stand[stan..
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..
