백트래킹(Backtracking)에 대해 공부 후 정리하였습니다. Summary 백트래킹은 완전탐색을 효율적으로 줄이는 기법 DFS + Pruning 구조로 구현 시간복잡도는 최악은 지수적이지만, 가지치기로 충분히 줄어듦 코딩테스트에서 순열, 조합, 스도쿠, N-Queens, 경로 탐색 등에 많이 등장 ...
[알고리즘] 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)
너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대해 공부 후 정리하였습니다. Summary - BFS 그래프나 트리에서 가까운 정점부터 너비를 우선으로 탐색하는 알고리즘 큐(Queue)를 사용하여 구현 문제에 따라 다르지만 그래프의 경우 O(V + E), 2차원 배열의 경우 O(NM) 최단 거리 탐색,...
[알고리즘] 재귀 (Recursion)
재귀에 대해 공부 후 정리하였습니다. Summary 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법 종료 조건(기저 조건)이 반드시 필요하며, 함수 호출 스택을 사용 문제에 따라 다르지만 보통 O(분기^깊이) 분할정복, 백트래킹, DFS/BFS, 수학적 정의(팩토리얼, 피보나치 등) 등에 많이 사용 ...
[알고리즘] 순열, 조합, 부분 집합
순열, 조합, 부분 집합에 대해 공부 후 정리하였습니다. 1. 순열 (Permutation) 설명: 서로 다른 n개 중에서 r개를 순서 있게 뽑는 경우 시간 복잡도: O(n!) public class Permutation { static int n = 3; static int r = 3; static int[] a...
[알고리즘] 완전 탐색 : 브루트 포스 (Brute Force)
완전 탐색 중 Brute Force 알고리즘에 대해 정리하였습니다. 1. 완전 탐색 (Exhaustive Search) 모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법입니다. 모든 가능성을 고려하므로 항상 최적의 해를 찾을 수 있지만, 경우의 수가 많은 경우 시간과 메모리의 부담이 커질 수 있습니다. 완전 탐색의 종류 브루트 ...
[코딩테스트] Java 정리 - 2 (2)
코딩테스트에서 자주 사용되는 Java 자료구조 등을 정리했습니다. 컬렉션 프레임워크는 다양한 자료구조를 직접 구현하지 않고, 쉽게 사용할 수 있도록 제공해줍니다. D. Set 인터페이스 중복 X, 순서 X 연관 메서드 메서드 설명 add(E e) 요소 추가...
[Java] 지료형 변환과 Stream 문법
코딩테스트 문제를 풀다가 자료형 변환하는 방법 중 stream에 대해 정리하게 되었습니다. 1️⃣ Stream이란? Java 8부터 도입된 기능 배열이나 리스트 같은 데이터들을 선언형(데이터 중심 방식)으로 처리 for나 if 없이 .map(), .filter(), .collect() 등을 사용해 가공 가능 자주 쓰는 Stre...
[Java] 문자열을 배열로 변환하는 방법
코딩테스트 문제를 풀다가 String을 배열로 변환하는 방법에 대해 공부 중 정리하게 되었습니다. 1️⃣ 구분자 없는 문자열 1. split() - String[] 반환 String s = "hello"; String[] arr = s.split(""); System.out.println(Arrays.toString(arr)); // [h, e,...
[Java] 배열 복사 메서드 비교
코딩테스트 문제를 풀다가 부분 배열 반환에 대해 공부 중 정리하게 되었습니다. 1️⃣ Arrays.copyOf() Arrays.copyOf(복사할 배열, 길이) int[] original = {1, 2, 3}; int[] copy = Arrays.copyOf(original, 5); 기능 : 배열을 지정한 길이만큼 복사 특징 ...
[Java] List와 ArrayList 차이
자료구조를 공부하다가 리스트 선언에 대한 의문을 가지고 정리하게 되었습니다. 1️⃣ List vs ArrayList List : 인터페이스 ArrayList, LinkedList, Vector 등 여러 구현체(클래스)의 공통 규약을 정의합니다. add(), get(), remove() 같은 메서드가 정의되어 있지...