알고리즘
![[백준,BOJ 2231] 분해합(JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbP6alW%2FbtqzBsDg1t2%2FEEbcS0jVKSRUPtHEbJcMjk%2Fimg.png)
[백준,BOJ 2231] 분해합(JAVA 구현)
-내 생각 우선 알고리즘 공부를 시작하면서 자연수 n이 있을 때 각 자리수를 추출하는 방식은 공부했기 때문에 알고 있어서 푸는데 어려움은 없었다. 다만 반복문을 만들 때 범위를 어디까지 해야할까 생각해봤는데 자연수n의 범위가 1부터 1,000,000까지 였기 때문에 최소한 1,000,000을 넘는 생성자는 없다고 생각했다. 1,000,000의 경우에는 1,000,000+0+0+0+0+0+0+1 = 1,000,001이기 때문에 문제에서 주어진 자연수n의 범위를 초과하게 된다. -해법 비교적 간단하기 때문에 코드만 보고 이해가 가능할 것 같다. import java.util.*; public class Main { public static boolean create(int x,int n) { // 생성자를 ..
[Algorithm] 다이나믹 프로그래밍
-다이나믹 프로그래밍이란? 솔직히 여러 블로그나 강의를 봤을 때 드는 예시가 대표적으로 피보나치 수열이라 개념의 이해자체는 쉬웠다. 분할 정복 방식과는 다른 형태로 어떤 큰 문제가 작은 문제로 나눠질 때 또 이 큰 문제가 더 큰 문제의 작은 문제일 때, 동시에 해당 값들에 변화가 없을 때 사용한다고 한다. 즉 피보나치 수열에서 f(3) = f(2) + f(1) 이고, f(4) = f(3) + f(2)이므로 f(3)에서의 f(2)와 f(4)에서의 f(2)는 값이 변하지 않는 중복되는 연산이다. 이러한 중복 연산들을 메모이제이션 기법으로 별도로 기록해두고 (캐시같은 개념) 필요할 때 마다 가져다 사용하면 되는 것이다. 즉, f(3)의 결과를 최초로 실행할 때 저장해 둔 후, f(4)를 구할 때 f(3)을 구..
[Algorithm] 이진트리의 순회 알고리즘(JAVA 구현)
-이진트리란? 트리의 한 종류로써 대표적인 비선형 자료구조의 형태로 1개의 데이터에 대해 0, 1, 2개의 자식 노드를 가지는 트리를 말한다. 이진트리는 일반적으로 탐색을 할 때 많이 사용하는데 그 이유는 특정 데이터를 탐색하고자 할 때 좌, 우로 나뉘어서 탐색하기 때문에 한쪽을 일방적으로 제외할 수 있어 빠른 탐색속도를 가지게 된다. 이진트리의 구현은 일반적으로 배열과 노드를 이용해 구현이 가능하지만, 완전 이진트리를 제외하고는 배열을 사용할 때 많은 메모리 낭비가 발생하기 때문에 노드로 구현하는 것이 좋다. -이진트리의 순회방식 이진트리의 순회방식으로는 3가지가 존재하는데 1)전위순회, 2)중위순회, 3)후위순회이다. 이는 탐색하는 순서에 따라 구분되며 D를 현재의 노드, L을 왼쪽 자식노드,R을 오..
[Algorithm] Union-Find 알고리즘 (JAVA 구현)
-Union Find 알고리즘이란? 서로소 집합 알고리즘과 같은 개념으로 여러 개의 노드가 존재하는 그래프에서 두 노드가 연결되어있는지 판별하는 알고리즘이다. 구현에 필요한 자료구조로는 1) 모든 정점들의 부모 정점을 표현하기 위한 배열이 필요하다. 다음과 같이 6개의 독립적인 노드가 존재한다고 할 때 배열을 이용해서 원소에 해당 노드의 부모 노드를 표시하게 된다. 현재는 모두 독립된 노드이기 때문에 자기 자신을 부모로 삼는다고 할 수 있다. 1 2 3 4 5 6 1 2 3 4 5 6 이와 같은 상태에서 만약 1번 정점과 2번 정점이 연결을 수행하게 되면 두 정점을 합치는 Union작업이 수행되게 되는데, 이 과정을 거치고 나면 아래와 같이 2번 정점의 원소를 부모 정점인 1로 바꿔주게 된다. 이 과정에..