알고리즘 문제풀이/백준
-
[백준/BOJ] 1238번 파티 (C++)알고리즘 문제풀이/백준 2020. 12. 30. 11:45
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 이용하면 해결할 수 있는 문제 (다시 풀기) 새롭게 알게된 점 pair형에서 sort함수를 쓰면 first를 기준으로 적용된다. (default) 다익스트라를 이용해 1번부터 n번 정점까지 target으로 갈 수 있는 최소 비용을 dist배열에 갱신한 후, res배열에 복사합니다. dist배열을 초기화하고, 이번에는 target에서 1번부터 n번 정점까지 갈 ..
-
[백준/BOJ] 1929번 소수 구하기 (C++)알고리즘 문제풀이/백준 2020. 12. 29. 21:30
www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 입력값이 최대 1,000,000 이므로 단순 소수를 찾는 방법은 시간 초과가 발생합니다. 따라서 에라토스테네스의 체라는 방법을 이용해서 해결해야합니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int m, n; cin>>m>>n; vector v(n + 1); for(int i = 2; i
-
[백준/BOJ] 1260번 DFS와 BFS (C++)알고리즘 문제풀이/백준 2020. 12. 29. 21:20
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그래프에서의 DFS와 BFS를 연습할 수 있는 좋은 문제입니다. 인접 행렬 혹은 인접 리스트를 이용해서 그래프를 만들 수 있는데, 저는 인접 리스트를 이용했습니다. ※ 인접 행렬과 인접 리스트의 차이점이 궁금했었는데 잘 설명한 블로그 글이 있어 주소를 남겨봅니다! seohyun0120.tistory.com/entry/C-BFS%EC%99%80-DFS-%EC%9D%B8%EC%..
-
[백준/BOJ] 9095번 1, 2, 3 더하기 (C++)알고리즘 문제풀이/백준 2020. 12. 28. 17:08
www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 브루트 포스(완전 탐색) 또는 DP 둘다 이용해서 풀 수 있는 문제 브루트 포스로 해결할 경우 DFS를 통해 1, 2, 3을 이용하여 n을 나타내는 모든 경우의 수를 구하면 됩니다. DP를 통해 해결할 경우 다음과 같은 규칙을 찾아내면 됩니다. 1을 표현할 수 있는 경우 : 1 -> 1가지 2를 표현할 수 있는 경우 : 1+1, 2 -> 2가지 3을 표현할 수 있는 경우 : 1+1+1, 1+2, 2+1, 3 -> 4가지 따라서 다음과 같은 점화식을 도출해낼 수 있습니다 dp[n] = dp[n - 2] + dp..
-
[백준/BOJ] 1182번 부분수열의 합 (C++)알고리즘 문제풀이/백준 2020. 12. 28. 16:51
www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제 현재 누적합과 현재 인덱스 값을 더한게 s와 같은지 확인해서 같으면 answer를 증가시키고, 그게 아니라면 현재 인덱스 값을 더하거나, 더하지 않고 그대로 재귀함수를 호출합니다. 이때 sum + v[idx]의 값과 s의 비교를 기저조건에서 하지 않는 이유는 입력값의 조건이 음수가 포함이므로 이를 기저조건에 두면 답인 경우가 더해지지 않는..
-
[백준/BOJ] 6603번 로또 (C++)알고리즘 문제풀이/백준 2020. 12. 28. 16:20
www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제입니다. k개의 수에서 6개를 뽑는 조합을 DFS를 이용해 구현하였습니다. #include #include #include using namespace std; int res[6]; void DFS(int idx, int cnt, vector v) { if(cnt == 6) { for(int i = 0; i < 6; i++) { cout
-
[백준/BOJ] 11508번 2+1 세일 (C++)알고리즘 문제풀이/백준 2020. 12. 27. 02:11
www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 쉬운 그리디 문제입니다. 가격을 기준으로 내림차순 정렬을 한 후, 3개씩 묶을 때 마지막 가격만 빼면 되므로, 현재 인덱스 번호 % 3 의 값이 2가 아닌 경우는 모두 더해주면 됩니다. #include #include #include using namespace std; int cmp(long long a, long long b) { // 내림차순 정렬 return a > b; } int main(v..
-
[백준/BOJ] 14247번 나무 자르기 (C++)알고리즘 문제풀이/백준 2020. 12. 26. 19:52
www.acmicpc.net/problem/14247 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 그리디 유형 문제입니다. 나무가 자라는 가중치 값을 기준으로 오름차순 정렬을 한 후, 가중치가 작은 값부터 나무를 자르면 해결할 수 있는 문제입니다. #include #include #include using namespace std; int cmp(pair a, pair b) { return a.second < b.second; // 가중치 값을 기준으로 오름차순 } int main(void) { ios_ba..