'🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록 (2 Page)

자료구조 - 이진탐색 트리 (Binary-Search-Tree)

2020.12.21

이진탐색 트리 구조 이진탐색 트리의 조건 (이진 트리와 다르다) 모든 원소는 중복된 값을 가지면 안된다. 트리의 루트를 기준으로 왼쪽에 존재하는 노드들의 값은 루트의 값보다 작아야 한다. 반대로 오른쪽에 존재하는 노드들의 값은 루트의 값보다 커야 한다. 이진탐색 트리의 삽입 위에 이진트리의 조건을 이용해서 삽입을 위 그림 처럼 해주면 된다. 삽입 코드를 작성해 보면, public class BinaryTree { Node root; public void insertNode(int value) { /* root가 비었을 경우 */ if(root == null){ root = new Node(value); }else { Node temp = this.root; while(true) { /* 왼쪽으로 가야 하..

🌻 JAVA/알고리즘, 자료구조

알고리즘 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

2020.12.21

BFS (너비 우선 탐색) BFS의 장점 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다. 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다. BFS의 단점 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다. BFS 구현 Queue에 루트를 넣어주고, 아래의 순서를 반복하면 된다. Queue에서 하나의 노드를 꺼냅니다. 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다. /..

🌻 JAVA/알고리즘, 자료구조

알고리즘 - 백트래킹(Back-Tracking)

2020.12.14

백트래킹 이란? 백트래킹은 모든 조합의 수를 살펴보지만, 조건이 만족할 때만 살펴보기 때문에 어떤 경우에 따라 훨씬 빠를수도 있다. 백트래킹 실행 순서 백트래킹은 DFS(깊이 우선 탐색)을 먼저 실행하면서 더 이상 탐색을 진행할 수 없는 상황이면 다시 되돌아 가서(백트래킹) 탐색을 진행한다. 관련 문제를 풀어보면 이해가 잘 될 것이다. www.acmicpc.net/step/34 백트래킹 단계 조금 더 복잡한 백트래킹 문제 1 www.acmicpc.net N과 M (1) 풀어보기 자연수 N이 주어지면 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하면 된다. 예를 들어, N : 3 , M : 3 일때, 중복 없이 아래 처럼 출력시키면 된다. ---------------------------..

🌻 JAVA/알고리즘, 자료구조

알고리즘 - 재귀 알고리즘 (feat. Factorial, Fibonacci)

2020.11.16

재귀(Recursion) 이란 무엇일까? 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을... 출처 : namu.wiki/w/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98 팩토리얼로 알아보는 재귀 알고리즘 먼저 팩토리얼 이란? 숫자 n이 주어졌을 때, n 부터 1까지의 곱의 결과를 뜻한다. 0! = 1 1! =..

🌻 JAVA/알고리즘, 자료구조

알고리즘 - Merge Sort (분할 정복, 병합 정렬)

2020.11.16

안녕하세요, 알고리즘을 정리하는 포스팅입니다. 다른 알고리즘을 참고하시려면 해당 카테고리를 이용해주세요. 😊 '🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록 공부한 것들 정리한 내용을 포스팅합니다. iseunghan.tistory.com 분할 정복 (Merge Sort) Merge Sort, 분할 정복, 병합 정렬, 합병 정렬 이라고도 한다. 시간복잡도는 최악의 상황까지도 O(n log n)을 보장한다. 나는 이 알고리즘을 공부할때, 분할 정복이라고 배워서 분할 정복이라고 칭하겠다. 그렇다면 왜 분할 정복일까? Merge Sort가 O(n logn)을 보장할 수 있었던 이유는 정렬 할 배열을 반으로 분할 한뒤 각각 정렬 시키고 합치기 때문에 속도가 빠르다고 할 수 있다. (아래의 이미지를 보자) ..

🌻 JAVA/알고리즘, 자료구조

알고리즘 - Counting Sort (카운팅 정렬 / 계수 정렬) 알고리즘

2020.11.16

안녕하세요, 알고리즘을 정리하는 포스팅입니다. 다른 알고리즘을 참고하시려면 해당 카테고리를 이용해주세요. 😊 '🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록 공부한 것들 정리한 내용을 포스팅합니다. iseunghan.tistory.com 계수 정렬 (Counting Sort) 카운팅 정렬은 시간복잡도가 𝚶(𝑛) 으로 속도가 빠른 알고리즘이다. 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort) 의 평균 시간복잡도는 𝚶(nlogn) 인데 카운팅 정렬은 시간복잡도가 𝚶(𝑛) 으로 속도가 아주 우수한 알고리즘이다. 카운팅 정렬을 코드로 하나하나 뜯어서 보자. 먼저, 배열은 세가지를 선언 해준다. int[] array = new int[100]; //수열의 원소 : 100개 int[] cou..

자료구조 - 이진탐색 트리 (Binary-Search-Tree)

알고리즘 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

알고리즘 - 백트래킹(Back-Tracking)

알고리즘 - 재귀 알고리즘 (feat. Factorial, Fibonacci)

알고리즘 - Merge Sort (분할 정복, 병합 정렬)

알고리즘 - Counting Sort (카운팅 정렬 / 계수 정렬) 알고리즘

티스토리툴바