반응형 컴퓨터공학 기초/알고리즘6 [알고리즘] 이진탐색트리(BST) 란 ? 이진탐색트리(BST)란? 최대 2개의 자식노드를 가지는 트리 그 하위도 이진탐색트리의 구조를 가진다. 각 노드에는 값이있으며 값사이에는 전순서가 있다. 중복값을 허용하지 않는다. 이진탐색트의 연산 삽입 삭제 검색 이진탐색의 예시 이진탐색트리(BST)의 구현 public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int size=sc.nextInt(); BSTMethod bstMethod = new BSTMethod(); BST root=null; for(int i= 0;i data) { child = insertPreNode(node.preNode, data); node.preNode = .. 2020. 2. 9. [알고리즘] 너비우선탐색(BFS) 이란 ? 너비우선탐색(BFS) 이란? Breadth First Search의 약자 어떠한 노드에서 인접한 노드들부터 순차적으로 방문하는 탐색방법 장점 최단경로를 보장한다. 단점 경로가 길 경우에는 많은 기억공간을 요구한다. 무한그래프의 경우 해가 없는경우에는 찾지도, 끝내지도 못하는 상황이 발생할 수 있다. 유한그래프의 경우 해가 없는 경우에 모든 그래프를 탐색한 후 실패로 끝난다. 깊이우선탐색(DFS)보다 구현이 복잡하다. 사용사례 최단경로를 찾고 싶을때 실행순서 예시 구현코드 public class Main { public static void main(String[] args) { int size; int command; Scanner sc = new Scanner(System.in); size = sc.n.. 2020. 2. 7. [알고리즘] 깊이우선탐색(DFS)이란 ? 깊이우선탐색(DFS)이란? Depth First Search 그래프의 탐색방법중 한 가지로 시작한 노드에서 최대한 깊숙히(더 이상 갈곳이 없을때까지)탐색한 후 원점으로 돌아와서 다른 노드들을 탐색하는 방법입니다. 깊이우선탐색의 특징 자기 자신을 호출하는 순환 알고리즘 어떤 노드를 방문했는지를 반드시 체크해야한다. 체크하지 않으면 무한루프에 빠질 수 있다. 장점 구현이 간단하다. 현재 경로상의 노드만 기억하면 되므로 저장공간이 적게든다. 목표노드가 깊은곳에 있을경우에 빠르게 찾을 수 있다. 단점 단순 검색속도는 너비우선탐색보다 느리다. 해가 없는경우에 깊이 빠질 수 있다. 구한 경로가 최단경로가 아닐 수 있다. 실행순서 예시 구현 코드 import java.util.Scanner; public class .. 2020. 2. 5. [알고리즘] 스택(Stack)이란 ? 스택(Stack)이란 ? - 선형 자료구조의 한 종류로써 한쪽 끝에서만 입/출력이 일어나는 자료구조 스택의 특징 - LIFO ( Last In First Out) : 가장 나중에 추가된것이 가장 먼저 제거된다. --> 가장 처음의 추가된것은 가장 마지막에 제거된다. 연산의 종류 - pop() : 가장 위의항목을 제거 - push() : 가장 위에 Item을 추가 - empty() : 비어있는지 검사 - peek() : 가장 위의항목을 반환 (아래 구현부에서는 top이라 칭한다) TIP..peek와 pop의 차이점 -> pop은 제거하지만 peek는 제거가 아니다 ex) 1 2 3 이 차례대로 있는 Stack의 경우 peek를 하면 1 2 3 이 그대로 있지만 pop을 하면 1 2 만 남게된다. 스택의 구.. 2020. 2. 3. [알고리즘] 퀵정렬이란 ? 퀵정렬이란 ? Divide-and-Conquer paradigm을 사용 - 풀기어려운 큰문제를 풀기쉬운 여러개의 작은문제로 바꾸어 해결 Partitioning 이용 - Pivot을 이용하여 왼쪽에는 Pivot보다 작은것들 오른쪽에는 Pivot보다 큰거를 정렬 - 1번하고 끝나는것이 아니라 정렬이 완료될때까지 재귀적으로 호출 - Pivot을 어떤방법으로 잡는지가 성능에 큰 영향을 끼친다. 시간복잡도 - 최악의경우 : O(n²) - 평균의경우 : O(nlogn) 수도코드 QuickSort(A[], p, r) { if(p 2020. 2. 2. [알고리즘] 버블정렬이란 ? 1. 버블정렬이란 ? - 인접한 두수를 비교하여 큰수를 뒤로 보내는 정렬방법. - 시간복잡도 : O(n²) 2. 구현소스 1. 큰수부터 맨뒤까지 보내야하기때문에 처음검사할때 마지막 인덱스까지 검사해야합니다. 2. 인접한 두수를 비교하여 앞인덱스의 숫자가 더 크다면 위치를 바꾸어줍니다. 3. 한번수행을 완료할때마다 뒤에서부터 큰수가 위치하게됩니다 그렇기때문에 한번수행할때마다 뒤에서부터 검사할 인덱스가 하나씩 줄어들게 됩니다. ex) 3 1 2 5 4 라는 배열이 있을때 1번수행하게 되면 5가 마지막에 위치하므로 5번째 인덱스는 검사를 하지않아도됨 3. 실행결과 2020. 2. 1. 이전 1 다음
