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

접근 부 배열은 수열의 연속된 부분에 대한 합이다. 다른 두개의 수열 각각의 부 배열에 대한 합이 특정한 값과 같은 조합의 갯수를 세는 문제다. 두 수열에 대해 가능한 부 배열의 합을 모두 구하고, 투포인터를 이용해 각각의 합에 대해서 특정한 값과 맞는지 갯수를 세는 방식으로 문제를 해결했다. 해결 부 배열의 합을 구하기 위해서, 구간합을 먼저 구한 뒤 이중반복문으로 존재하는 모든 부 배열의 합을 구했다. 나는 부 배열의 합을 dict형식으로 저장해, '부 배열의 합'을 Key로, '갯수'를 Value로 사용하여 한번에 처리하도록 구성했다. 그리고 한 부 배열 조합은 부 배열의 합의 종류에 대해서 오름차순으로, 다른 부 배열 조합은 내림차순으로 정렬한 뒤에 투포인터를 이용해 각자의 인덱스로 접근하여 합의..

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

접근 이름에서부터 뿜어져 나오는 위상정렬의 향기. 위상정렬에 대한 해설은 이전 게시글을 참고하자. 2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp) 문제 풀이의 우선순위 조건이 몇가지가 있다. 문제 번호가 더 큰 문제가 어려운 문제 먼저 푸는 것이 좋은 문제가 있다면, 그 문제부터 해결해야함 쉬운 문제부터 풀기 문제풀이의 우선순위(선수과목)이 있다면, 웬만하면 위상정렬일거라 생각해서 위상정렬로 방향을 잡았다. 해결 위상정렬로 기본적인 알고리즘을 구현하되, "쉬운 문제부터 풀기" 이 조건을 해결하기 위해 우선순위 큐를 사용했다.(나는 Heap큐를 사용했다) 코드가 간단하니 해설은 길게하지 않겠다. 위의 위상정렬해설과 아래 코드를 같이 ..

접근 연결된 그래프를 분할하고,그 가중치 합의 최솟값을 구해내는 문제다. 보자마자 당연히 먼저 든 생각은 다익스트라를 떠올렸지만, 그럼 마을을 분할하는 과정을 접근하기 쉽지않다. 그 다음에 든 생각은 저번에 풀었던 2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) 이 문제의 알고리즘인 크루스칼 알고리즘이 떠올랐다. 최소 스패닝 트리는 모든 노드를 연결하는 엣지들의 최소 가중치를 찾는 문제다. 그럼 모든 노드를 연결짓는 최소 가중치를 찾고, 나머지 하나 가장 큰 가중치의 엣지를 제거하면 되겠네? 라는 흐름으로 이어졌다. 해결 위에 언급했던대로, 크루스칼 알고리즘을 사용하여 쉽게 해결했다. 근데 처음 과정은 가장 큰 가중치 하나를 찾고, M..

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

접근 세상에나 중간에서 만나기라는 알고리즘이 있다는 것이 신기하다. 부분수열의 합은 고등학생 때 부분집합의 갯수를 구하는 공식을 떠올려보면 이해하기 쉽다. 고등학생 때 전체 집합의 원소의 갯수가 $ N $ 개라면, 부분집합의 갯수는 $ 2^N $이 되었다. 그런 이유는 공집합에 원소마다 [넣기 / 안넣기] 2가지의 선택권밖에 없었기에, $ 2 * 2 * ... * 2 = 2^N $으로 도출될 수 있는 것이다. 여기선 최악의 경우를 생각해보면, $ O(2^{40}) $의 시간복잡도가 나오게 된다. 중간에서 만나기는 이분 탐색과 분할 정복의 형태와 비슷하다. 이분 탐색은 매 탐색마다 $ N / 2 $ 를 수행해서 시간 복잡도가 log 단위로 나오는 반면, 중간에서 만나기는 처음 한번 $ N / 2 $ 수행하..

접근 팰린드롬 문자열의 전체 분할 갯수의 최솟값을 구하는 문제이다. 문자열의 최대 길이는 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 문제일 줄 알았지만, 그리디 형태로 접근하는 문제였다. 아. 그리디 너무 싫다. 너무 어렵다. 문제 자체는 간단한데 풀이방법에서 이게 맞을까? 하면 이게 맞는 그런 문제들이다 항상.. 처음 접근은 수집하지 않은 보석을 저장해두기 위해, heap트리 두개를 사용해서 접근했는데 시간초과가 났다. 분명 접근은 맞는 것 같은데, 시간 초과를 해결할 수가 없어서, 질문 게시판을 찾아보며 다른 사람들은 어떻게 구현했는지 보고 구조를 참고하여 해결했다. 해결 그리디 문제는 욕심쟁이기 때문에, 문제에 정렬이나, 우선순위 큐(힙 트리 등) 구조를 활용하여 조건이 되는 애들 중에 가장 큰 값을 챙기려고 하는 의도가 담겨있다. 그 의도를 생각하며, 아래 해결을 참고해보자. 먼저 보석과 가방의..

접근 주어진 그래프에서, 가중치가 최소가 되도록 하는 모든 정점을 연결하는 부분 그래프를 구하는 문제이다. 최소 스패닝 트리는 대표적으로 Kruskal 알고리즘을 활용할 수 있다. Kruskal 알고리즘은 아래와 같은 절차를 따른다. 간선들의 가중치를 오름차순으로 정렬 오름차순으로 간선들의 탐색을 진행하며, 사이클을 만들지 않는 정점들을 연결 포함된 간선의 갯수가 `정점의 갯수 - 1` 가 되면 종료 Kruskal 알고리즘을 진행할 때, 사이클을 체크하는 과정은 대표적으로 Union-Find 알고리즘을 활용한다. 간단하게 생각하면 A-B 친구, B-C 친구, A-C? => 친구 이런식의 해결방법이다. 아래는 알고리즘 진행에 대한 좋은 설명 자료이다. 해결 Kruskal 알고리즘과 Union-Find를 이..

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