전체 글

2276 - 암기왕https://www.acmicpc.net/problem/2776문제연종이 하루 동안 본 정수들을 수첩1에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종이에게 M개의 질문을 던졌다. 연종이가 봤다고 주장하는 수들을 수첩2에 적어 놓았다.=> 수첩2에 적혀있는 순서대로, 각각의 수에 대하여 수첩1에 있으면 1/ 없으면 0 출력입력첫째 줄: 테스트케이스 개수 T 수첩 1에 적어 놓은 정수의 개수 N (1 수첩 1에 적혀 있는 정수들이 입력으로 들어옴수첩 2에 적어 놓은 정수의 개수 M (1 수첩 2에 적어 있는 정수들이 입력으로 들어옴출력수첩 2에 적혀있는 M개의 숫자 순서대로 수첩 1에 있으면 1/ 없으면 0 출력풀이이진 탐색(BinarySearch)리스..

2293 - 동전 1https://www.acmicpc.net/problem/2293문제n가지 종류의 동전/ 각각의 동전이 나타내는 가치는 다름동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶음각각의 동전은 몇 개라도 사용할 수 있음사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우입력첫째 줄: n (1 n개의 줄에는 각각의 동전의 가치가 주어짐 (자연수) (출력: 경우의 수 (풀이이전 결과 이용해서 다음 결과 구해야 함=> 작은 문제의 해를 저장하면서 큰 문제 해결: DP `dp[i]`: i원을 만드는 경우의 수`dp[0] = 1`: 0원을 만드는 경우는 아무 동전도 사용 X => 1가지`dp[j] += dp[j - i]`: 현재 금액 j를 만드는 방법은, j - i원 만든 다음..

2606 - 바이러스https://www.acmicpc.net/problem/2606문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파됨한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 됨ex. 7대의 컴퓨터가 네트워크 상에 연결1번 컴퓨터가 웜 바이러스 걸림 -> 2, 5번 거쳐 3, 6번까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸림But, 4번과 7번 컴퓨터: 1번 컴퓨터와 네트워크상에 연결 X -> 영향 X입력첫째 줄: 컴퓨터의 수 (양의 정수) 둘째 줄: 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어짐그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터 번호 쌍이 주어짐출력1번..

1197 - 최소 스패닝 트리https://www.acmicpc.net/problem/1197문제최소 스패닝 트리: 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리입력첫째 줄: 정점의 개수 V (1 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, CA번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않음그래프의 정점은 1~V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있음(-2,147,483,648 출력최소 스패닝 트리의 가중치 풀이MST(Minimum Spanning Tree): 최소 스패닝 트리모든 정점을 연결하면서 사이클 없이 간선 가중치 합이 최..

1260 - DFS와 BFShttps://www.acmicpc.net/problem/1260문제방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문, 더 이상 방문할 수 있는 점 X -> 종료정점 번호: 1 ~ N번입력첫째 줄에 정점의 개수 N (1 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호 주어짐어떤 두 정점 사이에 여러 개의 간선이 있을 수 있음/ 입력으로 주어지는 간선은 양방향출력: V부터 방문된 점을 순서대로 출력DFSBFS풀이DFS깊게, 한 방향으로 끝까지 파고들다가 돌아옴/ 재귀static void dfs(int node) { System.out.print(node + " "); visited[node] = true; for (int next :..

11404 - 플로이드https://www.acmicpc.net/problem/11404문제모든 도시 쌍 (a, b)에 대해 도시 a에서 b로 가는데 필요한 비용의 최솟값입력첫째 줄: 도시의 개수 n (2 둘째 줄: 버스의 개수 m (1 셋째 줄 ~ m+2줄: 버스의 정보버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c시작 도시와 도착 도시가 같은 경우 X, 비용 (자연수) 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음출력n개의 줄 출력i번째 줄에 출력하는 j번째 숫자: 도시i에서 j로 가는데 필요한 최소 비용만약, i에서 j로 갈 수 없는 경우 0 출력풀이플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)모든 도시 쌍 (i, j) 간의 최소 이동 비..