본문 바로가기

Algorithm

[알고리즘] 깊이 우선 탐색(DFS) 2020. 8. 1. 그래프 탐색 그래프 탐색은 하나의 노드에서 시작하여 모든 노드를 차례로 한 번씩 방문한다. 깊이 우선 탐색(Depth First Search : DFS) DFS는 그래프 탐색 중 하나로 루트 노트 또는 정해진 노드로부터 시작하여 최대한 깊이 탐색한 후 더 이상 갈 곳이 없으면 다시 원점으로 돌아와 다른 루트를 탐색하는 방식이다. 모든 노드를 방문하고자 할 경우 이 방법을 선택하고, 스택 또는 재귀함수를 통해 구현한다. 너비 우선 탐색(BFS)보다는 간단하지만 검색 속도가 비교적 느리다. 예제 코드 public class DfsExam1 { static int T; // 테스트 케이스 static int N; // 조합하고자 하는 숫자, 경우의 수 static int visited[] = new int[7..
[자료구조] 이진 탐색 트리(Binary Search Tree) 2020. 7. 31. 이진 탐색 트리(Binary Search Tree) 각각의 노드가 최대 2개의 자식(Child) 노드를 가질 수 있는 트리 구조 중 하나이다. 이진 탐색 트리는 index 검색이나 숫자들을 비교하는 작업을 수행할 경우 좋은 성능을 보인다. 루트(Root) 노드를 기준으로 작은 값은 왼쪽에 위치한다. 루트(Root) 노드를 기준으로 큰 값은 오른쪽에 위치하게 된다. 모든 원소들의 값은 중복되어서는 안 된다. 이진 검색 트리 삽입 연산 root 노드가 null일 경우 노드를 생성하여 루트에 삽입 삽입할 data값이 root의 data값보다 작을 경우, 왼쪽 노드에 data를 삽입 삽입할 data값이 root의 data값보다 클 경우, 오른쪽 노드에 data를 삽입 이진 검색 트리 검색 찾고자 하는 값과 노드..
[자료구조] 자바 Queue 정리 2020. 7. 30. Queue(큐) 선입선출(FIFO : First in First Out) 구조 삽입된 순서대로 데이터들이 나열되고 가장 먼저 삽입된 데이터가 가장 먼저 나오게 되는 구조이다. 가장 먼저 저장된 데이터를 front, 가장 나중에 저장된 데이터를 rear라고 구분하고, 데이터의 삽입은 front, 데이터의 삭제는 rear에서 이루어지게 된다. 주요 메서드 메서드 내용 boolean add(Object o) 지정된 데이터를 큐에 추가 boolean offer(Object o) 큐에 데이터를 저장 Object remove() 큐에서 데이터를 꺼내 반환 (비어있을 시 NoSuchElementException) Object poll() 큐에서 데이터를 꺼내 반환 (비어있을 시 null 반환) Object eleme..
[자료구조] 자바 Stack 정리 2020. 7. 29. Stack 클래스 후입선출(LIFO : Last in First Out) 구조 데이터를 아래서부터 차곡차곡 쌓아가며 저장하는 형태이고 가장 마지막으로 저장된 데이터가 가장 먼저 꺼내지는 구조이다. 스택에 저장된 데이터는 top(마지막에 저장된 데이터)에서만 접근이 가능하다. top에서만 데이터를 삽입, 삭제가 가능하다. 주요 메서드 메서드 내용 push(E item) 데이터를 스택에 저장 pop() 가장 위에 있는 데이터를 가져온다. 데이터를 스택에서 제거 peek() 가장 위에 있는 데이터를 가져온다. 데이터를 스택에서 제거x boolean isEmpty() 스택이 비어있는지 확인 Stack 클래스 구현 public class Stack { class Node { private T data; priva..
[정렬] 버블정렬(Bubble sort) 2020. 7. 19. 버블정렬 (Bubble sort) 인접한 두 값을 비교하여 자리 교환하는 방식이다. 첫 번째 값부터 반복적으로 비교하여 한 바퀴가 끝나고 나면 마지막 값은 가장 큰 값이 된다. 선택정렬 대비 swap이 많이 이루어지기 때문에 자료가 역순으로 정렬되어 있을 경우 성능이 좋지 않다. 반대로 정렬이 어느정도 이루어져 있는 경우 성능이 좋다. 버블정렬 수행과정 배열 {23, 4 ,7, 12, 2, 1} 버블정렬 과정 1. 23과 4 비교, 23이 더 크므로 swap {4, 23, 7, 12, 2, 1} 2. 23과 7 비교, 23이 더 크므로 swap {4, 7, 23 ,12, 2, 1} 3. 23과 12 비교, 23이 더 크므로 swap {4, 7, 12, 23, 2, 1} 4. 23과 2 비교, 23이 더 ..
[정렬] 선택정렬 (Selection sort) 2020. 7. 18. 선택정렬(Selection sort) 기준점을 선정하고 가장 작은 원소를 선택하여 서로 교환해 나가는 방식의 정렬 데이터의 양이 적을수록 성능이 좋지만 데이터의 양이 많아지게 되면 속도가 느리고 성능이 좋지않다. 선택정렬 수행과정 배열 { 3, 6, 2, 4, 7, 8} 선택 정렬 과정 1. 기준점 3과 가장 작은 값 2와 자리 교환 2 {3 , 6 , 4, 7 ,8 } 2. 기준점 3과 가장 작은 값 3과 자리 교환(제자리) 2 3 { 6, 4, 7, 8} 3. 기준점 6과 가장 작은 값 4와 자리 교환 2 3 4 {6 , 7, 8} 4. 이러한 과정을 계속 해서 반복하면 오름차순 정렬 완료 2 3 4 6 7 8 작은 값을 선택하기 위해 수행되는 비교횟수는 많지만 swap되는 횟수는 적다. 예제 코드 ..

티스토리툴바