integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 경우로 세는 방법, 다른 경우로 세는 방법)

1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 풀이 정수 n을 1,2,3만 사용해서 만드는 방법의 수를 구하는 문제 1) 여기서 1,2,3은 중복해서 사용 가능하다 2) 동일하게 사용해도 순서가 다르면 다르다고 취급한다. 즉 1+1+2와 1+2+1은 다른 경우이다. dp[n]을 n을 만드는 방법의 수로 정의하고, 일단 n이 11보다 작기 때문에 dp의 크기를 11까지 잡아준다. n을 만들려면 어떻게 해야할까? 1,2,3만 사용할 수 있기 때문에 3가지 경우가 가능하다. 1) n-1에서 1을 더하면 n n-1을 만드는 방법의 수 dp..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 7. 31.
• textsms

자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기

1. 문제 1947번: 선물 전달 (acmicpc.net) 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 풀이 PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가 뜨네 (mjstudio.net) PS를 위한 수학 - 교란 순열(완전순열) 교란 순열 ps.mjstudio.net 비가 오는 날에 n명의 사람이 자기의 우산을 쓰고 한 건물에 모여있다. 모두 동시에 집에 가려고 다시 우산을 쓰고 나가려는데, 자신의 우산을 사용하지 않는 경우의 수는? n개의 물건을 n명의 사람에게 다시 분배하는데, 자기 물건을 다시 갖지 않는 경우의 수를 교란순열(완전순열, derangement)라고 부른다 점화식이 유명한데 (고등..

• format_list_bulleted 조합론
• · 2023. 7. 18.
• textsms

정수론 - 방정식을 만족하는 순서쌍의 수 세기 - 브루트포스 탐색 범위 줄이는 테크닉 익히기

1. 문제 C - Four Variables (atcoder.jp) C - Four Variables AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이1 당연히 안될 것 같지만 방법을 모르겠다면 브루트포스로 접근하는게 기본이다 AB+CD = N을 만족하는 양의 정수쌍 A,B,C,D를 찾기 위해 1부터 N까지 순회해본다 이 값을 AB = x라 하고, 그렇다면 CD는 자동으로 N-x로 결정된다 그리고 AB = x에서 1부터 x까지 순회해서 그 수를 A라 하고, 만약 x가 A로 나누어 떨어진다면 B를 찾은 것이다. 마..

• format_list_bulleted Atcoder
• · 2023. 3. 11.
• textsms

1차원 convolution 연산을 효율적으로 하는 계산하는 방법은?

1. 문제 22964번: conv1d (acmicpc.net) 22964번: conv1d A = [1, 1], B = [1] : 1 1 A = [1, 1], B = [2] : 2 2 A = [1, 2], B = [1] : 1 2 A = [1, 2], B = [2] : 2 4 A = [2, 1], B = [1] : 2 1 A = [2, 1], B = [2] : 4 2 A = [2, 2], B = [1] : 2 2 A = [2, 2], B = [2] : 4 4 1+2+1+2+2+4+2+4 = 18 1+2+2+4+1+2+2+4 = 18 www.acmicpc.net 입력데이터와 필터가 주어질때, 1차원 convolution 연산을 수행하는 문제 2. 풀이 역시 만만한 문제가 아니다 단순히 곱하는거면 문제가 아닌..

• format_list_bulleted 구현,시뮬레이션
• · 2022. 12. 10.
• textsms

반복문에서 경우의 수를 나누는 방법

1. 문제 여러개의 음료수가 준비되어 있는데 각 음료수가 a개있고 1개당 b리터만큼 존재하고 1개당 c 칼로리의 열량을 가진다. 주어진 음료수에 대한 정보가 담겨있는 배열의 각 원소가 [a,b,c] 형태로 주어지고 p리터만큼 음료수를 마시고자 한다. 최대로 열량을 섭취하고자 할 때 최대 열량을 return하도록 함수를 완성한다면? 단, p리터 이전에 한번 마시기 시작한 음료수는 끝까지 다 마셔야한다고 가정한다. 그리고 한번에 a개의 음료수를 모두 마실 필요 없이 a개중 일부만 마시고 다른 음료수를 마신 다음에 못마신 음료수를 다시 마셔도 된다. 예를 들어 [[3,1,1],[1,2,2]]의 음료수 정보가 주어지고 p=3리터만큼 마시고자 할 때 총 4칼로리의 최대 열량을 얻을 수 있다. 첫번째 3개 있는 음..

• format_list_bulleted 알고리즘 일반
• · 2021. 11. 28.
• textsms