[백준 알고리즘]
-
백준 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 ..
-
백준 15651 N과 M (3) | 중복순열 | C++[백준 알고리즘]/[C++] 2021. 3. 30. 11:24
이번 포스팅은 백준 15651번 N과 M (3)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 기본 알고리즘 재귀함수를 이용해 구현한 중복순열 전체 코드 방법1 - 순열 코드에서 bool selected[] 코드 부분 제거 순열 코드 참고(scarlettb.tistory.com/126) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..
-
백준 15649 N과 M (1) | 순열 | C++[백준 알고리즘]/[C++] 2021. 3. 30. 11:06
이번 포스팅은 백준 15649번 N과 M(2)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 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 39 40 41 42 43 44 //백준15649 N과M..
-
백준 15650 N과 M (2) | 조합 | C++[백준 알고리즘]/[C++] 2021. 3. 30. 10:53
이번 포스팅은 백준 15650번 N과 M (2)입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 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 39 40 41 42 //백준15650 N과M(2) #..