목록2024/09 (49)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/1931 2. 접근 방법문제 풀이는 생각보다 간단하다. 종료 시간을 기준으로 정렬하면 된다.이후, for 문을 돌면서, 현재 선택된 강의의 종료시간 보다, 시간 시간이 늦는 강의를 고르게 된다면,가장 빨리 강의가 끝나는 강의를 고르게 될 것이다. 여기서 lambda x: (x[1], x[0]) 에서 x[0] 은 왜 sorting을 해주는 지에 의문이 들었다.시작 시간은 상관이 없는 것 아닌가? 끝나는 시간이 같다면, 2-5이든 3-5이든 같다고 생각했다. 따라서, 질문 게시판에서 반례를 찾아보다 아래 반례를 찾았다.https://www.acmicpc.net/board/view/148737 "회의의 시작기간과 끝나는 시간이 같을 수 있다"이..
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 연산은 분배가 가능하기 때문이다. 즉, 이게 동일하다는 것이다. 두 코드가 동일한 결과를 반환하는 이유는, ..