알고리즘30 나무 자르기 ( 백준 2805 ) https://www.acmicpc.net/problem/2805 * 랜선 자르기와 똑같은 문제* 랜선은 mid 값으로 나누었을때 갯수와 비교* 나무는 mid 값으로 뺄셈을 했을때 길이와 비교하는것* 로직은 비슷하지만 (mid+1)과 (mid-1)을 결정하는 decision() 함수를 구현할때 헷갈려서 글을 남긴다 import java.io.*;import java.util.*;public class BOJ2805 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringToken.. 2025. 3. 9. 랜선 자르기 ( 백준 1654 ) https://www.acmicpc.net/problem/1654 * 이분탐색을 기반으로한 Parametric Search 알고리즘 활용하는 문제.* 범위는 전선 길이는 1부터 시작하니 left는 1로 설정하고, right는 주어진 전선 길이중에 제일 긴 전선을 선택한다.* Binary Search는 찾아야 하는 값이 mid 값보다 크면 left = mid+1 해주었지만 위 문제는 잘라야할 길이를 결정해주어야 한다 - mid 값으로 각각의 전선을 자르면서 최종 잘려져야할 케이블 갯수를 Binary Search로 탐색하는 것이다.- 위 같은 Parametric Search는 한번 탐색한 mid 값은 탐색하지 않아야 하기 때문에 (mid+1) 과 (mid-1) 양옆을 탐색한다.- while() 조건도 le.. 2025. 3. 9. 1번 문제 보호되어 있는 글 입니다. 2025. 3. 8. 1번 풀이 보호되어 있는 글 입니다. 2025. 3. 4. UnionFind 알고리즘 개념과 구현 * UnionFind- 유니온 파인드 알고리즘은 서로소 집합 ( Disjoint Set ) 을 관리하는 알고리즘- 같은 그룹인지 판별 할때 쓰는 isConnected() 함수- 두 그룹을 합칠떄 쓰는 Union() 함수를 사용한다. 1. 연결 요소가 존재하는가?- isConnected() 함수의 로직은 2개의 node가 포함된 루트 노드가 같은지 다른지를 판단하여같으면 연결 요소가 존재한다고 판단하고 True 반환. 다르면 연결 요소가 없다고 판단하여 False 반환. 2. Graph Cycle Detection- union() 함수를 사용하여 2개의 node를 합칠때 두개의 node의 루트노드가 다를때 union 된다.하지만 두개의 루트노드가 같을때 union 할시 Cycle 발생. - 즉 두개의 no.. 2025. 3. 3. 집합의 표현 ( 백준 1717번 ) https://www.acmicpc.net/problem/1717 * UnionFind 알고리즘 문제* 연산이 주어지는데- 0이면 a가 포함되어있는 집합과 b가 포함되어 있는 집합을 합친다는 의미- 1이면 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산* 1연산을 진행했을때 포함되었으면 YES, 아니면 NO를 출력하면 된다. UnionFind 알고리즘 사용하기만 하면 풀리는 문제라서 개념은 따로 정리하겠다.아래는 코드. import java.io.*;import java.util.*;public class BOJ1717 { static int[] parents; public static void main(String[] args) throws IOException { Buff.. 2025. 3. 3. 이전 1 2 3 4 5 다음
