반응형 Programming401 [Python] 백준 #2407 조합(수학) 이번 문제는 \(_nC_r\) 조합을 구하라는 것입니다. 조합을 구하는 알고리즘은 수학을 알고 있다면 손쉽게 할 수 있습니다. 단지 문제는 숫자가 커지기 때문에 BigInteger 자료형을 제공하는 파이썬이나 자바를 이용하시는 것이 편합니다. https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 저는 파이썬을 이용했습니다. \[ _nC_r = \frac{n!}{(n-r)! r!} \] 이것을 그대로 구현하였습니다. 제가 작성한 소스입니다. """ // baekjoon #2407 // - by Aubrey Choi // - created at 2019-06-27 "".. 2023. 4. 29. [C/C++] 백준 #2367 파티(포드-폴커슨 알고리즘) 이번 문제는 파티에서 음식을 준비할 때, 음식의 종류와 할 수 있는 음식 종류, 그리고 가져올 수 있는 음식의 개수가 제한되어 있을 때, 최대한의 음식을 준비하는 것을 목표로 하는 내용입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2367 2367번: 파티 첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개 www.acmicpc.net 이 문제를 풀기 위해서는 최대 유량 알고리즘을 알아야 합니다. 최대 유량은 제한 조건이 있을 때, 그 조건을 지키는 한도 내에서 최대의 결과를 얻을 때 사용됩니다. 최대유량과 관련되어.. 2023. 4. 28. [C/C++] 백준 #2357 최솟값과 최댓값(세그먼트 트리) 세그먼트 트리를 구현해서 푸는 문제가 참 많습니다. 옛날에는 세그먼트 트리가 Platinum 등급에 있었는데, 이제는 모두 Gold 등급으로 떨어졌습니다. https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최소값과 최대값을 주어진 범위안에서 찾는 알고리즘은 모두 \(O(N)\) 입니다. 미리 테이블을 만들어서 하는 것도 어렵죠. 세그먼트 트리만이 올바른 방법이라고 볼 수는 없습니다. 데이터를 \(\sqrt{N.. 2023. 4. 27. [C/C++] 백준 #2352 반도체 설계(가장 긴 증가하는 부분수열) 가장 긴 증가하는 부분수열 문제는 백준 사이트에서 자주 접할 수 있는 문제입니다. 이 알고리즘을 잘 이해하면, 풀 수 있는 문제들이 많이 있습니다. 증가하는 부분수열 중 하나를 출력하라면 조금 골치가 아프겠지만, 현재 이 알고리즘을 이용해서 부분수열도 출력할 수 있습니다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 반도체에서 서로 라인이 겹치지 않도록 설계하는 것은 중요한 문제입니다. 실제로는 다층기판을 이용하기 때문에.. 2023. 4. 27. [C/C++] 백준 #2346 풍선 터뜨리기(데크 자료구조) #2346 풍선 터뜨리기 문제는 자료구조를 사용하면 좋습니다. 제 경우에는 데크 자료구조를 이용하여 문제를 풀었습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 데크 자료구조는, 큐와 스택 모두 사용하여도 성능이 좋습니다. 그래서 큐 대신에 많이 사용되는 편입니다. 구현은 데크를 이용하여 적절한 삭제만 해주시면 됩니다. 데크 자체가 앞과 뒤 연산에는 효율적이지만, 중간에 데이터를 넣는 작업이나 빼는 .. 2023. 4. 27. [C/C++] 백준 #2331 반복수열(구현) #2331 반복수열 문제는 단순하게 구현만하면 됩니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 이 문제에서 구현의 초점은 바로 자리수를 가져오는 것과 그것을 p제곱하는 것입니다. A란 숫자가 있으면, p값이 바뀌지 않는다면, 모든 자릿수를 p제곱한 후의 합은 항상 같은 숫자가 됩니다. 저는 개수를 세기 위해서 배열에 count를 하게 했습니다. 배열의 최대 개수는 9의 5제곱은 59049이므로 이것을 4개 더한 236196보다 크게 잡아주면 됩니다. 제가 구현한 소스입니다. //---------------------------.. 2023. 4. 26. 이전 1 ··· 4 5 6 7 8 9 10 ··· 67 다음 728x90
