Tree 계층적인 구조를 나타내는 자료구조 트리의 용어 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말노드(terminal node) : 자식이 없는 노드 비단말노드 : 적어도 하나의 자식을 가지는 노드 자식, 부모, 형제, 조상, 자손 노드 : 인간과 동일 레벨(level) : 트리의 각층 번호 최상위 경우 level 1 그 자식은 level 2, level 2의 자식은 level 3 높이(height) : 트리의 최대 레벨(3) 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 트리의 값 저장 방식 1. 데이터와 연결 상태를 저장할 클래스 공간(=노드) 생성 public static..

1. 삽입정렬 / 머지정렬 / 퀵정렬을 구현하고, 아래의 데이터를 만들어서 시간 비교를 해주세요 1. 1~1000만까지 순서대로 숫자가 저장된 배열 public class algorithm1 { private static void insertion_sort(int[] a, int size) { for(int i = 1; i = 0 && target < a[j]) { // 타겟이 이전 원소보다 크기 전 까지 반복 a[j + 1] = a[j];// 이전 원소를 한칸씩 뒤로 j--; } //위 반복문이 끝났을 때 j인덱스보다 타겟..

Time Complexity 시간 복잡도 시간복잡도란? 시간복잡도는 문제 해결을 위한 알고리즘의 로직을 코드로 구현할 때 '입력값의 변화에 따라 연산이 실행될 경우, 연산 횟수에 비례해 시간이 얼마만큼 소요되는가'를 나타내는 것이며 Big-O 표기법을 사용해 나타낸다 2가지 코드가 있다. int n, sum = 0; scanf("%d", &n); for(int i=1;i

정렬 알고리즘 데이터를 일정한 순서로 나열하는 알고리즘 내부 정렬과 외부 정렬 30장의 카드를 한 줄로 늘어놓을 수 있는 책상에서 트럼프 카드를 정렬한다고 가정해보자 만약 카드가 30장 이하라면 모든 카드를 책상에 늘어놓고 한 번에 훑어보면서 작업할 수 있지만, 카드가 500장이라면 책상에 모든 카드를 늘어놓을 수 없기 때문에 큰 책상을 따로 마련해야 합니다. 정렬 알고리즘도 하나의 배열에서 작업할 수 있을 때에는 내부 정렬을 사용하고 하나의 배열에서 작업할 수 없을 땐 외부 정렬을 사용 한다 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘 외부 정렬은 내부 정렬을 응..

8퀸 문제란? 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓는 경우의 수를 찾는 문제 체스판에서 퀸은 현재 놓여있는 지점에서 가로*세로*대각선 8가지의 방향으로 직선 이동을 할 수 있다. 언뜻 보면 매우 쉬워보인다. 체스판의 가로줄을 행, 세로줄을 열이라고 하고 배열 인덱스에 맞추어 행과 열에 0~7 번호를 부여 한다. 퀸 배치하기 STEP1 8개의 퀸을 배치하는 조합은 8x8 총 64칸의 칸이 있다. 첫번째 퀸을 아무곳이나 배치하고 두번째 퀸을 배치할 땐 63 ..이러한 형식으로 64x63x62x61x60x59x58x57 = 178,462,987,637,760 가지이다. 그러나 이 조합을 모두 나열하기엔 현실상 불가능 하고 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있다. STE..