암호코드
A를 1이라고 하고, B는 2로, 그리고 Z는 26. 만약, “BEAN”을 암호화하면 25114가 나오는데 25114를 다시 영어로 바꾸면, “BEAAD”, “YAAD”, “YAN”, “YKD”, “BEKD”, “BEAN” 총 6가지가 나온다. 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있가?
A를 1이라고 하고, B는 2로, 그리고 Z는 26. 만약, “BEAN”을 암호화하면 25114가 나오는데 25114를 다시 영어로 바꾸면, “BEAAD”, “YAAD”, “YAN”, “YKD”, “BEKD”, “BEAN” 총 6가지가 나온다. 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있가?
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
D[k][n]: 0~N 수를 K번 이용해 합이 N이 되는 경우 수
정의를 먼저하고 점화식을 생각해보자
0+3, 1+2, 2+1, 3+0
K번 중에 마지막 수 (K-1) 를 선택했을 경우를 생각해보면?
D[2][3] = D[1][3] + D[1][2] + D[1][1] + D[1][0]
D[1][3]: 선택한 수가 0 이었을 때 합이 3이 되는 경우
D[1][2]: 선택한 수가 1 이었을 때 합이 2이 되는 경우
D[1][1]: 선택한 수가 2 이었을 때 합이 1이 되는 경우
D[1][0]: 선택한 수가 3 이었을 때 합이 0이 되는 경우
D[k][n]는 D[k-1][0] + D[k-1][1] + ... + D[k-1][n]
s와 e 구간의 수열이 palindrome 인지 판단하면 된다
while (s < e) {
if (array[s++] != array[e--]) {
return false;
}
}
복잡도는 N/2 * M 정도 나오겠다. 10^3 * 10^6 이기 때문에 ac받기 어려울 것 같다.
M이 크기 때문에 전처리가 필요 할 것 같다.
int f(int s, int e) {
if (s > e) return 1;
if (checked[s][e]) return cache[s][e];
checked[s][e] = 1;
return cache[s][e] = f(s + 1, e - 1) & (arr[s] == arr[e]);
}
for (int i = 1; i <= N; i++)
cache[i][i] = 1; //길이가 1인 palindrome
// i는 거리 s에서 e까지 길이
for (int i = 2; i <= n - 1; i++) {
for (int j = 1; j <= n - i; j++) {
if (arr[j] == arr[j + i] && cache[j + 1][j + i - 1]) {
cache[j][j + i] = true;
}
}
}Node insert(Node root, int val) {
if (root == null) {
return new Node(val);
}
if (root.val > val) {
root.left = insert(root.left, val);
} else {
root.right = insert(root.right, val);
}
return root;
}
boolean search(Node root, int val) {
if (root == null) {
return false;
}
if (root.val == val) {
return true;
} else if (root.val > val) {
return search(root.left, val);
} else {
return search(root.right, val);
}
}a) Inorder (Left, Root, Right) : 4 2 5 1 3
void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.key + " ");
/* now recur on right child */
printInorder(node.right);
} (b) Preorder (Root, Left, Right) : 1 2 4 5 3
void printPreorder(Node node)
{
if (node == null)
return;
/* first print data of node */
System.out.print(node.key + " ");
/* then recur on left sutree */
printPreorder(node.left);
/* now recur on right subtree */
printPreorder(node.right);
} (c) Postorder (Left, Right, Root) : 4 5 2 3 1
void printPostorder(Node node)
{
if (node == null)
return;
// first recur on left subtree
printPostorder(node.left);
// then recur on right subtree
printPostorder(node.right);
// now deal with the node
System.out.print(node.key + " ");
} (d) Breadth First or Level Order Traversal : 1 2 3 4 5
find left or right element
int findMin(BstNode* root) {
if (root == NULL) {
return -1;
}
BstNode* current = root;
while (current->left != NULL) {
current = current->left;
}
return current->data;
}
// recursion
int findMin(BstNode* root) {
if (root == NULL) {
return -1;
}
else if (root->left == NULL) {
return root->data;
}
return findMin(root->left);
}height = max (left child node of height + right child node of height) + 1
findHeight(root)
{
// if it returns 0, the leaf's height is 1 then. that is wrong. it should be 0 so, it returns -1.
if (root is null) return -1;
leftHeight = findHeight(root->left)
rightHeight = findHeight(root->right)
return max(leftHeight, rightHeight) + 1
}height = max (left child node of height + right child node of height) + 1
findHeight(root)
{
// if it returns 0, the leaf's height is 1 then. that is wrong. it should be 0 so, it returns -1.
if (root is null) return -1;
leftHeight = findHeight(root->left)
rightHeight = findHeight(root->right)
return max(leftHeight, rightHeight) + 1
}https://leetcode.com/problemset/all/?topicSlugs=tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/ https://leetcode.com/problems/minimum-depth-of-binary-tree/ https://leetcode.com/problems/invert-binary-tree/ https://leetcode.com/problems/diameter-of-binary-tree/ https://leetcode.com/problems/merge-two-binary-trees/ https://leetcode.com/problems/same-tree/
https://www.acmicpc.net/problem/10891 O(n+m)
dfs 탐색을 하다가 이미 방문했던 노드를 탐색하게 된다면 사이클을 이루는 것이다. 이 사이클을 이루는 노드들을 모두 체크해놓자. 이후에 체크된 노드를 다시 탐색하게 된다면 그 노드는 적어도 2개 이상의 사이클에 포함되어 있으므로 선인장 그래프가 아니다. 이러한 노드가 없다면 선인장 그래프이다.
#include
트리의 지름 - 트리에서 가장 긴 경로
트리의 중심: n개의 노드로 구성된 트리에서 어떤 노드 u를 제거했을때, 쪼개지는 성분들의 사이즈가 n/2 을 넘지 않으면 u를 트리의 중심이라고 부른다.
트리 또는 그래프에서 거리가 가장 먼 두 노드 사이의 거리를 “지름”이라 하고 이 지름의 중간에 해당하는 노드를 트리의 중심(center)으로 해서 트리를 재구성하면 높이(레벨)가 가장 작은 트리를 만들수 있다는 것입니다.
중요한 성질 중 하나가 트리의 반지름과 트리의 중심은 트리의 지름 위에 있다는 것(겹친다는 것)인데, 트리의 중심은 트리의 지름에서 거리상으로(정점의 개수로 판단하는 것이 아님) 가운데에 있는 노드이다.
트리의 지름 구하는 법 가장 긴 경로가 되려면 leaf node - leaf node이거나 root node - leaf node (이진트리가 해당)이여야 한다. 보통 leaf node - leaf node로 보면 된다.
root node -leaf node 의 최대 길이 (트리 높이) 싸이클이 없으므로 root에서 갈 수 있는 node의 최대 값 갱신
int height(TreeNode* root) { int h = 0;
for(int i = 0; i < root->children.size(); ++i) h = max(h, 1 + height(root->children[i]));
return h; } 높이 구하는 걸 응용해 지름을 구할 수 있다. 서브 트리 높이이를 정렬: O(NlogN) 트리 순회와 다를 바 없어 O(N) 으로 간주
int childSize[MAX_V];
int child[MAX_V][MAX_V];
int leafLongest;
// root를 루트로 하는 서브 트리의 높이 계산
int height(int root) {
// 각 자식을 루트로 하는 서브트리 높이 계산
vector
트리의 중심 구하는 법
원점 기준으로 벡터 B가 벡터 A의 반시계 방향이면 양수, 시계 방향이면 음수, 평행이면 0을 반환한다
vector cross(vector A, vector B) { //외적
return vector(A.x * B.y - B.x * A.y)
}
double ccw(vector A, vector B) { //원점을 기준으로 CounterClockWise
return cross(A, B)
}
double ccw(vector base, vector A, vector B) { //base를 기준으로 ccw 판단
ccw (A - base, B - base)
}
https://www.acmicpc.net/problem/5820