[백준 알고리즘]/[C++]
-
백준 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) #..
-
백준 1766 문제집 | C++[백준 알고리즘]/[C++] 2021. 3. 29. 13:50
이번 포스팅은 백준 1766번 문제집입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 기본 알고리즘 위상정렬 Topological Sort 우선순위 큐 Priority Queue 풀이 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. line 14 priority_queue pq; 오름차순 정렬..
-
백준 1005 ACM Craft | C++[백준 알고리즘]/[C++] 2021. 3. 29. 13:44
이번 포스팅은 백준 1005번 ACM Craft입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 기본 알고리즘 위상 정렬 Topological Sort 풀이 최소 시간을 갱신하는 조건 line49 result[next] = max(result[next], result[cur] + time[next]); 정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을..
-
백준 2056 작업 | C++[백준 알고리즘]/[C++] 2021. 3. 29. 13:39
이번 포스팅은 백준 2056번 작업입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 기본 알고리즘 위상 정렬 Topological Sort 풀이 최소 시간을 갱신하는 조건 line42 result[next] = max(result[next], result[cur] + time[next]); 정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 짓는 시..
-
백준 1516 게임 개발 | C++[백준 알고리즘]/[C++] 2021. 3. 26. 12:51
이번 포스팅은 백준 1516번 게임 개발입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 기본 알고리즘 위상 정렬 Topological Sort 풀이 최소 시간을 갱신하는 조건 line56 result[next] = max(result[next], result[cur] + time[next]); 정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 ..
-
백준 2437 저울 | C++[백준 알고리즘]/[C++] 2021. 3. 25. 10:50
이번 포스팅은 백준 2437번 저울입니다. 아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다. www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 기본 알고리즘 그리디 알고리즘 셸 정렬 사용함 벡터와 sort 함수를 사용하면 코드의 길이와 실행 시간을 단축할 수 있다. 풀이 자연수 배열에서 배열 원소에 1이 존재하고, 배열의 (i-1)번째 원소까지의 누적합 sum에 대해 arr[i] > N; for (int i = 0; i > list[i]; } /*셸 정렬..