자료구조18 자료구조 - 선형 자료구조 연습문제 자료구조 - 선형 자료구조 연습문제 문제 1 방법 1 1. 단어의 각 스펠의 보드의 위치(x,y)를 찾는다. 2-1. 다음 스펠이 전 스펠의 위치와 x나 y가 (상황1)+1 or -1이라면 계속 진행, 해당 위치가 사용되었음을 기록하는 배열에 1를 입력 2-2. 전 스펠과의 위치가 (상황1)이 아니면 스펠의 다른 위치를 찾아서 반복 끝까지 없으면 앞의 스펠이 다른 위치가 있는지 확인 -> 재귀 -> 재귀를 구현하려고 하니 코드가 너무 복잡해져서 포기 public class Practice1 { public static boolean solution(char[][] board, String word) { int[][] visited = new int[board.length][board[0].length];.. 2023. 1. 6. 자료구조 - 우선순위 큐(Priority Queue) 자료구조 - 우선순위 큐(Priority Queue) 1. 우선순위 큐 모든 데이터에 우선 순위가 있어 우선순위가 높은 데이터가 먼저 나감 큐(FIFO)와 다르지만 우선순위가 같으면 FIFO 최소힙 및 최대힙의 삭제, 삽입과 같음 시간 복잡도 - 힙을 이용하면 가장 적은 시간 복잡도로 구현할 수 있음 2-1. 자바 기본 우선순위 큐 사용 // 자바 기본 PriorityQueue 사용 System.out.println("== 자바 기본 우선순위 큐 =="); // 우선순위: 낮은 숫자 순 PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.add(1); priorityQueue.add(7); priorityQueue.add(5); priori.. 2023. 1. 4. 자료구조 - 힙(Heap) 자료구조 - 힙(Heap) 1. 힙 중복값을 허용하며 반 정렬상태인 완전 이진트리 최솟값이나 최댓값을 찾을 때 유용 2. 최소힙, 최대힙 최소힙(Min Heap) 부모 노드 키 = 자식 노드 키 최소힙 - 삽입 - 트리의 젤 끝에 데이터 삽입후 삽입한 데이터 자식 노드이면 자리 교체 반복 2. 최소힙 삽입, 삭제 구현 - 리스트로 트리를 만들어 부모와 자식노드의 값을 비교해 자리를 바꾸어주면 되어 비교적 쉽게 구현하였다. // 비선형자료구조 - 힙 // ArrayList 로 최소 힙 구현 import java.util.ArrayList; .. 2023. 1. 4. 자료구조 - 그래프(Graph) 자료구조 - 그래프(Graph) 1. 그래프 정점과 간선으로 이루어져 연결된 정점간의 관계를 표현할 수 있는 자료구조 - 그래프와 트리의 차이점 종류 무방향 그래프 - 간선에 방향이 없는 그래프(양방향 이동이 가능) - 정점 A-B 간선 표현 : (A,B) = (B,A) 방향 그래프 - 간선에 방향이 있는 그래프(해당 방향으로만 이동) - 정점 A,B의 간선 표현 : != 가중치 그래프 - 간선에 값이 있는 그래프 완전 그래프 - 모든 정점이 모두 연결되어 있는 그래프 - 정점이 N개일 경우, 간선의 수 : N(N-1)/2 그래프 탐색 DFS- 깊이 우선 탐색(Depth First Search) - 깊이 파고들며 순회 - 한 노드의 자식노드를 끝까지 순회한 후 다른 노드 순회(자식 우선) - 각 노드 방.. 2023. 1. 3. 자료구조 - 이진탐색트리(Red - Black Tree) 자료구조 - 이진탐색트리(Red - Black Tree) 1. Red - Black Tree 조건 root 노드와 leaf 노드의 색은 black red 색 노드의 자식은 black (double red 불가능) 모든 leaf 노드에서 root 노드까지 가는 경로의 black 노드의 수는 같음 조건이 깨지는 상황에서 리밸런싱 삽입 노드 삽입 후 double red 발생 case 1 - 부모 노드의 형제 노드가 red 일 때 Recoloring 진행 - 삽입한 노드의 부모와 부모의 형제 노드를 모두 black으로 변경 - 부모의 부모 노드를 red로 변경 - 부모의 부모 노드가 root 인지에 따라 조정 진행 (root 라면 검정으로 변경, 아니면 부모 노드의 색에 따라 조정) case 2 - 부모 노드의.. 2023. 1. 2. 자료구조 - 균형 이진 탐색 트리(Balanced Binary Search Tree) 자료구조 - 균형 이진 탐색 트리(Balanced Binary Search Tree) 1. 균형 이진 탐색 트리 노드의 삽입과 삭제가 일어날 때, 균형을 유지하도록 하는 트리 종류 : AVL 트리, Red-Black 트리 2. AVL 트리 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리 BF(Balance Factor) : 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이 각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지 3. 리밸런싱 균형이 깨진 경우 - BF가 '+'이면 왼쪽 서브 트리에 이상이 있음 - BF가 '-'이면 오른쪽 서브 트리에 이상이 있음 회전 연산 - 단순 회전 : LL,RR - 이중 회전 : LR, RL LL (Left - Left) - 오른쪽 방향으로 .. 2022. 12. 30. 자료구조 - 이진 탐색 트리(Binary Search Tree) 자료구조 - 이진 탐색 트리 ( Binary Search Tree) 1. 이진 탐색 트리 규칙 - 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 - 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 - 각각의 서브 트리도 이진 탐색 트리를 유지 - 중복된 키 허용 X 특징 - 이진 탐색 트리 규칙에 의해 트리 정렬 - 이진 트리에 비해 탐색이 빠름(균형 유지 필요) - 균형 상태 : O(logN) - 불균형 상태 : O(N) 2. 이진 탐색 트리의 탐색, 삽입, 삭제 탐색 - 루트 노드 부터 시작하여 데이터 비교 - 찾는 데이터가 작으면 왼쪽 노드, 크면 오른쪽 노드로 이동 - 찾는 데이터가 없으면 null 반환 삽입 - 루트 부터 비교 시작 ( 중복 노드 발견시 종료) - 삽입할 키가 현재 노드 보다 .. 2022. 12. 30. 자료구조 - 이진 트리(Binary Tree) 자료구조 - 이진 트리(Binary Tree) 1. 트리 노드와 링크로 구성된 자료구조 계층적 구조를 나타낼 때 사용 특징 - 하나의 노드에서 다른 노드로 이동하는 경로는 유일 - 노드가 N개인 트리의 edge의 수는 N-1개 - 그래프의 일종이나 cycle이 존재 X - 모든 노드는 서로 연결되어 있음 - 하나의 edge를 끊으면 2개의 Sub-Tree로 분리됨 구조 - 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가짐 - 단말 노드(leaf node): 자식이 없는 노드(말단 노드, 잎 노드) - 내부(internal) 노드: 단말 노드가 아닌 노드 - 간선(edge): 노드를 연결하는 선 (link, branch) - 형제(sibling): 같은 부모를 가지는 노.. 2022. 12. 29. 자료구조 - 연습문제 자료구조 - 연습문제 ※ 문제 내용은 추후 추가 예정 문제 1 import java.util.Arrays; public class Practice1 { public static int[] solution(int[] arr){ int[] arrOrigin = new int[arr.length]; int idx = 0; int cnt = 0; int val ; while (cnt < arr.length){ while (arrOrigin[idx] != 0){ idx = (idx+1) % arr.length; } val = arr[cnt++]; arrOrigin[idx] = val; idx = (idx + val) % arr.length; } return arrOrigin; } public static int[.. 2022. 12. 26. 이전 1 2 다음
