목록코딩 테스트/백준 (139)
미소를뿌리는감자의 코딩
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. 문제https://www.acmicpc.net/problem/1948 2. 접근 방법최대 cost 를 0으로 채워두고, 해당 노드까지 방문할 cost 중 제일 높은 cost로 수정해주는 방식으로 적용하였다. 따라서 while dq 문을 수행하고 나면, cost 별 idx에 가장 높은 cost가 저장되어 있게 된다.뒤에서 부터 앞으로 진행하며, (reverse_edges) 이용.cost[u] == cost[v] + w 를 통해서 거리의 합이 최대가 될 수 있는 경로를 탐색하도록 구상한다. 해당 과정에서, stack 에 해당 노드를 넣었는지 유무를 파악하기 위해 visited 함수를 이용해 준다. 3. 코드from collections import dequedef longest(start, end): ..
1. 문제https://www.acmicpc.net/problem/2637 2. 접근 방법이번 문제는 정석적인 위상 정렬에서, 개수가 포함된 문제이다. part_need라는 2차원 리스트를 구성하고, 이를 통해서 위상 정렬 동안 계산이 되는 결과를 저장해 주었다.inDegree가 없는 것부터 접근하여, 마지막까지 계산을 진행하기 때문에, 필요한 부품에 대한 정보가 순차적으로 저장이 되게 된다. 만약 5번 부품이 2번 부품 3개를 필요로 하게 된다면 2번 행에 * 3을 한 idx 값을 5번 행에 더해주었다. 3. 코드from collections import dequefrom collections import defaultdictdef machine(): dq = deque() base = []..