[백준 알고리즘]/[C++]
-
백준 2252 줄 세우기 | 위상정렬 | C++[백준 알고리즘]/[C++] 2021. 4. 12. 10:34
이번 포스팅은 백준 2252번 줄 세우기입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 기본 알고리즘 위상정렬 Topological Sort 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41..
-
백준 1613 역사 | 플로이드-워셜 | C++[백준 알고리즘]/[C++] 2021. 4. 9. 10:01
이번 포스팅은 백준 1613번 입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 기본 알고리즘 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 풀이 line 45-53 if (map[event1][event2] == INF && map[event2][event1] == INF) //event1→event2 경로 존재하지 않음 && event2→event1 경로 존..
-
백준 10159 저울 | 플로이드-워셜 | C++[백준 알고리즘]/[C++] 2021. 4. 8. 09:20
이번 포스팅은 백준 10159번 저울입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 기본 알고리즘 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 풀이 line 40-48 int cnt //정점i와 연결되어 있는 정점의 개수 if (map[i][j] != INF || map[j][i] != INF) //i보다 무거운 물건 존재 또는 i보..
-
백준 2458 키 순서 | 플로이드-워셜 | C++[백준 알고리즘]/[C++] 2021. 4. 8. 00:54
이번 포스팅은 백준 2458번 키 순서입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 기본 알고리즘 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 풀이 line 39-49 int ans //출력(정답) int cnt //정점i와 연결되어 있는 정점의 개수 if (map[i][j] != INF || map[j][i] != INF) //i보다 큰 사람이 존재 또는 ..
-
백준 15654 N과 M (5) | 조합 | C++[백준 알고리즘]/[C++] 2021. 4. 6. 14:01
이번 포스팅은 백준 15654번 N과 M (5)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 기본 알고리즘 조합을 재귀함수로 구현 15650번과 정렬이 되어있지 않은 입력 값들이 들어온다는 점만 제외하면 동일한 문제 15650번 풀이 참고 - scarlettb.tistory.com/125 백준 15650 N과 M (2) | 조합 | C++ 이번 포스팅은 백준 15650번 N..
-
백준 11404 플로이드 | C++[백준 알고리즘]/[C++] 2021. 4. 6. 13:53
이번 포스팅은 백준 11404번 플로이드입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 기본 알고리즘 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 풀이 ★시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 최소 비용을 계산하므로 입력 값이 중복되어 들어올 경우 더 작은 비용의 값으로 갱신한다. ★i에서 j로 갈 수 없는 경우에는 그 자리에 0을 ..
-
백준 9663 N-Queen | 백트래킹, DFS | C++[백준 알고리즘]/[C++] 2021. 4. 1. 14:06
이번 포스팅은 백준 9663번 N-Queen입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 기본 알고리즘 DFS, 백트래킹 풀이는 주석에 담았습니다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..
-
백준 15652 N과 M (4) | 중복조합 | C++[백준 알고리즘]/[C++] 2021. 3. 30. 11:50
이번 포스팅은 백준 15652번 N과 M (4)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 기본 알고리즘 재귀함수로 구현한 중복조합 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 //백준15652 N과 M (4) #include ..