아이작의 작(作)

트리의 좋은 모습은 "균형 잡힌" 트리이다. "균형 잡혔다"는 뜻은 자식 노드가 한쪽 방향으로 치우치지 않고 깊이가 비슷한 상황을 이야기한다. 이진 탐색 트리에서 삽입된 노드가 균형을 깨뜨리는 경우가 발생한다. 그럴 때 우리는 트리를 회전 시켜줘야한다. 회전에서 Left 회전과 Right 회전이 있다. 오른쪽 자식의 오른쪽 sub 트리가 문제일 때 : L회전 왼쪽 자식의 왼쪽 sub 트리가 문제일 때 : R회전 L회전은 오른쪽 자식을 부모 노드로 하고 부모 노드를 자식의 왼쪽 자식으로 편입하는 것이다. R회전은 반대로 왼쪽 자식을 부모 노드로 하고 부모 노드를 자식의 오른쪽 자식으로 편입하는 것이다. 이번에는 조금 더 복잡한 경우를 보자. 오른쪽 자식의 왼쪽 sub 트리가 문제일 때 : RL회전 왼쪽 자..

오늘 공부해볼 내용은 AVL 트리이다. AVL 트리는 "균형잡힌" 이진 탐색 트리라고 할 수 있다. 트리에서 "균형잡혔다" 라는 의미는 오른쪽과 왼쪽의 서브 트리의 높이 차이가 1이하 인 경우이다. 따라서 새로운 노드를 삽입하거나, 노드를 삭제할 때 높이가 달라지는 부분에서 트리를 rotate 해야 한다. 아래는 그림으로 그려본 AVL트리의 예시이다. 지금 8에서 문제가 발생한다. 오른쪽은 깊이가 2인데 왼쪽은 0이다. 차이가 1을 초과하므로 회전 시켜줘야한다. 왼쪽으로 회전 시켜줘서 균형잡힌 트리를 만들 수 있다. 이번에도 8에서 문제가 발생한다. 왼쪽이 깊이가 2인데 오른쪽이 0이다. 차이가 1을 초과한다. 오른쪽으로 회전시켜 균형을 맞춰준다. 이번에는 조금 더 복잡한 경우이다. 회전을 여러번 해줘야..

정수의 경우 2가지 방법이 있다. 첫번째는 위와 같이 문자열로 n개의 숫자를 받아서 n번의 반복문을 돌면서 최소와 최대를 탐색하는 것이다. 두번째는 정수의 크기만큼 길이의 배열을 만들어서 각 정수에 해당하는 위치에 정수를 저장하는 것이다. 이렇게 하면 가장 먼저 등장하는 정수는 최소, 가장 뒤에 서 처음으로 등장하는 정수는 최대이다. 특정 상황에서 두번째 방법이 유리하다. 하지만 첫번째 방법이 시간 복잡도가 linear 하므로 더 보편적으로 효율적인 방법이다.

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. www.acmicpc.net 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다..

문제집: 별 찍기 (baekjoon) www.acmicpc.net 2438번 별 찍기 1 코드 #include int main(){ int n; scanf("%d", &n); for (int i = 1; i 0; k--){ printf(" "); } for (int j = 0; j < i; j ++){ printf("*"); } printf(..

2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net def chocoBBusher(n, m): l = n+m-2 h = (n-1)*(m-1) return l+h if __name__ == "__main__": n, m = list(map(int, in..