꾸준히 개발하자

위상 정렬 위상 정렬은 그래프의 정렬을 의미한다. 이를 위해서는 그래프가 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 할 필요가 있다. DAG란 간선이 단방향이어야 하며, 사이클이 존재하지 않는(어떤 노드를 출발했을 때 다시 그 노드로 돌아올 수 없는)그래프여야 한다. 위상 정렬은 그렇게 어렵지 않다. 만약 아래와 같은 그래프가 있다고 하자. 동그라미 안에 있는 숫자는 노드의 번호이고 네모 안에 있는 숫자는 노드를 가리키는 간선의 개수이다. 간단하게 다음 규칙에 맞게 정렬을 해주면 된다. (BFS 방법) 1. 네모 안에 숫자가(노드를 가리키는 간선의 개수) 0인 노드들을 Queue에 넣어준다. 2. Queue에서 노드 하나를 빼서 방문한 뒤 해당 노드의 간..

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

이진 탐색 트리 이진 탐색 트리는 이진 트리의 한 종류로써 각 노드가 key 값을 가지고 있다. 모든 노드들은 왼쪽 서브트리에 자신보다 작은 key값을 갖고있는 노드들을 포함하고 오른쪽 서브트리에 자신보다 큰 key값을 갖고있는 노드들을 포함한다. 보통 삽입, 삭제, 검색 등이 O(logN)의 시간복잡도를 갖기 때문에 빠른 정렬, 검색이 가능하다. 또한 중위 순회를 하면 key값의 오름차순으로 노드를 탐색할 수 있다. 단점은 중복 key값을 가질 수 없고 트리가 편향되면 탐색 시간이 늦어진다. (트리가 편향되는 문제를 해결하기 위해 레드-블랙 트리 등의 균형잡힌 이진 탐색 트리가 만들어졌다) 이진 탐색 트리 구현 기본적으로 Tree 클래스를 만들고 내부에 Node 클래스를 만들어 구현한다. Node들은 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 18. 03:46

리스트란? 리스트는 데이터를 순서대로 나열해 놓은 자료구조를 말한다. 리스트는 선형 리스트와 연결 리스트로 나눌 수 있는데 선형 리스트는 데이터들이 메모리에서 배열처럼 연속적으로 저장되어있는 리스트를 말하고 연결리스트는 각각의 데이터들이 메모리에 연속적으로 저장되어 있지는 않지만 각각의 데이터 안에 다음 순서의 데이터의 위치가 저장되어있는 리스트이다. 선형 리스트 구현 선형 리스트는 배열과 같은 구조이기 때문에 1차원 배열을 통해 쉽게 구현할 수 있다. class Student{ String name; int no; Student(String s, int n) { name = s; no = n; } } class Main { public static void main(String[] args) throw..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 16. 17:01

문제 수열 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