Programming456 [C/C++] 백준 #2410 2의 멱수의 합(동적 계획법) #2410 문제는 점화식을 잘 세우면 동적 계획법을 이용해서 풀 수 있습니다. 하지만 늘 그렇듯이 점화식을 만드는 과정이 쉽지만은 않습니다. https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떤 수가 주어지면, 그 수를 2의 멱승(1, 2, 4, 8, ...과 같이 \(2^k\)으로 표현되는 수)의 합으로 표시하는 경우의 수를 구하는 것입니다. 2의 멱승을 하니 조금 이상할 수 있지만, 이진수 표현법이 기초가 됩니다. 홀수가 주어졌다고 하죠. 예를 들면 9가 주어졌습니다. 8 + 1 4 + 4 + 1 4 + 2 + 2 +.. 2023. 4. 29. [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. 이전 1 ··· 13 14 15 16 17 18 19 ··· 76 다음
