명이나물 라이브러리

이분 탐색이분 탐색은 영어로 Binary Search라고 한다.처음에는 이름이 조금 어렵게 느껴졌는데, 개념 자체는 생각보다 단순하다.핵심은 이것이다.정렬된 데이터에서 가운데 값을 확인하고,필요 없는 절반을 버리면서 원하는 값을 찾는 방법이다.즉, 처음부터 끝까지 하나씩 확인하는 것이 아니라,범위를 계속 절반으로 줄여가며 찾는 탐색 방법이다.이분 탐색이란?이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘이다.예를 들어 1부터 100까지 숫자 중에서 73을 찾는다고 해보자.하나씩 찾는다면 이렇게 확인해야 한다.1, 2, 3, 4, 5, ... 73운이 나쁘면 꽤 많은 숫자를 확인해야 한다.하지만 이분 탐색은 가운데부터 본다.1 ~ 100의 가운데쯤인 50을 확인한다.73은 50보다 크다.그러면..

그리디 알고리즘이번에는 코딩테스트에서 자주 나오는 그리디 알고리즘에 대해 공부했다.그리디는 이름부터 조금 낯설었다.영어로 Greedy는 “탐욕스러운”이라는 뜻인데, 알고리즘에서는 매 순간 가장 좋아 보이는 선택을 하는 방법을 의미한다.처음에는 “그냥 제일 큰 값이나 제일 작은 값을 고르면 되는 건가?”라고 생각했는데, 공부해보니 그렇게 단순하게만 볼 문제는 아니었다.그리디에서 중요한 것은 지금 선택한 것이 나중에도 손해가 되지 않는지 확인하는 것이다.그리디 알고리즘이란?그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복해서 답을 구하는 방식이다.쉽게 말하면 이런 느낌이다.지금 가장 좋아 보이는 선택을 한다.그 선택을 반복한다.최종적으로 답을 구한다.예를 들어 거스름돈을 줄 때를 생각해볼 수 있..

DP(다이나믹 프로그래밍), 중복 계산을 줄여주는 알고리즘이번에는 코딩테스트에서 자주 나오는 DP, 다이나믹 프로그래밍에 대해 공부했다.처음에는 이름부터 어렵게 느껴졌다.Dynamic Programming이라는 이름만 보면 뭔가 복잡한 알고리즘처럼 보이지만, 핵심은 생각보다 단순하다.한 번 계산한 값은 다시 계산하지 말고 저장해두었다가 재사용하는 것이다.즉, DP는 이전에 구한 작은 문제의 답을 이용해서 더 큰 문제의 답을 구하는 방식이다.1. DP란 무엇인가?DP는 Dynamic Programming의 줄임말이고, 한국어로는 동적 계획법이라고 부른다.하지만 이름보다 중요한 것은 개념이다.DP의 핵심은 다음과 같다. 핵심 개념설명저장한 번 구한 답을 배열 등에 저장한다재사용같은 계산이 필요할 때 다시 계..

한 길을 깊게 갈까, 가까운 곳부터 볼까?이번에는 코딩테스트에서 자주 나오는 DFS/BFS를 공부했다.미로 탐색, 연결 요소, 토마토, 최단 거리 문제를 풀기 전에 기본 개념을 먼저 정리해두려고 한다.처음에는 DFS와 BFS가 둘 다 “탐색”이라 비슷하게 느껴졌는데, 공부해보니 핵심 차이는 생각보다 단순했다.DFS = 한 길을 먼저 깊게 탐색한다BFS = 가까운 곳부터 차례대로 탐색한다다만 여기서 주의할 점이 있다.DFS가 한 방향으로만 가고 끝나는 것은 아니다.BFS가 진짜 동시에 모든 방향으로 움직이는 것도 아니다.이 두 부분이 처음에 조금 헷갈려서 같이 정리해보려고 한다.1. DFS와 BFS는 언제 사용할까?DFS와 BFS는 보통 그래프나 2차원 배열에서 연결된 곳을 탐색할 때 사용한다.예를 들면 ..

