반응형 Develop/Coding Test | Algorithm17 유니온-파인드 알고리즘 집합 알고리즘에 주로 사용되는 연산: 합치기, 탐색Union: 합치기, Find: 탐색활용 시나리오조건: 여러 개의 그룹이 형성되어 있음문제: 특정 원소가 주어졌을 때, 이 원소들이 같은 그룹인지 판단해야 할 경우유니온-파인드 알고리즘과 경로 압축 알고리즘 활용파인드 연산특정 노드의 루트 노드가 무엇인지 탐색하는 방법특정 노드가 같은 집합에 있는지 확인할 때 사용A, B 두 노드가 있을 때 이 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것특정 노드부터 재귀로 거슬러 올라가며 루트 노드를 찾음과정현재 노드의 부모 노드를 확인한다. 부모 노드를 확인하다가 부모 노드가 루트 노드이면 찾기 연산을 종료한다.1에서 찾기 연산이 종료되지 않으면 1을 반복한다.1단계집합을 정의하고, 노드 7의 루트 노드를 찾.. 2025. 4. 4. 원형 큐 1. 원형 큐란?원형 큐(Circular Queue)는 일반적인 큐(Queue)의 한계를 극복한 자료구조로,배열을 원형 형태로 연결하여 큐의 공간을 효율적으로 활용하는 방식이다.✅ 일반적인 큐의 문제점일반적인 선형 큐(Linear Queue)는 enqueue(삽입)과 dequeue(삭제)를 반복하면 배열의 앞쪽 공간이 비어도 재사용할 수 없음즉, 배열의 크기를 초과하면 사용되지 않는 공간이 발생하여 비효율적임✅ 원형 큐의 특징선형 큐의 메모리 낭비 문제를 해결배열의 끝과 시작이 연결된 형태배열을 넘어가면 다시 처음으로 돌아갈 수 있음 (모듈러 연산 활용)2. 원형 큐 vs 선형 큐 비교비교 항목선형 큐 (Linear Queue)원형 큐 (Circular Queue)메모리 활용비효율적 (삭제 후 공간 재사.. 2025. 2. 14. Tree 전위, 중위, 후위 순회 입력 값1234567 소스코드package algorithm.boj;import java.io.BufferedReader;import java.io.FileInputStream;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main { public static void main(String[] args) throws IOException { System.setIn(new FileInputStream("/Users/kdelay/study/programmers/src/main/j.. 2024. 11. 7. 알고리즘 정리 및 예제 ≣ 목차동적 계획법 (Dynamic Programming, DP)예제: 피보나치 수열 (Fibonacci Sequence) • 문제 설명: 피보나치 수열의 n번째 숫자를 구하는 문제입니다. • 접근 방법: DP를 사용해 재귀적으로 구하는 대신, 중복 계산을 피하고, 계산된 값을 배열에 저장해 최적화를 할 수 있습니다.public class FibonacciDP { public static void main(String[] args) { int n = 10; System.out.println(fibonacci(n)); // Output: 55 } public static int fibonacci(int n) { if (n 추가 예제: 최소 동전 개수.. 2024. 10. 22. 기본 자료구조 및 사용법 정리 ≣ 목차 Array (배열)Java에서 배열은 고정된 크기를 가지며, 인덱스를 통해 빠르게 접근할 수 있는 자료구조입니다.public class ArrayExample { public static void main(String[] args) { // 배열 선언과 초기화 int[] arr = new int[5]; // 크기가 5인 정수형 배열 int[] initializedArr = {1, 2, 3, 4, 5}; // 초기화된 배열 // 배열 값 변경 arr[0] = 10; // 배열 순회 for (int i = 0; i ArrayList (동적 배열)ArrayList는 동적 크기.. 2024. 10. 22. 예상 알고리즘 문제 Two Sum 문제 개요: • 배열에서 두 숫자를 찾아서 더했을 때 목표 값이 되는 쌍을 찾는 문제. 해결 방법: • 배열을 한 번 순회하면서 현재 숫자의 보완 값(목표값 - 현재값)이 해시맵에 있는지 확인합니다. • 해시맵에 없다면, 현재 값을 해시맵에 저장합니다. 이렇게 하면 O(n) 시간 복잡도로 해결 가능합니다.public int[] twoSum(int[] nums, int target) { Map map = new HashMap(); for (int i = 0; i Merge Intervals 문제 개요: • 주어진 여러 간격(interval)을 병합하는 문제. 해결 방법: • 먼저 각 간격을 시작점을 기준으로 정렬합니다. • 각 간격을 순차적으로 순회하면서 겹치는 간격이 있.. 2024. 10. 22. [백준] JAVA 풀이 - 2805: 나무 자르기 https://www.acmicpc.net/problem/2805 ▶️ 힌트이분 탐색(결과값 (결과값 > 기대값) 인 경우, min = mid + 1; //1씩 증가하면서 확인 ▶️ 풀이 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenize.. 2024. 5. 10. [백준] JAVA 풀이 - 1181 : 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net ▶️ 풀이 Comparator 인터페이스를 처음 써봐서 문제 풀 때 난관이었는데, 작동법이 신기하고 새로워서 재밌었다 :3 유용하게 쓸 수 있으니 중복 제거 소스도 참고할 것! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; .. 2024. 3. 15. [백준] JAVA 풀이 - 10989 : 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net ▶️ 풀이 처음에는 시간 초과로 못 풀었었는데 인덱스 활용과 StringBuilder를 적절하게 활용하여 문제 해결 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { Buf.. 2024. 3. 14. 이전 1 2 다음 728x90 반응형
