의식이 흐르는대로 해보는 프로그래밍

목차 접근 DP를 이용해서 행렬 곱셈을 진행할 때 최소가 되는 곱셈 연산의 횟수를 구하는 문제다. 행렬 자체는 연산이 가능하도록 순서대로 주어지는데, 우리는 연산 순서의 우선순위를 결정해야한다. 예시에도 잘 나와있지만, 일단 옮겨보도록 하겠다. 예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다. 이렇게 행렬은 연산 우선순위를 변경함으로써, 같은 연산을 진행할..

목차 접근 배낭(Knapsack) 알고리즘 문제다. 배낭 알고리즘에 대해선 자세히 써놓았던 이전 아티클을 참고해보자. 2023.12.11 - [알고리즘(Algorithm)] - [BOJ] 12865번 : 평범한 배낭(DP, Knapsack) 해결 배낭 알고리즘은 대표적인 DP 문제로 축의 의미를 어떻게 정의할건지가 중요하다. 당연히 한 축은 탐새할 물건의 인덱스가 되어야 할 것이다. 나머지 한 축은 가치를 저장할 시점의 용량이 되어야하는데, 여기선 두 가지가 있다. 하나는 사용 중인 메모리 바이트 수(`M`) 다른 하나는 비활성화 했을 때의 비용(`C`) 다. 하지만 메모리 바이트 수를 축으로 삼자니 범위가 $ 1 \le M \le 10,000,000 $ 로 말이 안된다. 그럼으로 비활성화 했을 때의 비..

목차 접근 Ref: [Velog] 그림으로 알아보는 LCS 알고리즘 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. velog.io [Wikipedia] Longest Common Subsequence Longest common subsequence - Wikipedia From Wikipedia, the free encyclopedia Algorithmic problem on pairs of sequences Comparison..

목차 접근 D.P.로 해결하는 간단한 문제. 근데 생각지도 못한 완전탐색을 진행하면서.. 너무 당연한 형태의 D.P.문제여서 그냥 풀면되겠지 했는데, 생각보다 점화식이 떠오르지 않았다. 왼발과 오른발에 대한 얘기가 있어서 어떻게 접근하지 하면서, 질문게시판 제목들을 보면서 대충 풀이를 유추했는데 시간복잡도에 관한 질문들이 많이 보였다. 그럼 혹시...? 하면서 전체탐색을 진행하며 D.P.를 수행하여 해결했다. 해결 이번에 밟아야할 발판에 대해서, (왼발, 오른발) 모든 조합에 대한 경우의 수를 탐색하며 D.P.를 수행했다. 이렇게 전체 탐색에 대한 의심을 한 이유는 입력의 길이가 100,000개 까지 들어올 수 있다는 것, (왼발, 오른발)의 조합이 5 x 5 = 25가 나옴으로 최대 시간복잡도는 `O(..

접근 으아아아아아!!! 진짜 오래 걸렸다. 접근 자체는 너무 유명한 문제라 간단하게 했는데 최적화하는 과정에서 2일은 잡아먹었다. 외판원을 잡아다가 그냥 알아서 좀 가라고 너무 말하고싶었다... 결론은 DFS로 갈 경로를 정하고, BitMask로 지금까지 방문했던 도시를 저장한다. 또한 DP를 이용해서 해당 도시 방문의 최소비용을 저장하여, 효율성을 높인다. 앞서 해결했던, 2023.12.31 - [알고리즘(Algorithm)] - [BOJ] 1562번 : 계단 수(DP, BitMask) 문제에서 설명했듯이, BitMask 방법론은 너무 큰 N에 대해선 공간 효율면에서는 맞지않을 수 있다고 말했다. 하지만 이 문제는 N이 16정도로 별로 크지 않기 때문에 BitMask를 사용해볼 수 있다. BitMask..

접근 비트마스크를 이용한 동적프로그래밍으로 해결하는 문제. 비트마스크.. 정말 하기싫었는데, 이게 동적 프로그래밍이랑 엮어서 나온다고? 최고의 조합이다. 그래도 모르면 안되는 개념이니, 비트마스크에 대한 기본적인 내용을 한번 정리해보고 가야겠다. 비트마스크(BitMask) 말그대로 비트를 마스크로 다루는 것이다. 예를 들어 우리가 어떤 인덱스의 방문을 다루기 위해선 일반적으로 배열을 사용한다. `visited = [False, False, True, False, True]` 이런식으로 방문여부를 저장하는 배열을 생성한 뒤 조작한다. 예시를 든 배열의 경우엔 2, 4번 인덱스가 방문을 했다는 것을 알 수 있다. 방문여부의 경우는 어떻게 보면 마스크 개념과 동일하다. 2, 4번 인덱스는 방문했으니까, 못 쓰..

접근 팰린드롬 문자열의 전체 분할 갯수의 최솟값을 구하는 문제이다. 문자열의 최대 길이는 2,500자이기에 인덱스 연산으로 팰린드롬 분할 전체를 구해내는 것은 힘들어보였다. 사실 이 문제는 DP 문제인데. 팰린드롬 공부를 좀 더 자세히 해보고싶어서 찾아보다, Manacher's Algorithm을 알게 되었다. 그래서 팰린드롬을 공부하는겸 Manacher's Algorithm을 이용해서 한번 문제를 해결해봤다. 해결 Manacher's Algorithm Manacher씨가 개발한 Longest Palindromic Substring을 $ O(n) $ 의 시간복잡도로 찾는 엄청난 알고리즘이다. 이 문제를 해결하면서 아래의 링크들을 참고했다. https://en.wikipedia.org/wiki/Longes..

접근 순차적인 접근으로, 우선시 되는 건물의 건설 시간 중 가장 긴 시간을 갖도록 목표 건물의 건설 시간을 구하는 문제. 느낌적으로 봤을 땐, DP, 그래프 탐색 이론등을 통해 해결할 수 있을 것 같다. 또한 사이클이 존재하지 않는다면, 위상정렬을 통해 또한 해결이 가능할 것 같아 보였다. 결론적으로는 위상정렬을 사용해서 해결했다. 위상정렬은 뭔가? https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘..

접근 문제 그대로 평범한 배낭 문제다. D.P.를 이용한 Knasack알고리즘을 사용해서 해결할 수 있다. (여담이지만, 올리고 있는 글순서를 보면 알겠지만 솔브닥 클래스 클리어중인데, 이 문제 2년전쯤 그리디 공부할 때 시도했다가 틀리고 안풀고있었던걸 이제 알았다.) (여담2이지만, 이번에 풀 때도 1초틀이었는데, 2년전에 시도했던 코드랑 구조가 똑같았다. 난 발전이 없는것인가...? 하지만 이번엔 해결했다. 내가 틀린 반례도 적어두겠다.) 해결 Knapsack 알고리즘을 사용하지 않고, 전체 탐색으로 해결 자체는 가능하다. 당연히 시간초과가 나겠지만. 그러니까 배낭문제는 그냥 배낭으로 풀자.. 변수는 아래와 같다. $ N $ : 물건의 갯수 $ K $ : 버틸 수 있는 최대 무게 dp Table은 $..