전체 글 (172) 썸네일형 리스트형 [백준] 9251 LCS / DP / Python / 골5 (개발자 강화/코딩 테스트) 2024. 11. 20. 22:03 최장 공통 부분 수열 LCS를 구현하는 문제이다 LCS 개념은 이분이 굉장히 잘 설명해 두셨음https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest.. [백준] 1915 가장 큰 정사각형 DP / python 골4 (개발자 강화/코딩 테스트) 2024. 11. 20. 15:44 https://xn--acmicpc-lw16a.net/problem/1915 DP를 이용 뭔가 BFS같이 생겼는데, 아니었다 처음에는 정사각형을 판별하려면 2차원 배열을 돌아가면서 뭘 봐야 할까...하다가현재 원소의 아래한칸 원소와 오른쪽한칸 원소를 보면 정사각형 여부를 알 수 있을까? 하면서 탐색했다하지만 정사각형을 판별하는 방법이 되지는 못했고... 알고보니 현재 원소의 위쪽 한칸 원소와 왼쪽 한칸 원소, 대각선 왼쪽 위 원소를 봐야했다 현재 원소가 0이 아니라면왼쪽, 대각선 왼쪽 위, 위쪽 원소 3개를 보고,세 값의 min 값을 현재 원소에 더해준다 일단 정사각형이 형성 가능하려면,현재 원소의 왼쪽, 왼쪽 위, 위쪽으로 같은 값만큼 확장이 되어야 하기 때문에최대값을 고려하면, 그게 정사각형이 아니.. [백준] 1로 2만들기 2 / DP python 실1 (개발자 강화/코딩 테스트) 2024. 11. 19. 16:11 https://www.acmicpc.net/problem/12852 처음에 접근하려고 한 방법 일단 1,2,3인경우에는 답이 간단하게 나오니까각 경우는 직접 출력하고,그 이상의 값은 dp를 이용하도록 하려고 했다 for문으로 4부터 n+1까지 순회하면서현재 값이 2로 나누어 떨어지면 dp[i//2]를 temp 배열에 넣고현재 값이 3으로 나누어 떨어지면 dp[i//3]을 temp 배열에 넣고dp[i-1]값을 temp배열에 넣고 이 temp 배열에서 min값을 구해서 dp[i]에 min값+1을 넣었다 이와 같은 점화식을 세우게 된 이유는직접 그려봤을 때min 길이를 구하는 방법이 방금 설명한 방법과 같았기 때문 우선 이렇게 해서 1로 도달하는 최소 길이 구하는 것까지는 괜찮았는데,그 후 n에서 1로 도달하.. 이전 1 ··· 33 34 35 36 37 38 39 ··· 58 다음
