deulee의 개발 노트

문제 전위 순회하는 이진 트리가 주어진다. 이를 통해 후위 순회한 결과를 출력한다. 입력 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다. 노드의 수는 10,000개 이하이다. 예제 입력 50 30 24 5 28 45 98 52 60 예제 출력 5 28 24 45 30 60 52 98 50 문제 해결 어디서 힌트를 얻을 수 있을까? 전위 순회라는 말에서 우리는 이것을 분할 정복으로 문제를 풀 수 있다는 것을 눈치챌 수 있다. 전위 순회는 (루트)(왼쪽 자식)(오른쪽 자식) 순으로 출력하는 순회 방법으로 맨 처음 출력되는 것이 루트라는 것을 알 수 있다. 또한, 이는 이진 트리이기 때문에 루트를 기준으로 왼쪽은 더 작은 값 오른쪽은 더 큰 값이라는 것을 알 ..

알고리즘/문제 2023. 6. 4. 23:30

문제 N•M의 모눈종이 위에 아주 얇은 치즈가 다음과 같이 표시되어 있다. 회색 부분은 치즈를 나타내고 흰색 부분은 공기를 나타낸다. 이때 다음처럼 치즈 밖에 있는 공기를 외부 공기, 치즈 안에 있는 공기를 내부 공기라고 할 수 있다. 치즈는 외부 공기에 두 변 이상 만나게 되면 1시간 뒤에 사라진다. 그럼 모든 치즈가 다 녹게 되는데 몇 시간이 걸리게 될까? 이때 모눈정이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M이 주어진다. (5 ≤ N, M ≤ 100) 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 예제 입력 8 9 0 0 0 0 0 0 0 0 0 ..

알고리즘/문제 2023. 6. 4. 22:55

문제 N이 주어졌을 때 첫째 줄부터 N번째 줄까지 별을 출력한다. 이때 규칙에 따라 출력해야 한다. 입력 첫째 줄에 N이 주어진다. N은 항상 3•2^k 수이다. (0 ≤ k ≤ 10) 예제 입력 24 예제 출력 * * * ***** * * * * * * ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * * * * * * * * * * * * * ***..

알고리즘/문제 2023. 5. 30. 14:36

문제 nCm을 출력해라. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤100, m ≤ n) 예제 입력 100 6 예제 출력 1192052400 문제 해결 어디서 힌트를 얻을 수 있을까? 'nCm'과 '조합'이라는 키워드를 보았을 때 나는 이항 계수를 떠올렸다. 그리고 수많은 반복되는 중복 문제를 고려하여 다이나믹 프로그래밍도 적용도 생각했다. 그리고 최대 범위의 조합의 수를 고려하면 커다란 범위의 수를 어떻게 처리해야 할 지도 고안해야 했다. 우선 하나하나 해결해보도록 해보자. 우선 이항 계수를 삼각형으로 표현한 파스칼의 삼각형의 점화식을 보도록 하겠다. 위의 점화식에 따라 커다란 틀을 구현할 수 있겠다. 그리고 메모이제이션은 다음과 같이 할 수 있다. (N, M)쌍에 값이 이미 갱신..

알고리즘/문제 2023. 5. 26. 00:29

문제 N개의 정점을 갖는 이진 트리의 정점에 1부터 N까지의 번호가 중복 없이 매겨져 있다. 이때 중위 순환과 후위 순환이 주어졌을 때, 선위 순환을 구하는 프로그램을 작성해라. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 줄에 중위 순환을 나타내는 N개의 자연수가 주어진다. 그다음 줄에 후위 순환을 나타내는 N개의 자연수가 주어진다. 예제 입력 3 1 2 3 1 3 2 예제 출력 2 1 3 문제 해결 어디서 힌트를 얻을 수 있을까? 우선 중위 순환과 후위 순환이 어떻게 이루어지는지 알 필요가 있다. 중위 순환 : (왼쪽)(루트)(오른쪽) 후위 순환 : (왼쪽)(오른쪽)(루트) 위를 보면 알겠지만 후위 순환으로 출력하게 될 경우 루트는 가장 마지막에 존재한다. 이를 통해 루트를 ..

알고리즘/문제 2023. 5. 26. 00:04

문제 N•M의 행렬로 표현되는 맵이 주어진다. 맵은 0과 1로 이루어져 있으며 '0'은 이동할 수 있는 곳 '1'은 벽을 의미한다. (0, 0)부터 시작하여 (N-1, M-1)의 위치까지 이동하는 최단 거리를 구해야 한다. 이때 상하좌우로 이동할 수 있으며, 벽은 한 개까지 부수며 이동할 수 있다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 1,000) (1 ≤ M ≤ 1,000) 다음 줄에는 N개의 줄에 M개의 숫자가 주어진다. 예제 입력 6 4 0100 1110 1000 0000 0111 0000 예제 출력 15 문제 해결 어디서 힌트를 얻을 수 있을까? '행렬', '최단 경로'를 통해 이 문제가 BFS를 이용하여 문제를 풀 수 있다는 것을 알 수 있다. 우선 최단 경로란 한 번 방문한 노..

알고리즘/문제 2023. 5. 25. 23:14

문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 먼저 첫 줄에 적혀 있는 세 개의 숫자 중에서 하나를 골라 다음 줄로 차례대로 내려간다. 이때 다음의 조건이 있다. 파란 원은 갈 수 있는 공간이고 빨간 X는 갈 수 없는 공간이다. 이렇게 해서 최대 합과 최소 합을 구하는 문제이다. 입력 첫째 줄에 N이 입력된다. (1 N; int x, y, z; for (int i = 0; i > x; dist1[i] = x; dist2[i] = x; } int temp0 = 0, temp2 = 0; for (int i = 1; i > x >> y >> z; temp0 = dist1[0]; te..

알고리즘/문제 2023. 5. 24. 23:55

문제 사이클이 없는 무방향 그래프 트리(tree)가 주어질 때 트리의 지름을 구하는 문제다. 입력 첫째 줄에 노드의 개수 N (1 N; int X, Y, C; int ret; while (1) { if (!(std::cin >> X >> Y >> C)) break ; varr[X].push_back(P(Y, C)); varr[Y].push_back(P(X, C)); } dfs(1, 0); std::memset(cache, 0, sizeof(cache)); maxDis = 0; dfs(maxNode, 0); std::cout

알고리즘/문제 2023. 5. 24. 18:56