목록알고리즘 (4)

개발정리

트리 회전시키기

균형잡히지 않은 트리위와 같이 한 방향으로 나열된 트리를 균형 잡히지 않은 트리 라고 합니다.일반적인 트리는 시간복잡도가 O(logN) 이지만균형 잡히지 않는 트리는 시간복잡도가 O(N) 입니다.따라서 트리를 사용하는 데 있어서 비효율이 발생합니다. 왼쪽으로 돌리기public void rotateLeft(Node x){ //일단 돌리자 Node y = x.right; x.right = y.left; //y입장에서 parent 정리 if(y.left != null) y.left.parent = x; y.parent = x.parent; //x입장에서 parent 정리 if(x.parent == null){ root = y; } else if(x == x.parent.left){ x.parent.l..
알고리즘 2025. 5. 4. 13:22
배열 90도 회전 시키기

public static int[][] rotate90Degrees(int[][] matrix) { int n = matrix.length; // 원래 배열의 행 수 int m = matrix[0].length; // 원래 배열의 열 수 int[][] rotated = new int[m][n]; // 회전된 배열 (m x n 크기) // 배열 회전 for (int i = 0; i
알고리즘 2024. 9. 10. 13:59
자바_병합정렬

class MergeSort{ int[] preorder; void mergeSort(int[] arr) { this.preorder=new int[arr.length]; merge(arr,0,arr.length-1); } private void merge(int[] arr,int start,int end) { if(start==end) { return; } int mid=(start+end)/2; merge(arr,start,mid); merge(arr,mid+1,end); int i=start; int j=mid+1; int idx=start; while(i!=mid+1 && j!=end+1) { if(arr[i]
알고리즘/개념 2023. 7. 29. 20:20
그래프 탐색

그래프의 탐색 이란? 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘 깊이 우선 탐색과 너비우선 탐색이 있다. 깊이 우선 탐색 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 검사하지 않은 간선이 있다면 방문 더이상 갈곳없는 막힌 정점에 도달하면 되돌아감 깊이 우선 탐색의 시간 복잡도 인접리스트 이용 for문에 의해 V번 호출 각 정점에서 dfs()가 호출(E번) 따라서 시간복잡도는 O(V+E) 인접행렬 사용 인접행렬은 2차원 배열을 모두 탐색(V*V) 따라서 O(V^2)
알고리즘/개념 2023. 7. 28. 18:34
이전 Prev 1 Next 다음