코딩 테스트291 실패율 첫번째 코드 리스트 안에 두 개의 값([깨지는 못했지만 스테이지에 도달한 사람, 스테이지 번호])을 갖고 있는 리스트를 만든다.그리고 stages 리스트를 이용하여 위의 리스트를 완성한다. 거꾸로 스테이지 도달한 플레이어 수를 더해가며 깨지는 못했지만 스테이지에 도달한 사람을 나누어준다. (실패율 구하기) 스테이지0과 모든걸 클리어한 사람을 빼준 후실패율이 높은 사람 순서대로 배열 하면서, 스테이지가 낮은 순으로 배열한다. (GPT sort 함수를 도와줘!) answer이라는 리스트를 생성하여, 스테이지를 리스트에 넣고 출력한다. def solution(N, stages): answer = [] count = [[0, i] for i in range(0, N+2)] for .. 2024. 8. 26. 동적 계획법 동적 계획법 dynamic programming 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최종적으로 복잡한 문제의 답을 구하는 방법 구현 방법1. 큰 문제를 작은 문제로 나눌 수 있어야 함2. 작은 문제들이 반복해서 나타나고 사용되며, 이 작은 문제들의 결과값은 항상 같아야 함3. 모든 작은 문제들을 한 번만 계산해 dp테이블에 정리(추후 재사용시 dp 테이블 이용: "memorization")4. 동적 계획법은 top-down 방식과 bottom-up 방식이 있다. 2024. 8. 25. 조합 조합 combination 동적 계획법 순열, 조합을 코드화하지 않고 점화식을 이용조합의 점화식 만드는 방법1. 특정 문제 가정하기2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기3. 특정 문제 해결을 바탕으로 일반 점화식 도출하기 2024. 8. 24. [1차] 다트 게임 첫번째 코드 첫번째 코드라기에 무색하게도 많이 고쳤다.하지만 테스트 케이스를 통과하지 못해서...제출 내역이 없어 정답 코드로 설명하기로 한다! 3개의 다트만 쏘지만, 나는 일반화를 하여 풀고싶다는 생각이 들었다.하여 굳이 일반화된 결과로 작성하였다. ㅎㅎ; 먼저 생각한 아이디어는 함수를 따로 만들어서 숫자에 계산하자는 것이었다.그래서 점수와 함께 영역에 해당하는 값을 구하는 bonus라는 함수를 작성하였다. 사실 그리고 option이라고 해서 옵션이 있는 경우 해당 함수를 돌리려고 했으나,코드를 수정하는 과정에서 문제가 생겨 해당 부분을 제거하였다.(근데 어떻게 다시 작성하면 아래 코드와 다른 정답 코드를 작성할 수 있을 것 같다!) 점수 영역, 옵션 으로 이루어진 문자열을 분리해야한다.이를 위해서 i.. 2024. 8. 23. 083 선물 전달 첫번째 코드 완전순열에 관련된 문제로 점화식을 생각하는 것이 나는 조금 어려웠다.이전 상황을 가정한다고 했는데 계속 가정의 상황이 생각이 드는 기분이랄까? 또한 예외에 대해서도 많이 생각해야 할 것이다. 코드는 책을 참고했다. import sys n = int(input()) mod = 1000000000 dp = [0] * 1000001 dp[2] = 1 for i in range(3, n+1): dp[i] = (i-1) * (dp[i-1] + dp[i-2]) % mod print(dp[n]) 통과링크https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1947.%E2%80%85%EC%84%A0%EB%AC%BC%E2%80%.. 2024. 8. 22. 084 1로 만들기 첫번째 코드 dp를 이용한 첫번째 문제로 코드를 작성하는 방법은 보고 싶어서 책을 참고했다.개인적으로 책에는 top-down이 더 쉽다고 나와있는데,이전에 bottom-up을 경험해서 그런가... 점화식을 구하는게 더 마음이 편해서 그런가개인적으로 top-down이 더 복잡했다... 조건에 거꾸로 진행된다고 생각하면 되는 것 같다.문제 푸는 사람에 따라 푸는 방법이 다양할 것 같은 알고리즘이다. import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+1) for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] .. 2024. 8. 22. 이전 1 ··· 6 7 8 9 10 11 12 ··· 49 다음 728x90
