Algorithm50 완전탐색 응용, Next Permutation 1. 비트마스킹 순열 package com.algo.day9; import java.util.Arrays; import java.util.Scanner; public class BitmaskingPermutationTest { static int N, R, input[], numbers[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N];// 입력 수 배열 numbers = new int[R];// 순열 저장 배열 for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } .. 2024. 2. 8. DFS, 우선 순위 큐 1. DFS 1) DFS란 - 깊이 우선 탐색 - 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법 - 스택을 사용 2. 이진트리 순회 1) 순회 방법 - 전위 순회 : VLR - 중위 순회 : LVR - 후위 순회 : LRV public void dfsByPreorder() { if (isEmpty()) { System.out.println("==========preorder========"); dfsByPreorder(1); System.out.println(); } } private void dfs.. 2024. 2. 7. Tree, BFS 1. 트리 1) 트리의 개념 - 비선형 구조 - 원소들 간에 1:N 관계를 가지는 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 2) 트리의 용어 - 노드 : 트리의 원소 - 루트 : 최상위 노드 - 형제 노드 : 같은 부모 노드의 자식 노드들 - 조상 노드 : 산선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 - 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 - 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 - 노드의 차수 : 노드에 연결된 자식 노드의 수 - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 - 단말 노드 : 차수가 0인 노드 - 노드의 높이 : 루트에서 노드에 .. 2024. 2. 6. LinkedList 1. 리스트 1) 리스트란? - 순서를 가지는 데이터의 집합 - 값의 중복을 허용한다. - 순차 리스트와 연결 리스트로 나뉜다. 2) 순차 리스트 - 1차원 배열에 항목들을 순서대로 저장한다. - 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다. - 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. - 삽입 삭제 연산의 최악의 시간복잡도는 O(n) - 메모리 낭비, 새로운 배열 생성등의 문제가 있다. 3) 연결 리스트 - 개별적으로 위치하고 있는 각 원소를 연결하여 하느의 전체적인 자료구조를 이룬다. - 자료구조의 크기를 동적으로 조정 가능, 메모리의 효율적인 사용이 가능 - 삽입, 삭제 연산에 유리, 조회 연산은 불리 2. 연결 리스트 1) 기본 구조 - .. 2024. 2. 5. 이전 1 ··· 7 8 9 10 11 12 13 다음
