Algorithm84 자료 구조 - 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree)는 고정된 데이터 집합에서만 가능하던 이진 탐색의 단점을 보완한 이진 탐색을 위한 이진트리입니다. 그렇다면, 이진트리와 이진 탐색 트리의 다른 점은 무엇일까요? 이진 탐색 트리는 다음과 같은 규칙을 따릅니다. 왼쪽 자식 노드는 루트 노드보다 작고, 오른쪽 노드는 루트 노드보다 크다. 이진 트리 탐색에서의 이진 탐색 이진트리 탐색서의 이진 탐색은 기본적인 이진 탐색과 다르지 않습니다. 다만, 고정된 배열의 이진 탐색에서 중앙 요소가 이진트리에서는 루트 노드가 그 역할을 하게 됩니다. 목푯 값이 루트 노드보다 크면 오른쪽 트리를 탐색하고 작으면 왼쪽 트리를 탐색합니다. 그럼 위의 이진트리에서 목푯 값 34를 찾아가는 과정을 살펴보겠습니다. 목푯 값 34는 루.. 2021. 1. 17. [백준 알고리즘][자바] 1110번 : 더하기 사이클 https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 문제 해설 14를 예를 들어보자. 1 + 4 = 5이다. 새로운 수는 45이다. 4 + 5 = 9 이다. 새로운 수는 59이다. 5 + 9 = 14 이다. 새로운 수는 94이다. 9 + 4 = 13 이다. 새로운 수는 43이다. 4 + 3 = 7이다. 새로운 수는 37이다. . . . 쭉 해서 다시 14가 나올때까지의 연산의 횟수를 구해야 한다.(일의 자리는 앞에 0을 붙이고 시작).. 2021. 1. 14. 탐색 알고리즘 - 이진 탐색(Binary Search) 이진 탐색(Binary Search)은 정렬된 데이터 집합에서 사용할 수 있는 고속 탐색 알고리즘입니다. 이진 탐색을 수행하는 과정은 아래와 같습니다. 데이터 집합의 중앙에 있는 데이터를 고른다. 중앙에 있는 데이터값과 찾고자 하는 목표 값을 비교한다. 목표 값이 중앙에 있는 요소보다 작다면 중앙을 기준으로 왼쪽 데이터에 대해 새로 검색을 실시하고 크다면 오른쪽 데이터에 대해 새로이 검색을 실시합니다. 찾고자 하는 목표 값을 찾을 때까지 1~3번의 과정을 반복합니다. 예를 들어보자면, 아래와 같이 정렬된 데이터 집합이 있습니다. 이 데이터 집합에서 50을 찾아 보겠습니다. 1 5 18 20 35 40 46 50 70 90 먼저 중앙에 있는 요소를 고릅니다. 주어진 데이터 집합의 사이즈를 구하여 반으로 나.. 2021. 1. 14. 자료 구조 - 우선순위 큐와 힙 먼저 들어간 요소가 먼저 나오는(First-In First-Out) 자료 구조를 큐(Queue)라고 합니다. 우선순위 큐와 그냥 큐의 다른 점은 보통의 큐는 먼저 들어온 요소가 먼저 나가지만, 우선순위 큐에서는 요소에 우선순위를 부여해서 가장 높은 우선순위를 갖는 요소부터 빠져나가게 한다는 점에서 차이가 있습니다. 우선순위의 기준은 프로그래머에게 달려있습니다. 오름차순, 내림차순 등이 기준이 될 수도 있고, 시간의 빠름, 느림 등이 우선순위가 될 수도 있습니다. 우선순위 큐의 삽입 지금의 우선순위 큐의 기준은 값의 오름차순입니다. 이 큐에 20의 요소를 삽입한다면, 보통의 큐는 First-In First-Out의 구조로 32 뒤에 붙어야 하지만 우선순위 큐의 기준에 따라 17과 22의 사이에 삽입합니다... 2021. 1. 14. 탐색 알고리즘 - 순차 탐색(Sequential Search) 순차 탐색은 데이터의 집합(링크드 리스트, 배열등)을 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 알고리즘입니다. 순차 탐색은 '처음부터 끝까지 순서대로'라는 전략 때문에 효율은 나쁘지만, 구현이 간단하고 버그를 만들 가능성이 적어 높은 성능이 필요하지 않은 곳에서는 유용하게 사용됩니다. 아래의 코드는 링크드 리스트와 배열의 순차 탐색 코드 예입니다. ode* SLL_SequentailSearchNode(Node* Head, int Target) { //링크드 리스트를 위한 순차탐색 Node* Current = Head; Node* Match = NULL; // 탐색할 타겟과 일차하는 노드 while (Current != NULL) { //노드가 널이 아닐동안 => 널이면 빠져나옴 if .. 2021. 1. 12. [백준 알고리즘][자바] 10951번 : A+B - 4 https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 해설 일반적인 A+B 와 다른 점은 EOF를 알아야 한다는 점이다. EOF란 End of File 의 약자로 파일의 끝을 의미한다. BufferedReader를 통해 입력을 받을 때, 10952번 문제에서는 입력 값이 0이였을 때 반복문을 종료하였지만 10952번에서는 EOF를 통하여 입력을 종료 해야한다. 2021/01/10 - [Algorithm/Baekjoon] - [백준 알고리즘][자바] 10952번 : A+B -5 [백준 알고리즘][자바] 10952번 : A+B -5 https://www.a.. 2021. 1. 10. [백준 알고리즘][자바] 10952번 : A+B -5 https://www.acmicpc.net/problem/10952 10952번: A+B - 5 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 해결 방법 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Buffer.. 2021. 1. 10. [백준 알고리즘][자바] 15552번 : 빠른 A+B https://www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net 문제 해설 테스트 케이스를 여러 줄을 입력 받기 때문에 입출력 방식이 느리면 시간초과가 날 수 있다. 따라서 BufferdReader와 BufferdWriter 를 사용하여 입출력을 해야한다. 해결 방법 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade.. 2021. 1. 10. [백준 알고리즘][자바] 2884번 : 알람시계 https://www.acmicpc.net/problem/2884 2884번: 알람 시계 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, www.acmicpc.net 문제 해설 두 정수 H(시간), M(분)을 입력했을 때, 45분 앞서는 시간으로 출력을 해줘야 한다. 여기서 포인트는 45분 앞선 시간을 출력할 때, 시간의 변화를 체크해서 출력해줘야 한다는 점 해결 방법 M(분)이 음수로 떨어지면 H(시간)이 한시간 마이너스된다. M은 0~59 사이의 숫자이기 때문에 60진법이라고 생각하면 쉽게 풀 수 있다. 여기서 주의할 점은 H(시간)이 0시에서 23시로 갈 때만 체.. 2021. 1. 9. [백준 알고리즘][자바] 2753번 : 윤년 https://www.acmicpc.net/problem/2753 2753번: 윤년 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오. 윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. 예를 들어, 2012년은 4의 배수이면서 www.acmicpc.net 해결 방법 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int year; year = scan.nextInt(); if (1 2021. 1. 9. 이전 1 ··· 5 6 7 8 9 다음 반응형
