개발자꿈나무

정렬의 종류 버블 정렬 (bubble sort) - 가장 기본적인 정렬로 인접한 i번째 키와 i + 1번째 키를 비교하여 교환하는 방법 - 초기 데이터가 원하는 정렬 순서로 입력되면 정렬을 도중에 멈출 수 있으며 정렬 도중 완료된 경우에도 확인할 수 있음 - 평균 시간복잡도 : O(n^2) / 최악 시간복잡도 : O(n^2) 초기값 50 20 30 10 40 1단계 20 30 10 40 50 2단계 20 10 30 40 50 3단계 10 20 30 40 50 선택 정렬 (selection sort) - 키 중 최소값을 선택하여 첫 레코드와 교환하고, 다음에는 2번부터 n번까지에서 같은 과정을 수행 - 비교횟수가 많을 수 있으나 모든 키가 한 단계에 한번만 이동하면 되므로 이동횟수는 적음 - 평균 시간복잡..

그래프의 정의 - 그래프 : 공집합이 아닌 정점의 집합과 간선의 집합으로 구성되는 자료구조 무방향 그래프 (undirected graph) - 간선을 나타내는 정점의 쌍에 순서가 없음 - 정점 A와 B를 연결하는 간선 (A, B)와 간선 (B, A)는 같은 간선으로 취급 - n개의 정점을 가진 무방향 그래프에서 최대 간선수는 n(n - 1) / 2개 방향 그래프 (directed graph) - 정점 A에서 출발하여 B로 연결되는 간선은 - n개의 정점을 가진 방향 그래프에서 최대 간선수는 n(n - 1)개 그래프의 표현 그래프의 인접행렬 표현 - 그래프 내의 정점에 다른 임의의 정점과의 여부를 표현하는 방법 - 인접행렬의 크기는 정점의 수가 n일 때 n^2 - 무방향성 그래프의 인접행렬에서는 대각선에 ..

트리의 정의 트리의 정의 - 정점(노드)와 선분(가지)를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태 - 하나 이상의 유한한 개수의 노드로 구성되며 반드시 근(Root) 노드부터 시작해서 노드와 노드의 관계는 가지(Branch)에 의해 표현 * 트리의 용어 - 노드(node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것 (A, B, C, D, E, F, G ...) - 가지(branch) : 노드와 노드의 관계를 표시하는 것으로 트리에서는 가지가 1 : n으로 연결되는 일이 많음 - 근(root) : 트리의 1번 노드 (A) - 레벨(level) : 근의 레벨을 1로 하고 근에서 가지 하나로 연결될 때마다 1씩 증가 - 부모노드(parent), 자노드(child..

스택 (Stack) 스택의 특성 - LIFO(Last In First Out) : 스택의 모든 작업은 항상 최근의 위치에 국한 - 주요 작업은 삽입, 삭제이며 시작복잡도는 O(1) - 배열로 구현하는 방법은 간단한 반면 스택의 크기가 고정된다는 단점이 있음 - 연결리스트를 이용하면 구현은 약간 복잡하지만 스택의 크기를 필요에 따라 가변적으로 변경할 수 있는 장점이 있음 //배열 구조에서 스택의 삽입 void push(element item) { //전역stack에 item의 삽입 if(top >= MAX_STACK_SIZE-1) stackfull(); stack[++top] = item; } //배열 구조에서 스택의 삭제 element pop() { //stack의 최상위 원소를 삭제하고 반환 if(to..

포인터 -> Java에는 존재하지 않는 개념 포인터의 정의 - 포인터 변수는 다른 변수의 주소를 가지고 있음 사용되는 연산자 - & : 변수의 주소는 & 연산자를 변수에 적용시켜 추출할 수 있음 - * : 포인터 변수가 가리키는 메모리의 내용을 추출하거나 변경할 때 사용 * 포인터에 대한 연산 int A[6], int *p; p = &A[3], A = [10, 15, 20, 22, 26, 28] - p : A[3]의 주소, 포인터를 의미 - *p : 22, 포인터가 가리키는 값 - *p++ : 22를 출력 후 p는 A[4]의 주소를 기억 - *p-- : 22를 출력 후 p는 A[2]의 주소를 기억 동적 메모리 할당 -> Java의 new 연산자 - 동적 메모리 할당은 프로그램에서 필요한 만큼의 메모리를 ..

자료 구조 - 자료 구조 : 자료들의 상호 연관 관계 -> 어떤 연관 관계를 가지냐에 따라 선형구조와 비선형구조로 구분 선형구조 - 데이터의 항목 사이의 관계가 1:1이며, 선후 관계가 명확한 1개의 선의 형태를 갖는 리스트 구조 - 배열, 리스트(연결 리스트, 선형 리스트), 스택, 큐, 덱으로 나뉨 비선형구조 - 데이터의 항목 사이에 1:n 또는 n:m의 관계를 갖는 그래프적 특성을 갖는 형태 - 트리, 그래프가 이에 속함 - 그래프는 사이클을 허용하며, 트리는 사이클을 허용하지 않음 알고리즘 - 컴퓨터로 문제를 풀기 위한 단계적인 절차 - 특정한 일을 수행하는 명령어들의 집합 알고리즘의 특성 - 입력 (Input) : 외부에서 제공되는 자료가 있을 수 있음 - 출력 (Ouput) : 반드시 한 개 ..