위상 정렬(Topological Sort)에 대해 공부 후 정리하였습니다. 위상 정렬 (Topological Sort) 1️⃣ 개념 방향 그래프에서 사이클이 없는 경우(DAG), 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 알고리즘 간선 (u → v)가 있으면 정렬 결과에서 u가 반드시 v보다 앞에 나와야 함 주로 선행 조건...
[알고리즘] 투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window)
투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window) 대해 공부 후 정리하였습니다. 1. 투 포인터 (Two Pointers) 1️⃣ 개념 두 개의 포인터(인덱스)를 이용해 배열이나 리스트를 한 번에 탐색하는 방식입니다. 이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 많고, 투 포인터로 이분 탐색 문제를 풀 수...
[알고리즘] 이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)
이분 탐색(Binary Search)과 매개변수 탐색(Parametric Search)에 대해 공부 후 정리하였습니다. 1. 이분 탐색 (Binary Search) 추가할 내용 주의 사항 : 무한루프 주의 - start와 end가 1차이날 때 주의깊게 확인 (start+end+1)/2 정렬되어야 함 응용 문제 : 해당 타겟이 몇 개 ...
[알고리즘] 백트래킹(Backtracking)
백트래킹(Backtracking)에 대해 공부 후 정리하였습니다. Summary 백트래킹은 완전탐색을 효율적으로 줄이는 기법 DFS + Pruning 구조로 구현 시간복잡도는 최악은 지수적이지만, 가지치기로 충분히 줄어듦 코딩테스트에서 순열, 조합, 스도쿠, N-Queens, 경로 탐색 등에 많이 등장 ...
[알고리즘] BFS(너비 우선 탐색), DFS(깊이 우선 탐색)
BFS(너비 우선 탐색) 및 DFS(깊이 우선 탐색)에 대해 공부 후 정리하였습니다. 1. BFS (Breadth-First Search) 추가 정리 필요 중요한 포인트 : 큐에 넣을 때 방문 표시하기 (뺄 때하면 시간 초과 가능성) 응용 문제들 거리를 찾아야 한다면 true/false 대신 숫자로 거리 저장 (+1씩...
[알고리즘] 순열, 조합, 부분 집합
순열, 조합, 부분 집합에 대해 공부 후 정리하였습니다. 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,...