정리 이번 문제는 플로이드-와샬을 사용해서 풀었습니다. 전에 3문제 정도 플로이드-와샬과 관련된 문제를 전에 풀어봤었는데 그래서인지 다익스트라보다는 조금 더 친숙한 감이 있기도 했고, 경로표의 형태를 보니까 플로이드-와샬로 풀어도 무방할 것 같았습니다. 다른 건 괜찮았는데 마지막에 조금 헤맸던 부분이 1->2->5->6과 같이 2개 이상의 노드를 거쳐서 갔을 때 최단거리가 나오는 부분이었는데요. 처음에 짰던 코드로 돌렸을 때에는 2가 아닌 계속 5(도착 노드 바로 전 노드)가 나왔습니다. 어떤 식으로 접근을 해야 할지 감이 잡히지 않아서 이 부분 풀이를 참고했는데, road 배열(최단 경로를 가기 위해 처음 방문하는 노드를 담은 배열)의 경우 [i][k]를 구해주면 최단거리로 가기 위해서 제일 처음 방문..
전체 글
항공대 알고리즘 동아리 Koala 🥰
문제 링크 : https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 1753번처럼 한 노드에서 다른 노드들까지의 최단거리를 찾되, 모든 노드에 대해 이를 반복해 풀 수 있는 문제입니다. 다만 두 가지 함정이 숨어 있었는데요, 한번 천천히 알아보도록 하겠습니다. 이번 답안은 다익스트라 입문 문제인 1753번 코드를 많이 참고하면서 완성했는데요, 첫 번째 함정은 이번 문제는 그래프가 양방향 그래프가 된다는 것입니다. 1753번에서는 단순히 한 노드..
이번 문제는 올려주신 풀이를 거의 참고하여 풀었습니다. 다익스트라 관련 문제를 풀면서 적응할 필요가 있을 것 같네요. 다익스트라 개념을 이해하고, 코드로도 대충 어떤 식으로 짜야될지 구상은 됐는데 우선순위 큐를 어떤 식으로 활용해야 될지 몰랐습니다. 정리 처음에는 priority_queue에 3가지 데이터(x, y, 거리)를 pair로 담아주기만 하면 된다는 생각으로 거리를 마지막에 넣어주었는데 나중에 priority_queue의 사용 이유를 깨닫고, 순서를 바꾸어서 해결해주었습니다. 좌표와 좌표 사이 경사값의 최대를 구하면 되는 문제인데 익숙하지 않아서 그런지 계속 최단거리를 구하려고 했던 것 같습니다.(지금 생각해보면 왜 그랬는지 모르겠는데 다익스트라를 코드로 짜 본 적이 없어서 개념 자체를 적용해보..
일단 만들어놓은 반례 리스트입니다. -------- 5 5 9 4 4 4 4 9 4 9 4 4 9 4 9 4 4 9 4 9 4 4 4 4 9 4 답 1 -------- 3 3 4 1 9 1 8 9 9 9 답 6 --------- 3 3 4 1 9 7 8 8 9 9 답 3 ---------- 6 2 1 2 2 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 2 2 1 2 2 답 0 ----------- 5 4 5 8 7 2 8 6 2 10 9 3 4 15 6 20 4 9 4 3 2 3 2 3 5 1 답 2 ----------- 1 아무 숫자 답 0 ----------- 3 9 9 9 9 9 9 9 1 3 답 6 --------- 5 1 14 15 16 17 ..
힌트 1 더보기 세 가지 이상의 원소를 저장하는 자료구조는 c++에서 tuple이 있고, pair 형식으로도 구현 가능합니다. 힌트 2 더보기 입력 범위를 조심하세요! 풀이 더보기 모든 격자를 노드로 보고, 격자와 격자 사이의 경사를 에지로 봤을 때 하나의 그래프로 표현할 수 있습니다. (1, 1) -> (n, n) 으로 가는 최단 경로를 묻는 문제이므로 다익스트라로 해결 가능합니다. #include using namespace std; typedef long long ll; ll arr[1010][1010]; ll dist[1010][1010]; //dist[i][j] : (1, 1) -> (i, j) 최단 거리 int dy[] = {0, 0, 1, -1}; int dx[] = {1, -1, 0, 0}..
우선순위 큐 문제를 별로 안풀어봐서인지, 혼자서는 솔직히 이 문제가 우선순위 큐인지 알아차리지 못했을 것 같습니다... 가장 중요한 것은 적어도 배열의 맨 앞의 값 두개는 항상 가장 작은 값이여야 할 것이라고 생각했고, 우선순위 큐를 이용해서 풀어주었습니다. 파이썬으로 작성한 코드 우선순위 큐에 집어 넣고 매번 pop을 통해 2개의 값을 꺼낸뒤 합을 total에 더하고 다시 큐에 넣어줬습니다. 그렇게 반복할 때 마다 큐의 길이가 1씩 줄어들게 되는데 queue의 길이가 1이면 반복문을 탈출시켜줄 수도 있지만 매번 비교를 해야되므로 if를 쓰거나 while에 조건을 다는 대신 try와 except로 빈 큐에 pop을 하려 했을 때 나는 에러를 이용해서 탈출시켜 주었습니다. import sys import ..
숫자 카드 묶음의 개수 N 카드 묶음 각각의 크기가 N번 주어짐 묶음을 합칠 때는 a + b 만큼의 비교가 필요함 즉 a b c 가 있는 묶음에서는 ( a + b ) + ( ( a + b ) + c ) 번의 비교가 필요하다 그리디 알고리즘으로 heap 의 top, top + 1을 더한다. 이때 heap은 mean heap으로 구성돼 가장 작은 수가 top에 위치한다. 해당 차례의 최소 값 만을 더하고 다시 heap에 추가해서 반환한다. 처음 제출 시 n = 1일 경우의 예외처리를 진행하지 않아 시간 초과 문제가 발생했다 if(pq.size() == 1){ cout > n; for(int i=0; i> tmp; pq.push(tmp); } int sum = 0;..
문제 링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 함께 올려주신 파일 합치기 문제와 유사해 금방 해결할 수 있었습니다! 양옆의 두 원소를 합치기 때문에 N - 1번의 연산을 수행해야 하는데요, 따라서 마지막 끝의 두 원소를 합치는 경우가 아닌 이상 더했던 요소를 언젠간 추가로 더하게 되므로 제일 작은 값 둘을 합치는 연산을 반복해야 합니다. 이를 구현하는 데에 수만 개의 원소가 존재해도 원소를 추가하고 빼는 동작이 O..
지난번에 풀어본 적이 있었던 문제였는데 오랜만에 보니까 확실히 까먹게 되네요. 우선순위 큐를 사용해서 풀었습니다. 우선순위 큐를 선언할 때 greater를 같이 넣어줌으로서 내림차순 정렬(queue내부에서 내림차순, 따라서 순서대로 top을 출력보면 가장 마지막에 나온 숫자가 가장 크다)이 되게 해주었습니다. 은 greater를 사용하기 위해 선언해주었습니다. 입력을 받으면서 우선순위 큐에 바로바로 push를 합니다. while문에서 pq.size()가 1보다 클 때까지 반복을 해줍니다. 1보다 클 때까지로 조건을 정한 이유는 큐에서 두 개의 수를 뽑아 더한 뒤에 마지막에 push를 해주기 때문에 result에 최종 답이 담기게 되어도 pq에는 하나의 값이 더 남게됩니다. #include #include..
이번 문제는 투포인터를 개념을 적용해서 바로 풀 수 있었던 문제였던 것 같습니다. 에라토스테네스의 체를 통해서 MAXNUM까지의 소수를 구해주었습니다. 입력받은 n까지의 소수 개수 세고, 소수를 배열에 담아주었습니다. 투포인터 코드를 적용하여 마지막에 경우의 수를 출력해주었습니다. 소스코드 #include #define MAXNUM 4000000 using namespace std; bool check[MAXNUM]; int arr[MAXNUM]; int main(void) { int n; for (int i = 2; i n; int num=0; int idx=0; for (int i = 2; i = n) sum -= arr[lo++]; else if (hi == num) break; else sum +..
참고자료와 강의를 들으니 바로 풀리는 문제였다. 에라토스테네스의 체로 소수를 모두 구한 뒤 two pointer를 사용해 구하면 되는 문제였다. MAX 값을 4000000으로 고정 시킨 후 4000000까지의 소수를 구한 후 해당 소수들을 vector에 저장시켰다. 그 후 vector안의 값의 합이 입력 값과 같은지 two pointer를 사용해 확인한다. #include #include #include #include using namespace std; const int MAX = 4000000; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); vector prime; bool isPrime[MAX+1]; fill(isPrime+2, isPrime+..
문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이가 매우 직관적이어서 개인적으로 좋다고 생각했던 문제입니다. 코알라 투 포인터 강의영상 에서 나온 2003번 문제에 에라토스테네스의 체를 덧댄 버전입니다. 해결 방법은 정말 깔끔합니다. 1부터 N 사이에 있는 소수들의 배열(리스트)을 미리 만들어 두고, 해당 테이블에 대해 투 포인터 방법을 사용해 인덱스를 움직여가며 부분합이 N이 되는지 검사하기만 하면 됩니다. 저의 경우에는 소수들의 배열을 그냥 문제에서 주어진 범위인 4백만개로 초기화했지만, 그래도 시간 복잡도는 체를 만들 때 O(NlogN) +..