무제 무제

문제 You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,..

어떠한 자료를 트리를 사용해 저장할때 많이 검색되는 단어가 leaf쪽에 있으면 검색 비용이 높음 따라서 검색 빈도에 따라 비용을 최소화 할 수 있는 트리를 구현 어떤 트리가 있을때 이 트리가 Optimal이면 양쪽의 subtree도 optimal이라는 아이디어로 접근 시간복잡도는 O(n^2) 점화식: https://gsmesie692.tistory.com/116 최적 이진 탐색 트리 (Optimal Binary Search Tree) 이전 포스팅에서 설명했던 이진 탐색 트리 (BST) 의 활용 예를 보자. 설명할 때는 보통 이해하기 쉽게 노드에 들어있는 데이터를 숫자로 가정하지만, 실제로 쓰일 때는 문자열이라던가 더 다양한 데이터가 들어갈.. gsmesie692.tistory.com

(key, value)로 이루어진 자료구조 Search Delete Delete 는 평균 O(1) 최악 O(size) Hash Table의 bucket에 값을 넣는 방식은 보통 prime divisor를 사용하는데 이는 divisor를 짝수를 쓰면 항상 짝수는 짝수 bucket에, 홀수는 홀수 bucket에 들어가게 되어 bias가 생김. 홀수 divisor를 쓰면 이런 일이 없고 소수나 20이상의 두 소수의 곱인 수를 쓰면 bias를 더 줄일 수 있음

(key, value)로 이루어진 자료구조 Search Delete Delete 는 평균 O(1) 최악 O(size) Hash Table의 bucket에 값을 넣는 방식은 보통 prime divisor를 사용하는데 이는 divisor를 짝수를 쓰면 항상 짝수는 짝수 bucket에, 홀수는 홀수 bucket에 들어가게 되어 bias가 생김. 홀수 divisor를 쓰면 이런 일이 없고 소수나 20이상의 두 소수의 곱인 수를 쓰면 bias를 더 줄일 수 있음

Vertex와 Edge로 이루어진 자료구조 G=(V,E) Undirected graph - Vertex를 잇는 Edge에 방향이 없는 그래프. 최대 edge 수 n(n-1)/2 (n은 vertex개수) Directed graph - Vertex를 잇는 Edge에 방향이 있는 그래프. 최대 edge 수 n(n-1) Connected component - 현재 연결성을 유지하면서 더 이상 vertex나 edge를 추가할 수 없는 최대한의 subgraph. connected graph에는 오직 하나의 connected component만이 존재 Cycle - 그래프에서 edge를 통한 순환. cycle은 DFS를 활용해 O(V+E)만에 찾을 수 있음 # 사이클 찾기 그래프 문제를 풀다 보면 '사이클을 찾아라'..

n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조 n개의 원소가 n개의 set으로 초기화됨 (MakeSet()) Tree를 사용하는 것이 효율적. Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j) Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n)) void simpleUnion(int i, int j) {parent[i] = j;} 효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침 두 set의 height가 같으면 union된 set의 height 증가 Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포..

여러 개의 list에서 가장 작은 값이나 가장 큰 값을 찾을 때 사용 리프는 각 list의 첫번째 값들. Winner Tree - Tournament의 승자를 node에 기록. root node는 트리에서 가장 작은 값 최종 승자는 승자가 속해있던 list의 다음 값으로 교체되고 재실행 Loser Tree - Tournament의 패자를 node에 기록 K-way merge sorting이나 Bin Packing 문제 해결에 적용됨 Bin Packing에서 Best Fit decreasing알고리즘에 Selection Tree가 사용됨 First Fit decreasing: Item을 내림차순으로 정렬한 후 첫번째부터 남는 공간이 있는 bin에 item을 채우고 안되면 새로운 bin 사용 Best Fit..

필요한 기능: IsEmpty(), Search(key), Insert(key, value), Delete(key) Search(), Insert(), Delete()의 시간복잡도 각 노드는 key와 value로 구성되어있고, root의 왼쪽 subtree의 키는 항상 root의 key보다 작으며 오른쪽은 root의 key보다 큼 Indexed Binary Search Tree는 key,value이외에 left subtree의 node개수도 저장 InOrder로 읽으면 sort된 배열의 key가 나옴 Binary search tree를 밸런싱하기 위한 방법으로는 AVL tree와 RB tree가 있음