알고리즘

문제https://www.acmicpc.net/problem/2211 풀이1. 1번 컴퓨터에서 각각의 컴퓨터까지 다익스트라를 이용해 최단 경로 구하기-> 이 부분에서 처음에 문제를 읽고 '경루의 개수가 최소여야한다'는 말 때문에 헷갈렸으나, 원래 연결된 경로에서의 최소 시간 보다 크면 안된다는 말, 즉 최소 cost를 그대로 유지해야 한다는 말이 추가로 있기 때문에, 다익스트라로 최소 비용이 드는 루트들만 남기면 되는거였다.2. 이때 1번 컴퓨터에서 각 노드까지의 루트를 저장해둔다.-> 2차원 배열 route를 사용하여  저장해줬다.3. 2에서 저장해둔 루트를 중복 없이 출력한다.-> route 배열을 2중 for문으로 돌며 중복을 없애기 위해 pair자료형의 set인 finalRoute에 넣어줬다. 코..

문제https://www.acmicpc.net/problem/14938 풀이1. 하나의 정점을 출발지로 두고 다익스트라 알고리즘으로 모든 정점까지의 최단 거리 값을 구한다.(cost가 모두 양수이고 각 정점까지의 최단거리를 구하면 되므로 다익스트라 사용)2. 최단거리가 예은이의 수색 범위 이하에 있는 모든 정점의 item값의 합을 구한다.3. 출발지를 1~n까지 모두 설정하여 2를 구하고 최대값을 출력한다. 코드#include#include #include #define INF 1e9using namespace std;int n, range, r, answer = 0;vector> graph[101];int item[101];// 출발점이 departure일 때 조건을 만족하는 item값의 합을 출력in..

문제 https://www.acmicpc.net/problem/11779   풀이cost가 모두 양수이며, A에서 B 정점으로 가는 최소비용을 구하는 문제이므로 다익스트라 알고리즘으로 풀었다.다른 다익스트라 문제와는 달리, 어떤 정점들을 거쳐 갔는지 루트를 출력해야 했다.  코드 1처음엔 priority queue의 top에 접근 할 때마다 출력해봤는데 당연히 틀렸음.  코드 2그래서 route를 2차원 벡터로 만들어route[n] = { n까지 가는데 거쳐간 정점들 } 이런식으로 저장했다.#include #include #include #define INF 1e9using namespace std;int n, m, departure, arrival;vector> graph[1001];int dist[1..

입력값 n 의 범위가 1

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp[idx] = n -> idx까지의 최대 연속합이 n이라는 의미이다. dp[제곱수]는 무조건 1이다. 따라서 처음엔 어떤 수던간에 dp[i] = dp[직전 제곱수] + dp[i-직전 제곱수] 즉 dp[i] = 1 + dp[i-직전 제곱수] 라는 공식을 세우고 풀었는데 틀렸다. 코드는 다음과 같았다. #include #include #include #..

문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에 문제를 보고 도통 어떻게 풀어야하는지 답이 안잡혔는데,, 질문 게시판을 잠깐 보고 아이디어를 얻어 바로 풀었다. 힌트는 다음과 같다. 뒤에 0이 붙는 개수를 구해야하는데, 0이 붙는다는 것은 10이 한번씩 곱해진다는 것이다. 10의 소인수는 2와 5인데, 보통 2는 5보다 소인수로 많이 가지므로, 곱해지는 5의 개수를 카운트하면 된다. #include #include #include #include #include #include #include #include #inc..

문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 제한 메모리가 의도적으로 낮게 설정 되어있다. 처음엔 아무생각 없이 평소 하던대로 벡터에 입력 받고, sort함수로 정렬 후 출력했다. 당연히 결과는 메모리 초과. #include #include #include #include #include #include #include #include using namespace std; int n; vector v; int main() { ios_base::sync_w..

문제 https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 #include #include #include #include #include #include #include #include #include #include using namespace std; int n, year, month, date; string name, youngest, oldest; vector nameVec; vector dateVec, monthVec; vector yearVec; //year, idx vector youngVec, oldVec,..