비밀일기

이제 bfs는 하겠는데 dfs는 바로바로 써먹으려니 아직 좀 헷갈린다 dfs 재귀호출하거나 스택을 이용해서 사용할 수 있다.  재귀호출 이용시 인접 노드들을 for문으로 방문하면서 그 인접노드에 대해 dfs를 다시 시행해 단말노드까지 도달한다.  스택을 이용할 경우 스택에 인접 노드들을 모두 삽입하고 스택이 empty가 아닐 경우 스택에서 원소를 꺼내 그 노드의 인접노드들을 다시 삽입한다. 후입선출인 스택의 구조를 이용해 넣고 꺼내다보면 깊이우선 탐색을 완료할 수 있다.   트리와 쿼리 성공문제간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단..

가장 긴 증가하는 부분 수열 5  문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다. 가장 긴 증가하는 부분 수열 3을 푼 이후라 어떻게 가장 긴 ..

(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..

알파벳 성공다국어 문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.입력첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1≤R,C≤20$1 ≤ R,C ≤ 20$) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이..

안전 영역 문제재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 입력첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의..