목록전체 글 (540)
알고리즘 모음(C++)
문제 링크입니다. https://www.acmicpc.net/problem/13905 13905번: 세부첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄www.acmicpc.net최소 스패닝 트리와 DFS를 이용해 풀었습니다.숭이의 출발위치에서 혜빈이의 위치까지 이동할 때, 숭이가 들고 갈 수 있는 최대 금빼빼로의 개수를 구하는 문제입니다. 들고 갈 수 있는 금빼빼로는 다리를 이동할 때, 해당 다리의 비용만큼만 들고 갈 수 있습니다. 따라서, 집들을 연결할 때, 비용이 작은 것들이 아닌 큰 비용을 가진 다리들로 연결해야..
문제 링크입니다. https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net다익스트라와 DFS를 이용한 문제입니다.주어진 교역로를 통해 마을들끼리 서로 연결될 수 있는 최소 비용을 구하고, 해당 연결에서 가장 큰 경로의 비용을 구하는 문제입니다. 최소 비용으로 모든 마을이 연결될 수 있게 만드는 것은 최소 스패닝 트리를 통해 쉽게 구할 수 있습니다. 문제는 가장 큰 경로의 비용을 구하는 것인데, 간단하게 최소 스패닝 트리를 구하는 과정에서 가장 작은 비용..
문제 링크입니다. https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.N*N의 입력으로 정점끼리 연결된 정보가 주어질 때, 기부할 수 있는 최대 전선의 길이를 구하는 문제입니다. 최대 전선의 길이를 구하기 위해선, 컴퓨터들끼리 연결시킨 전선의 최소 길이를 구한 뒤, 전체 전선의 길이에서 빼주면 됩니다. 문제에서 모든 컴퓨터가 연결되어 있어야하며, 다른 컴퓨터들을 통해 연결될 수 있다면 서로 통신할 수 있다는 것..
문제 링크입니다. https://www.acmicpc.net/problem/1368 1368번: 물대기첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어www.acmicpc.net최소 스패닝 트리를 이용하는 문제였습니다.N개의 논에 물을 대려고 할 때의 최소 비용을 구하는 문제입니다. 논에 물을 대는 방법은 2가지가 있습니다. 1. 논에 우물을 파는 방법 2. 물이 있는 다른 논에서 자기 논으로 대는 방법 다른 최소 스패닝 트리 문제와 달리 다른 정점과의 간선 뿐만 아니라, 자기 자신의 값이 추가되었습니다. 하지만, 생각을 다르게..
문제 링크입니다. https://www.acmicpc.net/problem/21924 21924번: 도시 건설첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.모든 건물이 도로를 통해 연결되도록 할 때의 최솟값을 구하는 문제입니다. 다만, 모든 건물이 연결될 수가 없다면 -1을 출력해줘야 합니다. 모든 견물을 연결하는 방법은 최소 스패닝 트리를 통해 구해주면 됩니다. 문제는 전부 ..
문제 링크입니다. https://www.acmicpc.net/problem/12834 12834번: 주간 미팅첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000) 둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V) 셋째 줄에 팀원 N명의www.acmicpc.netN번의 다익스트라를 이용하는 문제입니다.팀원 N명의 집에서 각자 출발할 때, 모든 사람의 최단 거리의 합을 구하는 문제입니다. 최단 거리를 구하는 방법은 X번 사람의 집에서 KIST까지의 거리 + 씨알푸드까지의 거리 입니다. 만약, 거리가 갈 수 없다면 -1로 바꿔서 계산하면 됩니다. 문제를 푸는 방법은 간단하게 N번의 ..
불과 몇년 전만해도 플레티넘3은 커녕 플레티넘까지도 못가고 끝날 것이라고 생각했었을 때가 있었습니다. 꾸준히 하다보니 플레티넘5 를 올라갈 수 있었고, 어느샌가 플레티넘4 까지 왔었습니다. 이제 진짜 올라갈 때까지 올라갔구나, 내 실력에 비해서 더 높은 티어인것 같다고 생각했지만, 결국은 3까지 올라왔습니다. 지금은 이번 티어가 마지막을 것이라고 생각하지만, 나중에 보면 다를 수도 있을것 같다는 생각을 합니다. 알고리즘 분아에서 백준 상위 2%안에 든다고 적혀져있지만, 아직 그정도 실력은 아니고 많이 부족함을 느끼고 있습니다. 문제들을 풀면서 프로그레밍에 크게 재능은 없다고 생각하게 되고, 왜 이정도 밖에 못할까라는 생각을 가져본 적도 많습니다. 그렇지만, 지금까지 막히는 문제가 있으면 실마리가 잡힐 때..
문제 링크입니다. https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다맨위 첫 번째 줄에 T(1 n_cost){ parent[xx] = x; //자신과 연결된 부모 저장 Distance[xx] = n_cost; q.push({-Distance[xx], xx}); } } } } void solve(int num){ reset_array(); Dijstra(); if(Distance[M-1] != INF){ vector way; way.clear(); for(int i = M-1; i != 0; i = parent[i]){ // 저장된 부모들을 찾는다. way.push_back(i); } way.push_back(0); cout cost..
문제 링크입니다. https://www.acmicpc.net/problem/3036 3036번: 링출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.www.acmicpc.net유클리드 호제법을 이용한 문제입니다.첫번째 링의 길이를 기준으로 다른 링들과의 최대 공약수를 구해줍니다. -> 이때 유클리ㄷ, 호제법이 이용됩니다. 최대 공약수를 구해줬다면, 값을 바탕으로 링이 도는 횟수를 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include using namespace std; int N; int ring[101]; int Uc..
문제 링크입니다. https://www.acmicpc.net/problem/5063 5063번: TGN첫째 줄에 테스트 케이스의 개수 N이 주어진다. 다음 N개의 줄에는 3개의 정수 r, e, c가 주어진다. r은 광고를 하지 않았을 때 수익, e는 광고를 했을 때의 수익, c는 광고 비용이다. (-106 ≤ r,e ≤ 106www.acmicpc.net 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include using namespace std; int N; int main(){ cin.tie(0); cout.tie(0); cin >> N; for(int i = 1; i > x >> y >> cost; if(x < y - cost){ cout
문제 링크입니다. https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다.www.acmicpc.net간단한 조건문 문제입니다.문제에 주어진 조건에 따라 값을 저장한 뒤, 마지막에 비교해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include using namespace std; int N, Y, M; int main(){ cin.tie(0); cout.tie(0); cin >> N; for(int i = 1; i > x; Y +..
문제 링크입니다. https://www.acmicpc.net/problem/16118 16118번: 달빛 여우첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ bwww.acmicpc.net다익스트라를 사용하는 문제였습니다.달빛 여우와 늑대가 어느 정점을 갈 때의 최소 비용이 여우가 더 적은 정점의 개수를 찾는 문제입니다. 주의할 점은 여우는 주어진 비용으로만 가지만, 늑대는 (비용/2) -> (비용*2) -> (비용/2) ..... 의 방법으로 가게 됩니다. 그렇다면 다른 정점까지의 여우의 최솟값, 늑대의 최솟값..