꾸준히 개발하자

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 출력하시오. https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이번 문제는 LIS(Longest Increasing Subsequence)문제이다. 이번 LIS는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 지금까지 LIS문제는 모두 DP를 이용하여 풀었었는데 이번 문제는 DP로 풀었더니 계속 시간초과가 발생하였다. DP를 이용하면서 할 수 있는 최적화..

자료구조와 알고리즘/백준 2023. 4. 13. 01:33

보이어-무어 (Boyer-Moore) 보이어-무어 알고리즘은 문자열 검색 알고리즘의 하나이다. 이전 글에서 봤던 것까지 생각해보면 문자열 검색 알고리즘은 다음 3가지가 있다. 1. 브루트포스 2. KMP 3. 보이어-무어 문자열의 길이가 n, 패턴 문자열의 길이가 m일때 각각의 알고리즘의 시간복잡도를 비교해보면 다음과 같다. 1. 브루트포스는 가장 단순한 알고리즘이지만 시간복잡도가 O(mn)으로 3개 중에 가장 느린 알고리즘이다. 2. KMP는 최악의경우에도 시간복잡도가 O(n)으로 매우 빠르지만 패턴안에 반복하는 요소가 없으면 효율이 떨어진다. 3. 보이어-무어는 최악의 경우 시간복잡도가 O(mn)이지만 평균적으로 O(n)보다 빠른 시간복잡도를 갖는다. 이번에 보이어-무어까지 배우고 각각의 장단점에 따..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 6. 20:52

문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. https://www.acmicpc.net/problem/12865 처음 이 문제를 봤을때 dfs방식을 이용하여 문제..

자료구조와 알고리즘/백준 2023. 4. 5. 15:11

KMP 알고리즘 KMP알고리즘이란 문자열 "ABCABCD"가 있을때 그 안에서 문자열 "ABCD"를 찾는 알고리즘이다. 우리가 잘 알고있는 브루트포스로도 찾을 수 있지만 브루트포스는 ABCABCD에서 ABCD를 찾을때 다음과 같이 비효율 적으로 탐색을 한다. (1) ABCABCD ABCD (2) ABCABCD AABCD (3) ABCABCD AAABCD (4) ABCABCD AAAABCD 하지만 우리는 (1)에서 첫번째 문자가 'A', 두번쨰 문자가 'B', 세번째 문자가 'C'라는 것을 탐색을 통해 알았기에 굳이 (2), (3)의 경우를 탐색할 필요없이 (4)로 넘어가도 된다. 즉 우리가 탐색한 부분의 정보를 최대한 효율적으로 이용하자는 말이다. 굳이 탐색했던 'B', 'C'를 다시 탐색할 필요 없이 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 5. 04:40

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. https://www.acmicpc.net/problem/2206 늘 사용하던 BFS로는 풀 수 없는 문제이다..

자료구조와 알고리즘/백준 2023. 4. 4. 18:32

다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘이란 어떤 하나의 노드에서 다른 노드들까지 가는 최단경로를 전부 찾아내는 알고리즘이다. (출발지 고정) 백준 1753번 최단경로 문제를 풀면서 공부했다. (https://www.acmicpc.net/problem/1753) 우선 알고리즘을 간략하게 보자. (문제에서 노드간의 가중치를 알려줬다는 전제에서 시작) 배열을 만들어서 모든 노드의 cost(가중치)를 INT_MAX값으로 만든다. 그리고 출발지의 cost만 0으로 바꿔주고 출발지를 방문한다. '방문한 노드에 연결된 각각의 노드들의 cost'를 '방문한 노드와 연결된 노드 사이의 cost + 방문한 노드의 cost'와 비교하여 더 작은 값을 연결된 노드의 cost로 바꿔준다. 그리고 cost의 값..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 31. 17:14

플로이드-워셜 알고리즘 다익스트라가 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이라면 플로이드-워셜 알고리즘은 모든 노드 간의 최단 경로를 구하는 알고리즘이다. 그리고 다익스트라와 다르게 음의 간선도 사용이 가능하다. 플로이드-워셜이 어떤 알고리즘인지 간단하게 보자. 노드가 a ~ e까지 5개가 있다 하고 노드를 연결하는 간선의 가중치가 각각 다르다고 하자. 만약 a -> b의 가중치가 k라 할때 플로이드-워셜 알고리즘은 a에서 b로가는 경로의 최솟값을 찾기 위해 a -> (경유지) -> b의 경우의 가중치를 k와 비교하여 최솟값을 구한다. 예를들면 여기서는 경유지에 a ~ e까지 5개를 넣어서 비교하는데 (경유지가 a 또는 b인 경우는 a -> b와 같음) 만약 a -> d -> b의 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 31. 14:55

TreeMap 우리가 쓰던 HashMap에 이진트리의 기능을 더한 자료구조이다. HashMap처럼 key와 value를 갖는 요소들로 이루어져 있고 key값을 기준으로 이진 탐색 트리처럼 정렬이 이루어진다. 그래서 key값을 기준으로 최솟값과 최댓값을 탐색할 때 시간복잡도 O(logN)으로 탐색이 가능하다. 그러나 이진 탐색 트리에서는 루트값을 기준으로 나머지 요소들이 전부 크거나 전부 작으면 탐색의 시간이 O(N)까지 늘어난다.(트리의 높이만큼의 시간 복잡도가 걸린다) 그래서 TreeMap에서는 이진 탐색 트리의 단점을 보완한 레드-블랙 트리의 자료구조를 이용한다. 레드-블랙 트리는 루트노드를 기준으로 균등하게 트리가 완성될 수 있게 규칙에 따라 트리가 만들어진다. (규칙은 https://zeddios..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 22. 21:04