비밀일기

(0,0)좌표부터 (n-1,m-1)좌표까지 도달할 수 있는 모든 경로를 찾는 문제다. 다음 타일의 값이 더 작기만 하면 되는 조건이라 금방 풀 수 있을 거라 생각했다.. 처음에 그냥 bfs로 풀고 답이 나와서 제출하니 시간초과가 나왔다. 이 문제를 해결하기 위해서는 위해서는 dfs + dp로 최적화하여 계산한 다음 값을 내야 한다고 한다.. (문제는 최단 경로를 찾는 것이 아닌 가능한 모든 경로를 찾는 것이므로 bfs보단 dfs를 사용해 푸는 것이 더 낫다고 한다.!) 어떻게 최적화 해야 하는가? 🤔-> 방문한 길을 다시 방문하지 말야아 한다.  그럼 방문한 길을 어떻게 피하는가?-> dp배열의 값을 0이 아니라 음수값으로 초기화하고, 탐색한 dp배열 값이 음수인 경우에만 업데이트를 진행한다. 음수가 ..

문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.처음에는 vector> answer배열을 만들고dp 배열을 업데이트 할 때마다 같이 값을 업데이트 해줬는데,, 시간초과가 났다. 순회하면서 string 배열을 계속 확인하는데 시간이 좀 걸리나보다;;  그래서 dp배열의 역추적을 이용해 문자열을 구해보기로 하였다. dp 배열..

문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. dp배열을 사용해 풀이한다. 문자열 a b가 주어졌을때 a의 인덱스를 s, b 의 인덱스를 t라 한다.dp[s][t]인 이차원 배열을 사용하는데, 저장되는 값은 각 문자열의 끝을 a[s]와 b[t]라 했을 때 공통되는 부분수열의 최대 길이이다. a[s]==b[t]인 경우에..

문제아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?입력첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 처음에 그냥 모든 가중치가 1인 경로에서 최단거리를 찾는 문제라 생각하여 bfs로 정점과 간선의 정보를 사용해 풀이하였는데,, 메모리 초과가 나와서 마음이 힘들었다..이 문제를 해결하기 위해서는, 정점 사이 연..

문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.입력첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 출력만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시..

특정한 최단 경로문제방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c..