이항계수를 구하는 알고리즘 기초1 - 파스칼의 삼각형

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$을 이용하여 ..

• format_list_bulleted 알고리즘 일반
• · 2022. 8. 15.
• textsms

다이나믹프로그래밍 - 어떻게하면 완전탐색도 더 효율적으로 할 수 있을까?

1. 문제 N개의 block이 일렬로 있고 0부터 N-1까지 숫자가 붙어있다. 사이가 안좋은 개구리가 하나의 block위에 함께 있는데 이들이 서로 최대한 멀리 떨어지려고 한다. 만약 J와 K, J= s_h: s_h = h first += 1 else: break 현재 s-1에 첫번째 개구리가 시작할건데 blocks의 s부터 오른쪽으로 순회를 해서 h라고 두는거임 만약 h가 시작높이 s_h보다 크거나 같으면 점프할 수 있고 현재 개구리 높이 s_h를 h로 두고 first에 1을 더해서 개구리 위치를 갱신한다 근데 점프를 못하는 순간 더 이상 오른쪽으로는 못간다는 소리이므로 반복문을 탈출 s_h = blocks[s] #second frog for ind,h in enumerate(blocks[s::-1])..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 6. 23.
• textsms