반응형 Develop45 [BOJ] 15657번: N과 M (8) https://www.acmicpc.net/problem/15657* 백트래킹: "경로를 탐색하다가 해가 될 가능성이 없으면 즉시 되돌아가 다른 경로를 탐색하는" 알고리즘문제 정리N개의 자연수 중에서 M개를 고른 수열: N개의 주어진 숫자들 중에서 M개를 선택하여 수열을 만듭니다.같은 수를 여러 번 골라도 된다: 중복 선택이 허용됩니다.고른 수열은 비내림차순이어야 한다: A1≤A2≤⋯≤AM 와 같이, 뒤에 오는 숫자는 앞에 오는 숫자보다 작으면 안 됩니다.수열은 사전 순으로 증가하는 순서로 출력: 최종 결과도 사전 순으로 정렬되어야 합니다. (이 조건은 입력으로 주어진 N개의 수를 미리 정렬하고, DFS 탐색 시 올바른 순서로 탐색하면 자동으로 만족됩니다.)백트래킹의 적용 원리백트래킹은 "경로를 탐.. 2025. 6. 11. 연결 리스트 연결 리스트(Linked List) 는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조입니다. 각 노드는 데이터와 다음 요소에 대한 포인터를 가지고 있는데요. 이때, 첫 번째 노드를 HEAD, 마지막 노드를 TAIL 이라고 합니다. 연결 리스트는 메모리가 허용하는 한 요소를 계속 삽입할 수 있으며, 시각 복잡도는 탐색에는 O(n), 노드 삽입과 삭제는 O(1)라는 특징을 가지고 있습니다. 해당 아이디어로 파생된 자료구조는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List, Circular Linked List)가 존재합니다.배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용합니다. 반면, 연결 리스트는 메모.. 2025. 5. 30. DFS BFS 프루닝 기법 DFS/BFS에서 프루닝 기법이란? - 문제 예시와 실전 코드 포함프루닝(Pruning) 기법탐색 도중 불필요하거나 정답이 될 수 없는 경로를 미리 차단함으로써 탐색 시간을 줄이는 전략일반적인 프루닝 전략에는 다음이 포함됩니다:조건을 만족하지 않으면 더 이상 탐색하지 않기이미 더 나은 정답이 나온 상태라면 더 탐색하지 않기방문한 노드를 다시 방문하지 않기결과가 항상 나빠지는 경로 제거효과탐색 경로 수 감소: 중복되거나 더 비싼 경로는 무시시간 복잡도 개선: 큐에 들어가는 노드 수 감소결과의 신뢰성 유지: 정답에 영향을 주지 않으면서 성능 향상전략 설명DFS 프루닝재귀호출 전에 조건 체크하여 불필요한 경로 차단BFS 프루닝큐에 넣기 전에 최단 비용 조건 확인공통 장점탐색 공간을 줄여 속도 개선예제: 최소 .. 2025. 5. 22. 벨만-포드 알고리즘 그래프 최단 경로 구하기 2. 벨만-포드 알고리즘 최단 경로는 '가중치' 유무에 따라 다르다가중치가 없는 그래프에서는 간선 개수가 가장 적은 경로가중치가 있는 그래프에서는 가중치의 총합이 최소가 되는 경로벨만-포드 알고리즘노드에서 노드까지의 최소 비용을 구한다.매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로, '음의 가중치'를 가지는 그래프에서도 최단 경로를 구할 수 있는 특징이 있다.다익스트라 알고리즘은 음의 가중치를 허용하지 않는다는 점과 차별화된다.시작 노드 최소 비용:0, 나머지 노드 INF 초기화 (최소 비용을 갱신할 때 직전 노드 갱신)노드 개수 -1 만큼 연산 반복최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신하고, 직전 노드 값도 같이 갱신한다.마지막에 과정.. 2025. 4. 25. 유니온-파인드 알고리즘 집합 알고리즘에 주로 사용되는 연산: 합치기, 탐색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. 이전 1 2 3 4 5 다음 728x90 반응형
