포도가게의 개발일지

신장트리(spanning tree)란? - 간선의 개수 E가 노드(V)의 개수 n보다 n-1인 graph를 의미 한다. 왼쪽 그래프는 V(노드)의 개수가 5개지만 edge(간선)의 개수가 7개 이며 cyclic graph이다 출처 : 유투브 주니온TV https://www.youtube.com/watch?v=jQH2wrz04io 왼쪽 그래프는 간선의 개수가 3개를 지워 노드의 개수가 5이며 간선의 개수가 4인 acyclic graph이다 출처 : 유투브 주니온TV MST(Minimum cost spannig tree)란 가중치가 있는 간선이 있을때 cyclic graph -> acyclic graph로 만들기 위한 간선의 최소 가중치를 찾는 방법이다. 최적을 선택하는 방법으로는 프림 알고리즘과 크루스칼..

LCS란? - Longest Common Subsequence 최장 공통 부분 수열, 최장 문자열을 찾는 것이다 - X[ ~ ], Y[ ~ ], Z[ ~ ] 일때 - Xm = Yn이면 Zk = Xm = Yn이고 Z(k-1)은 X(m-1)과 Y(n-1)의 LCS이다 첫번째 정의로 인해 = (1+matrix(i-1][j-1]) = 1 + max(LCS(X(m-1)),LCS(Y(n-1))) - Xm /= Yn이면, Zk /= Xm은 Z가 X(m-1)과 Y의 LCS임을 의미한다. - Xm /= Yn이면, Zk /= Yn은 Z가 Y(n-1)과 X의 LCS임을 의미한다. 두 정의로 인해 = max(matrix[i][j-1],matrix[i-1][j]) https://www.acmicpc.net/problem/925..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 : 00와 1을 사용하여 만들 수 있는 경우의 수의 15746으로 나눈 나머지 접근법 - 타일의 개수의 따른 조합법을 찾았다 타일이 하나인 경우 조합이 1가지 타일이 둘인 경우 조합이 2가지 타일이 셋인 경우 조합이 3가지 타일이 넷인 경우 조합이 5가지 가 나왔으며 피보나치 수열처럼 f(n) = f(n-1) + f(n-2)로 움직이는 것을 확인 후 dp를 이용하여 접근 문제점 : 처음에는 top..

다이나믹 프로그래밍이란? - 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법 - 작은 문제의 값을 재활용 하여 상당한 시간복잡도를 줄 일 수 있다 - 대신 메모리를 사용하여 메모리 사용량이 증가한다 - 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization) - F(n) = F(n-1) + F(n-2)과 같이 점화식 또는 수학적 귀납법으로 적용되는 문제에 적용 할 수 있다. 대표적인 문제로는 피보나치 수열이 있다. 접근 방법으로는 top->down 형식과 bottom -> up 형식이 있다. 피포나치 수열이란? 1 = 1 2 = 2 3 = 3 = 1 + 2 4 = 3 + 2 = 1 + 2 + 2 와 같이 F(n) = F(n-1) + F(n-2)를 수학..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 1. 문제 - 외부 공기와 2개이상 맞닿은 치즈는 녹는다 - 내부 공기와 맞닿은 치즈는 카운트하지 않는다 - 내부 공기와 외부 공기가 이어지면 그건 외부공기로 친다 2. 접근법 - 처음에는 외부 공기와 내부 공기를 구별을 어떻게 해줄 것인가 모든 영역을 bfs탐색을 해야하나 고민함 - 하지만 0,0은 무조건 외부공기인데 같이 탐색되지 않으면 걔네들은 내부 공기다 - 외부공기를 -1로 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 문제 : 아기상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다. 2.접근법 - 너비 우선 탐색하여 먹이 좌표까지의 최소시간을 찾는다 - 어려웠던점 일반적인 너비우선탐색을 하면 먹이가 동시에 먹어짐 - 개선방향 먹을 수 있는 먹이의 위치를 일단 전부 찾고 그중에서 가장 가까운 거리에있는 먹이만 먹는다 - 같은거리일시 맨좌측 맨우측쪽인 먹이가 우선순위 ..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1. 문제 : 영역이 표시되지 않은 직사각형의 개수와 넓이 파악 2.접근법 - 배열의 개수가 곧 넓이 - 재귀 리밋 error로 100*100 = 10000을 설정해주었다 3. Dfs를 이용한 영역 확인 및 넓이 체크 import sys sys.stdin = open('inputs.text') sys.setrecursionlimit(10000) m,n,c = map(int,sy..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 : 가수들의 음악 방송 순서 정하기 접근법 1. 피디들의 각자 방송 순서를 정해서 온다 2. 피디들의 방송 순서에 위반되지 않게 방송 순서를 정해야 한다 -> 위상 정렬 3. 위상정렬은 DAG형태일 때 가능하며 순환되는지 체크해줘야 된다. -> 방문 체크나 사라지지 않은 간선(edge)의 개수를 파악하여 확인 4. Dfs(stack) 와 Queue(in_degree)를 이..