나그네

2211번: 네트워크 복구 문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 1번 정점의 슈퍼컴퓨터에서 모든 정점에 이어야 하므로 최소 시간에 연결이 돼야 하므로 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 문제에서 요구하는 것은 이어야 하는 간선의 수와 그 간선이다. 따라서 -1로 초기화되어 있는 prev 배열을 만..

10282번: 해킹 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 의존성이 있는 컴퓨터에 바이러스가 전염되는 시간과 몇 대의 컴퓨터가 감염되었는지 구하는 문제다. 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] !! 신경 쓸 점이 두 가지 있다. 1. 테스트 케이스가 여러 개이므로 배열과 변수 초기화에 신경 써야 한다. 2. a가 b에 의존하고 있..

5972번: 택배 배송 문제 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 양방향 그래프에서의 다익스트라 알고리즘을 사용하면 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int N, M; vector graph[50001]; vector dist(50001, INF), visit..

1427번: 소트인사이드 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 숫자의 각 자리 수를 내림차순으로 정렬하는 문제다. 숫자를 string 타입으로 입력받고 내림차순으로 정렬해주면 된다. 내림차순 정렬은 비교 연산자 위치에 greater()을 넣어주면 된다. 코드 #include using namespace std; int main() { string a; cin >> a; sort(a.begin(), a.end(), greater()); cout

1422번: 숫자의 신 문제 https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 풀이 K개의 수를 N번 사용해 가장 큰 수를 만드는 문제다. 단, 모든 수는 한 번은 이용해야 한다. 1. K개의 수 정렬 연결했을 때 가장 큰 수를 만들기 위해서 말 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경..

16496번: 큰 수 만들기 문제 https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 풀이 N개의 수를 이어붙여 가장 큰 수를 만들기 위해서 문자 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경우엔 110이 더 크기 때문에 위치가 바뀌지 않는다. 출력 조건이 하나 더 있는데 만약 답이..

1330번: 두 수 비교하기 문제 https://www.acmicpc.net/problem/1330 1330번: 두 수 비교하기 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. www.acmicpc.net 풀이 두 수 a, b를 입력받고 a가 크면 >를, b가 크면 > a >> b; if (a > b) { cout

1316번: 그룹 단어 체커 문제 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 풀이 문자열 내에서 같은 문자는 연속해서만 나타나면 그룹 단어다. 따라서 i번째 문자와 i+1번째 문자가 다른 경우에만 이후에 i번째 문자와 같은 문자가 있는지 확인해주면 된다. 코드 #include using namespace std; int main() { int n, ans = 0; cin >> n; for (int i = 0..

1292번: 쉽게 푸는 문제 문제 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 풀이 1 2 2 3 3 3 4 4 4 4 5 와 같이 1을 1번 2를 2번 3을 3번인 수열에서 a번째부터 b번째 수의 합을 구하는 문제다. cnt 변수를 하나 만들어주고 cnt 만큼 cnt를 배열에 추가하도록 했다. 배열 크기가 b를 넘지 않도록 하여 제한을 뒀다. 이후엔 합을 더하면 끝인 간단한 문제다. 코드 #include using namespace std; int main() ..

1202번: 보석 도둑 문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 보석의 무게와 가격이 주어지고 가방에 담을 수 있는 최대 무게가 주어진다. 가방은 최대 1개의 보석만 담을 수 있다. 훔칠 수 있는 보석의 가격의 최댓값을 구하는 문제. 먼저 기본적인 틀은 최대 무게가 가방에 담을 수 있는 보석 중에 가격이 가장 큰 보석을 담는 것이다. 당연히 담을 수 있는 무게가 큰 ..