목록2024/09 (49)
미소를뿌리는감자의 코딩
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,..
1. 개요이번에는 knap sack 문제에 대해서 알아보았다.knap sack은 보석의 무게와 가격이 있을 때, 어떻게 최대로 높은 가격의 보석을 제한된 무게 안으로 챙길 수 있는지에 대한 문제이다.이를 dynamic programming으로 코드를 작성해서 해결하게 된다.0, 1, 2, 3, 4, 5 는 가방의 최대 무게가 0일 때, 1일 때, ...을 의미한다. 이전 보석을 확인하고, 다음 보석을 확인할 때는 2가지 경우가 생기게 된다.보석이 남은 가방의 무게를 초과할 때보석을 가방에 넣을 수 있을 때 -> 보석을 가방에 넣을 것인가, 넣지 않을 것인가.로 나뉘게 된다. 이런 점화식을 기반으로 코드를 작성하게 된다. 점화식에서 B[i][w] = max(B[i-1][w], B[i][w - wi] + v..
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/1260 2. 접근 방법특정 노드를 방문하는 데 여러 간선이 있으므로 중복적인 방문이 될 수 있다.또한 dfs와 bfs 결과를 처음 나온 결과 하나만 반환한다.따라서, 방문을 기록하기 위해서 visited_bfs와 visited_dfs 라는 리스트를 기록해 주었다. dfs의 경우 처음 stack으로 풀고 싶었지만, 실패해서 재귀로 풀게 되었다.스택으로 처리한 경우가 있을까 하여 질문 게시판을 확인하였고 아래와 같은 답변을 찾을 수 있었다.https://www.acmicpc.net/board/view/128850 recursion vs. stack- 재귀 w. 전역def dfs(node): visited_dfs.append(node) ..