목록2024/09/28 (4)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/90842. 접근 방법이 문제를 해결하기 위해 우선 돈의 가치를 받은 후, 내림차순으로 정렬해주었다.이를 통해 큰 값을 지닌 동전의 몫에 따라 값을 확인할 수 있도록 하였다.차례로 몫에 따라, dfs 함수를 호출 해 주고, i == n-1이라면 마지막 동전이기 떄문에, 나머지가 0이라면 1을 return 해 주었다. 이후, count_coin이라는 함수를 작성하였다.total은 남은 금액을 의미하고, i는 동전의 순서를 의미한다. c_dict는 이전에 동일하게 계산한 값이 있다면 해당 dictionary 값을 반환해 주었다. c_dict[(i, total)] 을 통해서, 같은 값에 접근하게 된다면 딕셔너리 값을 반환해 주었다.i 는 동전의..
1. 문제https://www.acmicpc.net/problem/9251 2. 접근 방법전형적인 LCS 코드를 작성하면 된다.elif word1[j - 1] == word2[i - 1]: 헷갈린 부분이 있다면, elif 부분에 word1[j] == word2[i]로 작성하였던 점이다. j-1 과 i-1로 하나씩 감소해 주는 이유는 배열을 (n+1) 그리고 (m+1)로 늘려서 사용하기 때문이다.즉, n == 0 일 때, 그리고 m == 0 일 때, 0으로 채워주어, 다른 수들을 밀어주기 때문에 m 이 1일 때, i 는 0에 접근해야 하기 때문이다.lcs라는 함수는 재귀적으로 lcs를 해결하고자 했던 것이다. 하지만, recursion error가 발생하기에, 코드를 반복문으로 재작성해 주었다.3. 코드d..
1. 문제https://www.acmicpc.net/problem/1904 2. 접근 방법n에 대해서 나열해 보면,n = 1 -> 1개n = 2 -> 2개n = 3 -> 3개n = 4 -> 5개n = 5 -> 8개n = 6 -> 13개n = 7 -> 21개n = 8 -> 34개n = 9 -> 55개n = 10 -> 89개 잘 보면 패턴을 확인할 수 있다. 그렇다. 피보나치 수열이다. def fibo1(n, save): if n 이렇게 돌리게 되면?! 시간 초과가 나게 된다.따라서, result = (b1 + b2)%15746 이 된다.왜냐? modulo 연산은 분배가 가능하기 때문이다. 즉, 이게 동일하다는 것이다. 두 코드가 동일한 결과를 반환하는 이유는, ..
1. 개요이번에, LCS에 대해서 공부하게 되었다.LCS의 의미가 2가지로 해석될 수 있다.Longest Common SubstringLongest Common Subsequencesubstring의 경우 연속된 문자 배열을 가지는 경우의 수를 의미하며, subsequence의 경우엔 연속되지 않더라도 공통된 문자 배열의 길이를 의미한다. 참고한 코드는 내가 사랑하는 geeks for geeks...https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ Longest Common Subsequence (LCS) - GeeksforGeeksA Computer Science portal for geeks. It contains well written,..