Coding Test

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) 간의 최소 이동 비..

1744 - 수 묶기https://www.acmicpc.net/problem/1744문제길이가 N인 수열 -> 수열의 두 수를 묶어서 그 수열의 합어떤 수를 묶으려고 할 때, 위치에 상관 X 묶을 수 있음 But, 같은 위치에 있는 수(자기자신)를 묶는 것을 불가능어떤 수를 묶게 되면, 서로 곱한 후에 더함ex. {0, 1, 2, 4, 3, 5} -> 합: 0+1+2+4+3+5 = 15But, 2와 3, 4와 5 묶으면 -> 0+1+(2*3)+(4*5) = 27 최대수열의 모든 수는 단 한번만 묶거나 아니면 묶지 않아야 함=> 수열이 주어졌을 때, 각 수를 적절히 묶었을 때 최대합?입력첫째 줄: 수열의 크기 N (N (자연수) 둘째 줄부터 N개의 줄: 수열의 각 수가 주어짐 (-1,000 출력: 합이 최..

백준 11501 - 주식https://www.acmicpc.net/problem/11501문제3가지 중 한 행동을 함1. 주식을 산다2. 원하는 만큼 가지고 있는 주식을 판다3. 아무 것도 안한다=> 날 별로 주식의 가격을 알려줬을 대, 최대 이익이 얼마나 되는지?ex. 날 수: 3일/ 날 별로 주가: 10, 7, 6 -> 주가가 계속 감소 => 최대 이익: 0주가: 3, 5, 9 -> 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익: 10입력첫 줄: 테스트케이스 수 T각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 N (2 둘째 줄: 날 별 주가를 나타내는 N개의 자연수들 (공백, 날 별 주가 출력각 테스트케이스 별로 최대 이익을 나타내는 정수 출력부호 있는 64-bit 정수형으로..