SY DevLog

알고리즘 : 그리디 알고리즘, 정렬, 우선순위 큐 처음에 시간초과가 나서 다른 블로그를 참고해 해결하였다. 개인적으로 어려웠던 문제였다. 백준 : 1931번 회의실 배정 문제 와 달리 이번 문제는 시작시간 기준으로 정렬을 해야한다. 시작시간과 종료시간을 강의정보로 갖는 갖는 Lecture 라는 클래스를 만들어줬다. 그리고 강의들을 저장하는 lectures 배열이 필요하다. lectures 배열에 강의들을 시작시간을 기준으로 오름차순 정렬을 한다. (위의 예제로 예를 들면 lectures 배열에는 (1,3) -> (2,4) -> (3,5) 순으로 정렬됨) 이 문제에서 구하고자 하는 것은 최소 사용할 수 있는 '강의실 수' 이다. 이 문제에서 중요한건 우선순위 큐를 사용한다는 것이다. 우선순위 큐는 강의실에..

사용한 방법 : BFS 1차 시도 1번 노드부터 12번 노드까지 차례대로 시작노드로 잡고 BFS를 통해 각각의 길이가 최대가 되는 max값을 구하였다. 1번 노드가 시작점인 경우의 최대값 2번 노드가 시작점인 경우의 최대값 3번 노드가 시작점인 경우의 최대값 ... 12번 노드가 시작점인 경우의 최대값 그 후, 각각의 최대값들을 또 비교하여 그 중에서 최대가 되는 값이 최종 트리의 지름이 된다. 결과 : 메모리 초과 2차 시도 트리의 지름을 구하는 간단한 방법을 구글에서 찾아 적용하였다. 1. 먼저, 루트 노드를 시작노드로하여 가중치의 합이 가장 큰, 즉 가장 긴 곳의 노드를 maxDistNode로 지정한다. 2. 그 후, maxDistNode 노드를 다시 시작노드로 하여 가장 긴 곳의 노드까지가 트리의..

그래프 관련하여 문제를 풀다보면(가령 DFS, BFS 문제와 같은) 그래프에서 노드간의 연결관계를 저장해야 하는 경우가 있다. 이럴 때 그래프의 연결관계를 표현하는 방법이 대표적으로 두 가지가 있다. 인접 행렬 인접 리스트 인접 행렬 그래프에 N개의 노드가 있으면, N x N 이차원 행렬을 만들어서 노드와 노드 사이의 간선 가중치를 담는 방식이다. 그래프가 무방향 그래프이고, i노드와 j노드가 연결되어 있으며 둘 사이의 간선의 가중치가 w인 경우, graph[i][j] = graph[j][i] = w 로 나타낼 수 있다. 만약 그래프에 가중치가 주어지지 않은 경우에는 두 노드가 연결되어 있으면 1, 연결되어 있지 않으면 0 으로 나타내어 0과 1로만으로 연결관계를 표현할 수 있다. 혹은 boolean형으..

사용한 방법 : DFS, BFS 풀이 1. 반복문을 통해 2차원 배열 map에서 1(대륙)인 위치(n,m)를 찾는다. for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map[i][j] == 1) { isvisited = new boolean[N][N]; sameLand(i, j); // 같은 섬에 속하는 위치들의 isvisited를 true로 변경 bfs(i, j); } } } 2. 해당 지점을 포함하는 섬을 dfs방법으로 탐색한 후에 해당 위치들을 isvisited[i][j]=true로 변경한다. 여기서 isvisited[i][j]=true이며 map[i][j]=1인 위치는 (n,m)위치의 대륙과 동일한 섬에 속함을 의미한다. publi..

사용한 방법 : DFS, DP 문제 1. 처음에는 DFS만으로 문제를 풀었는데 메모리 초과가 나왔다. 생각을 해보니 DFS만으로 문제를 풀면 이미 지나갔던 경로를 다시 지나가야 한다는 문제점이 생기게 된다. 예를 들어 32 -> 30 -> 25 -> 20 -> 17 -> 15 -> 10 경로를 먼저 거친 후 재귀를 끝내고 다시 32로 돌아와서 32 -> 20 -> 17 -> 15 -> 10 경로를 구해야 할 때, 그 이전에 20 -> 17 -> 15 -> 10 으로 향하는 경로의 수를 구한 상태임에도 불구하고 갔던 경로를 또 탐색하게 된다. public static int dfs(int sm,int sn) { int count=0; for (int i = 0; i < 4; i++) { int m = sm..

사용한 방법 : DP i번째 수가 포함된 감소하는 수열의 길이 : dp[i] 전체코드 package num11722; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new ..

사용한 방법 : Stack 풀이 : 1. 왼쪽 소괄호 혹은 왼쪽 대괄호를 만나면 스택에 push한다. 2. 오른쪽 소괄호(오른쪽 대괄호)를 만났을 때, 스택의 맨 위의 문자가 왼쪽 소괄호(왼쪽 대괄호)가 아니면 균형잡힌 문자열이 아니다. - 스택의 맨 위의 문자가 왼쪽 소괄호(왼쪽 대괄호)이면 pop한다. - 스택의 맨 위의 문자가 왼쪽 소괄호(왼쪽 대괄호)가 아니면 균형잡힌 문자열이 아니므로 반복문을 빠져나간다. - 스택이 비어있으면 오른쪽 소괄호(오른쪽 대괄호)를 넣는다. 3. 문자열의 길이만큼 반복문을 마쳤을 때 스택이 비어있으면 균형잡힌 문자열이고, 스택이 비어있지 않으면 균형잡힌 문자열이 아니다. 전체코드 package num4949; import java.io.BufferedReader; im..

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제를 풀기 위해 다음과 같은 두개의 배열을 생성했다. dp[i] : 0부터 i번째 위치까지 팰린드롬 분할의 최소 개수 palindrome[j][i] : j번째부터 i번째까지의 문자열이 팰린드롬이면 true, 팰린드롬이 아니면 false 0번째부터 i번째까지 팰린드롬 분할의 최수 개수(dp[i])를 구하기 위해서는 0

사용한 방법 : BFS, DFS 어려웠던 점 : 처음에는 graph를 나타낼때 인접행렬을 사용하여 나타냈었는데 계속 메모리 초과가 났다. 그래서 ArrayList graph=new ArrayList();로 바꾸어서 해결하였다. 평소에 bfs, dfs 문제를 풀 때는 인접행렬을 이용하여 풀었기 때문에 리스트를 이용한 풀이가 낯설었다. 인접행렬의 경우, 두 정점이 인접할 경우 1을 넣고, 인접하지 않은 경우 0을 넣는 방식이다. 리스트를 사용하면 0번째 리스트에서는 정점 1과 인접한 정점들의 번호가 들어가고, 1번째 리스트에서는 정점 2와 인접한 정점들의 번호가 들어가는 식이다. 리스트를 사용하면 인접한 정점들에 대한 정보만 들어가기 때문에 메모리가 더 적게 차지한다. 즉, 메모리면에서는 행렬보다는 리스트가..

사용한 방법 : DP 2차원 배열을 이용하여 lcs를 구하였다. 예를 들어 dp[i][j]이면, 첫번째 문자열에서 i번까지의 문자열과 두번째 문자열에서 j번까지의 문자열의 LCS를 구한 값이 들어가게 된다. 먼저 예시로 주어진 ACAYKP와 CAPCAK로 LCS를 구해보면 A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K 1 2 3 3 4 4 다음과 같이 표를 완성할 수 있다. 여기서 나타나는 규칙을 보면 같은 문자가 만나는 지점에서 값이 증가한다는 점이다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K..