![]()
문제&링크https://www.acmicpc.net/problem/1238 풀이1. 각자 마을 별로 특정 마을까지 갔다가 오는 최소 거리를 계산해야 하기에, 다익스트라 알고리즘을 사용한다.2. 시작점과 끝점 가중치가 주어져 있기에 끝점과 가중치를 pair로 하는 벡터 행렬에 시작점을 기준으로 저장한다.3. 다익스트라 함수에서 시작점과 끝점을 파라미터로 받는다.4. fill 함수를 이용해서 모든 거리를 INF로 초기화한다.5. 우선순위 큐를 활용하여 가중치가 가장 낮은 값 먼저 탐색하도록 한다. 이때 우선순위 큐는 기본적으로 max heap 이기에 가중치를 음수로 하여 저장하고, 값을 사용할 때는 -를 붙여 양수로 사용한다.6. 시작점 s의 가중치를 0으로 초기화한 후 우선순위 큐에 삽입하고, 거리 또한 ..
문제https://www.acmicpc.net/problem/17413코드#include #include #include #includeusing namespace std;int main(){ string s; getline(cin, s); int intag = 0; string ans = ""; string word = ""; for (int i = 0; i ') { ans += s[i]; intag = 0; } //숫자나 알파벳 else { if (intag == 1) { ans += s[i]; } else { word = s[i] + word; } } } ans += word; cout 알고리즘 분류 : 구현문제 해설 : 태그 안일 때는 체크해주면서 문..
https://www.acmicpc.net/problem/1940 문제재료의 수 N(1 풀이고유한 수를 정렬한 후, 이중 반복문으로 두 수를 더해서 m이 되는 경우의 수를 센다. 이때, 안쪽 루프가 i+1부터 시작하므로, n*2보다는 적은 연산을 한다.#include #include using namespace std;int n, m, arr[15010], cnt = 0;int main() { cin >> n >> m; for (int i = 0; i > arr[i]; sort(arr, arr + n); for (int i = 0; i
![]()
https://www.acmicpc.net/problem/1854문제봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.입력첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1,000, 0 ≤ m ≤ 250,000, 1 ≤ k ≤ 100, mk ≤ 3,000,000) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에는 각각 도로의 정보를..
![]()
5972번: 택배 배송 (acmicpc.net)노드와 비용을 입력받고 최소 비용이 되는 길로 가야겠다import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)import heapqn,m=map(int,input().split()) graph=[[] for _ in range(n+1)]for _ in range(m): a,b,c=map(int,input().split()) graph[a].append((b,c)) graph[b].append((a,c))INF=int(1e9)dist=[INF]*(n+1) def dijkstra(start): visit=[] q=[] heapq.heappush(q,(0, start)) ..
![]()
풀이#include #include #include #include using namespace std;int N, M;int dist[1001];vector> v[1001];int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; while(M--) { int s, e, c; cin >> s >> e >> c; v[s].push_back({e, c}); } int start, end; cin >> start >> end; memset(dist, 127, sizeof(dist)); dist[start] = ..
https://www.acmicpc.net/problem/13549문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 소스코드i..
![]()
문제&링크https://www.acmicpc.net/problem/2589 풀이1. 가장 먼 두 점 사이의 거리를 구하는 문제임으로 시간 초과를 고려하여 BFS로 문제를 해결한다.2. 육지("L")로 이루어진 그래프가 여러 개 있을 수 있으므로, 모든 점을 기준으로 BFS를 구하고 거리의 최댓값을 구한다.-> 시간복잡도를 줄이기 위해서 각 그래프 별로 한 점을 잡고 두 번의 BFS를 사용하여 그래프 내의 거리의 최댓값을 구할 수 있다. (트리의 지름 활용) 3. 각 점별로 BFS를 실행할 때마다 cstring 헤더 파일의 memset 함수를 이용해서 거리(dist) 및 방문 여부(check) 배열을 초기화한다.4. BFS 함수를 통해 얻은 거리의 최댓값을 반환하도록 하여 다른 BFS 함수를 통해 얻은 거..
![]()
문제&링크https://www.acmicpc.net/problem/11279 풀이1. 우선순위 큐를 이용하여 최대 힙을 만든다.2. 0을 입력받은 순간 최대 힙이 비어있다면 0을 출력한다.3. 0을 입력받은 순간 최대 힙이 비어있지 않다면 제일 큰 값, 즉 우선 순위 큐의 top에 해당하는 값을 출력한다.4. 0이 아닌 다른 수를 입력받을 경우 최대 힙에 저장한다. 코드#include #include using namespace std;priority_queue pq;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = ..
![]()
https://www.acmicpc.net/problem/13549Algorithm점의 위치는 0~ 100000내에 존재하므로, 그래프를 생각했을 때 1~50000까지의 그래프 배열에는 2배를 한 위치로 이동할때 cost가 없고, 0~100000까지는 +1, -1칸 까지 이동할때는 cost가 1이 발생하도록 설정하여 다익스트라를 쓰면 된다고 생각했다. 위 사진처럼 그래프를 구성하였고, 시작점을 수빈이가 있는 위치로해서 distance배열계산을 하고, 동생의 위치를 출력해주면 된다.Codeimport sysimport heapqinput = sys.stdin.readlinesys.setrecursionlimit(10**6)BOUND = 100000n,k = map(int,input().split())INF..
https://www.acmicpc.net/problem/27964 문제토핑의 개수가 1이상 100 이하의 정수로 주어지고, 토핑의 목록이 문자열로 주어질 때, Cheese로 끝나는 토핑이 4종류 이상이면 yummy, 그렇지 않으면 sad를 출력한다. 풀이set을 사용해서 같은 종류의 토핑을 거르고, Cheese로 끝나는 문자열이 몇 개인지 확인한다.#include #include using namespace std;int n, cnt=0;string s, Cheese="Cheese";set st;int main(){ cin >> n; for (int i = 0; i> s; st.insert(s); } for (auto iter=st.begin(); iter!=st.en..
https://www.acmicpc.net/problem/4963문제정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력/출력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개..