Java 정렬 : Arrays.sort()와 Collections.sort()는 뭐가 다를까? Arrays.sort() → 배열을 정렬할 때 사용Collections.sort() → List를 정렬할 때 사용 즉, 핵심은 내가 지금 정렬하려는 대상이 배열인지, 리스트인지를 먼저 확인하는 것이다.1. Arrays.sort()는 배열을 정렬할 때 사용한다Arrays.sort()는 배열을 정렬할 때 사용한다.예를 들어 이런 배열이 있을 때:int[] arr = {3, 1, 2};정렬은 이렇게 한다.Arrays.sort(arr);전체 코드는 다음과 같다.import java.util.Arrays;public class Main { public static void main(String[] arg..

Heap 정리, 우선순위 큐를 이해하기 위한 자료구조자료구조에서 Stack, Queue, Deque를 정리한 뒤, 이번에는 Heap에 대해 공부했다.처음에는 Heap이라는 이름만 보고 메모리 영역의 Heap을 떠올렸는데, 코딩테스트에서 말하는 Heap은 보통 우선순위가 높은 데이터를 빠르게 꺼내기 위한 자료구조를 의미한다.Java에서는 Heap을 직접 구현하기보다는 보통 PriorityQueue를 사용한다.1. Heap이란?Heap은 최댓값 또는 최솟값을 빠르게 찾기 위한 완전 이진 트리 기반 자료구조이다.코딩테스트에서는 보통 다음 상황에서 사용한다.상황사용하는 자료구조가장 작은 값을 계속 꺼내야 한다최소 힙가장 큰 값을 계속 꺼내야 한다최대 힙우선순위가 높은 작업부터 처리해야 한다우선순위 큐매번 정렬하..

자료구조: Stack, Queue, Deque, PriorityQueue자료구조의 핵심은 하나다.데이터를 어떤 순서로 꺼내야 하는가?상황떠올릴 자료구조가장 최근에 넣은 값을 먼저 꺼내야 한다Stack먼저 들어온 값을 먼저 꺼내야 한다Queue앞뒤 모두에서 넣고 빼야 한다Deque최솟값/최댓값을 계속 꺼내야 한다PriorityQueue1. Stack핵심 개념Stack은 나중에 들어온 값이 먼저 나가는 구조이다.LIFOLast In First Out예시:push(1)push(2)push(3)pop() → 3Java에서 Stack 사용Stack stack = new Stack();stack.push(1);stack.push(2);stack.push(3);System.out.println(stack.pop())..

정렬 알고리즘Arrays.sort, Comparator, 문자열 정렬, 원본 배열 보존까지코딩테스트 문제를 풀다 보면 정렬은 정말 자주 등장한다.처음에는 정렬을 단순히 숫자를 오름차순이나 내림차순으로 나열하는 기능 정도로 생각했다.하지만 문제를 풀다 보니 정렬은 단순한 문법이 아니라, 데이터를 문제 풀이에 유리한 순서로 재배치하는 과정이라는 생각이 들었다.예를 들어 K번째 수를 찾거나, 구간이 겹치는지 확인하거나, 가장 큰 수를 만들거나, 좌표를 압축하는 문제에서도 정렬이 핵심으로 사용된다.이번 글에서는 Java 기준으로 정렬의 기본 문법과 코딩테스트에서 자주 나오는 정렬 유형을 정리해보려고 한다.1. 정렬이란?정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 것이다.가장 기본적인 정렬은 오름차순 정렬..

슬라이딩 윈도우코딩테스트를 준비하면서 이번에는 슬라이딩 윈도우 알고리즘을 공부했다.이름만 들었을 때는 조금 낯설었는데, 개념을 하나씩 정리해보니 생각보다 직관적인 방식이었다.말 그대로 창문을 옆으로 밀듯이, 일정한 구간을 유지하거나 조절하면서 배열이나 문자열을 탐색하는 방법이다.처음에는 투 포인터와 비슷해 보여서 헷갈렸다.특히 left, right를 같이 쓰는 문제들이 많다 보니, 이게 투 포인터인지 슬라이딩 윈도우인지 구분이 잘 안 됐다.공부하면서 내가 이해한 기준은 이렇다.고정 길이 구간 문제는 슬라이딩 윈도우로 접근하기 좋다.가변 길이 구간 문제는 left, right 포인터를 조절하는 투 포인터 방식으로 접근한다.다만 가변 길이 문제도 현재 구간의 상태를 유지하면서 이동하기 때문에,넓은 의미에서는..