SY DevLog

트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 시간복잡도 : O(m) (m은 문자열 길이) 트라이 예 트라이(Trie) 특징 트라이(Trie) 노드 특징 1. 트라이의 각 노드는 문자와 자식 노드를 맵 형태로 가지고 있다. -> Map 예를 들어, 루트노드의 경우, 자식노드가 2개이므로 Key가 'b' 이고, Value에 왼쪽 자식 노드를 가지고 있으며, Key가 'g' 이고, Value에는 오른쪽 자식 노드를 가지고 있다. 루트의 왼쪽 자식 노드도 마찬가지이다. 이 노드는 그림에서 보면 'b'를 가지고 있는 것처럼 보이지만, 사실은 특정 문자를 가지고 있는 것..

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제 먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다. Queue order = new LinkedList(); 그리고 dp 일차원 배열에는 작업의 최소 완료시간을 저장한다. dp[n] : 작업 n을 완료하기 위해 필요한 최소 시간 큐에서 가장 먼저 실행되는 작업(n)부터 하나씩 꺼낸다. dp[n] = dp[n] + time[n] 으로, dp[n]에 해당 작업의 소요시간(time[n..

2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 이중 반복문을 사용해서 브루트포스 방법으로 해결하였다. 소스코드 :

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍을 이용하여 풀이하였다. dp 배열을 3차원 배열로 만들었다. int[][][] dp = new int[T+1][3][W+1] int[][][] dp = new int[자두가 몇번째 떨어지는가][자두(사람이름)이 어느 위치에 있냐][이동횟수] dp[t][1][w] : t번째 자두가 떨어질 때, 1번 나무에서 떨어지는 경우 여태껏 w만큼 이동했을 때의 얻을 수 있는 자두 최대값 dp[t][2][w] : t번째 자두가 떨어질 때, 2번 나무에서 떨어지는 경..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) 이번에는 BFS에 대해서 다뤄볼 것이다. DFS(Depth First Search) - 깊이 우선 탐색 그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이.. lotuslee.tistory.com BFS는 너비 우선 탐색으로 특정 노드와 연결된 모든 노드들을 우선적으로 탐색한 뒤, 그 중에 하나를 선택하여 또 다시 그와 연결된 모든 노드들을 탐색하는 방식으로 진행된다. 하나의 경로만을 깊..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이 파고드는 방식이다. 반면에 BFS 는 넓이를 우선시한다. 특정 노드와 연결된 모든 노드를 한번씩 거친 다음에 다음 노드로 이동하는 방식이다. 예를 들어, 다음과 같은 그래프가 있고 1번부터 탐색을 시작한다고 할 때 왼쪽과 같은 탐색 방법을 DFS, 오른쪽과 같은 탐색 방법을 BFS라고 할 수 있다. DFS : 1 -> 2 -> 4 -> 7 -> 6 -> 3 -> 5 BFS : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 위의 DFS 방식에서 처음에 꼭..

백준 1655번 : 가운데를 말해요 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 최소힙(minHeap)과 최대힙(maxHeap) 두 개를 사용하여 푸는 문제였다. - 두 힙의 크기가 같으면, 최대힙에 입력한 값을 넣는다. - 두 힙의 크기가 다르면, 최소힙에 입력한 값을 넣는다. 그리고 최소힙의 peek() 과 최대힙의 peek()을 비교한다. 최소힙의 peek()가 최대힙의 peek()보다 더 작다면, 각각의 힙에서 poll()을 한 다음 서로 교환한다. 소스코드 :

신장 트리(Spanning Tree) : 모든 정점이 간선으로 연결되어 있으면서 사이클이 없는 그래프 예를 들어, 다음과 같은 그래프가 있다고 하자. 위 그래프에서 가능한 신장 트리는 아래와 같다. 1번부터 4번까지의 모든 정점이 연결되있으면서 사이클이 존재하지 않는다. 아래의 경우는 신장 트리가 아니다. 모든 정점이 연결되어 있으나 사이클이 존재하기 때문이다. MST(Minimum Spanning Tree) 신장 트리 중에서 간선의 비용(가중치)의 합이 최소가 되는 것을 최소 신장 트리라고 한다. 위의 그래프에서 6개의 신장 트리 중에 최소 신장 트리는 간선의 비용의 합이 6이 되는 경우이다. MST를 구하는 알고리즘은 대표적으로 2가지가 있다. 1. 프림(Prim) 알고리즘 2. 크루스칼(Kruska..

백준 2169번 : 로봇 조종하기 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 다이나믹 프로그래밍을 이용하여 풀이하였다. 오른쪽, 아래쪽으로만 움직일 수 있었다면 문제가 쉬었을텐데, 왼쪽이동이 가능함에 따라 난이도가 올라갔다. 처음에 이중for문을 사용하여 현재 위치에서의 최대가치는 dp[i][j] 는 dp[i][j] = Math.max(dp[i][j-1], Math.max(dp[i-1][j], dp[i][j+1]) + w[i][j] 왼쪽에서의 최대가치(dp[i][j-1]), 위쪽에서의 최대가치(..

백준 15990번 : 1, 2, 3 더하기 5 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 정수 n을 1,2,3의 합으로 나타내되, 1,2,3 이 연속으로 더해져서는 안된다. 백준 9095번 : 1,2,3, 더하기 문제에서 약간 변형하여 다이나믹 프로그래밍으로 해결하였다. 기존에 9095번 문제에서 dp 점화식은 다음과 같았다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 그런데 이번 문제에서는 같은 수가 연속으로 나오면 안되므로 dp를 이차원 배열로 만들어서 dp[n] 를 연산의 마지막이 1로 끝나는지, 2로 끝나는지, 3으로 끝나는지에..