1. 문제 4012. [모의 SW역량테스트] 요리사 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N개의 식재료를 N/2개씩 나누어 2개의 요리를 하려고 한다. 각 요리의 맛은 음식을 구성하는 식재료들의 시너지의 합으로 구해진다. 음식의 맛의 차이가 최소가 되는 경우를 찾는다면? 2. 풀이1 순열과 조합을 이용하는 문제가 될텐데 실전 문제에까지 직접 구현해서 사용할 이유는 전혀 없고 from itertools import combinations, permutations를 이용하자 처음에 풀때는 2개의 재료에 대해서는 설명이 명확한데 3개의 재료에 대해서는 시너지를 어떻게 계산하..
1. 페르마의 소정리 p가 소수이면 모든 정수 a에 대하여 $a^p$와 a를 p로 나눈 나머지는 서로 같다. 만약 a가 p의 배수가 아닌 서로소라면 $a^{(p-1)}$와 1을 p로 나눈 나머지는 서로 같다 역은 성립하지 않는다. 즉 모든 정수 a에 대하여 $a^p \equiv a (mod p)$임에도 불구하고 p가 합성수일 수 있다 2. 응용 - 이항계수를 빠르게 구하는 방법 n과 r이 10만에서 100만정도 되는 매우 큰 수에 대하여 어떻게 하면 빠르게 구할 수 있을까 파스칼의 삼각형을 이용한 다이나믹 프로그래밍으로는 이제는 불가능하다 그래서 $nCr = n! / ((n-r)! * r!)$을 직접 구할 필요가 있는데 이 경우 n과 r이 매우 크면 직접 나타내기 어려우므로 어떤 소수 p에 대해 나머지를..
1. 파스칼의 삼각형 이항계수에 대한 성질 $$nCr = n-1Cr-1 + n-1Cr$$을 이용하여 이항계수 값들을 미리 테이블에 저장해놓는다 시간복잡도는 $O(n^2)$ n과 r이 10000이상이면 사용하기 힘들지만 충분히 작다면 사용하지 않을 이유가 없을 정도로 충분히 빠르다 2. 알고리즘 2-1) 행의 수 t를 입력받는다 2-2) 1부터 t+1까지 모든 행에 대해 0으로 초기화한 2차원 배열 생성 ------------------- 만약 행의 수가 아니고 최대 1000Cr까지 구하고 싶다면??? 1001개의 행을 받아야한다는 점을 기억해야한다 ------------------- 2-3) 각 행의 맨 처음과 맨 끝은 1로 만들고 2-4) 나머지는 $nCr = n-1Cr-1 + n-1Cr$을 이용하여 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
