LUNA's Archive

이진 탐색(Binary Search)란?이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 매우 빠르게 찾아내는 알고리즘입니다. 일상생활에서 전화번호부나 사전에서 단어를 찾을 때 중간쯤을 펼쳐보는 것과 같은 원리라고 생각하면 이해하기 쉽습니다.핵심 원리: "반씩 버리기"이진 탐색의 가장 중요한 전제 조건은 데이터가 반드시 오름차순이나 내림차순으로 정렬되어 있어야 한다는 것입니다.작동 방식은 다음과 같습니다:데이터의 중간값을 선택합니다.중간값과 내가 찾으려는 값을 비교합니다.값이 같다면? 탐색 종료!중간값보다 크다면? 중간값 기준 오른쪽(큰 쪽)만 남기고 왼쪽은 버립니다.중간값보다 작다면? 중간값 기준 왼쪽(작은 쪽)만 남기고 오른쪽은 버립니다.값을 찾을 때까지 이 과정을 반복합니다.예시..

Data Structure & Algorithm 2025. 12. 23. 19:09

이번에는 알고리즘 공부하다 배우게 된 Fast and Slow pointer 알고리즘에 대해 알아보려 한다.이 알고리즘은 주로 연결 리스트(Linked List)에서 두 개의 포인터를 서로 다른 속도로 이동시키며 문제를 해결하는 기법이다. 공간 복잡도를 $O(1)$로 유지하면서 강력한 효율성을 보여주는 것이 특징이다.핵심 개념두 개의 포인터를 정의합니다:Slow Pointer (거북이): 한 번에 한 칸씩 이동합니다.Fast Pointer (토끼): 한 번에 두 칸씩 이동합니다.이 속도 차이를 이용하면 데이터 구조 내에서 특정 패턴이나 지점을 매우 효율적으로 찾아낼 수 있습니다.주요 활용 사례Middle of the Linked list원리: fast가 리스트의 끝에 도달했을 때, slow는 정확히 리스..

Data Structure & Algorithm 2025. 12. 21. 04:13

Linked List란?Linked List(연결 리스트) 는데이터와 다음 노드의 주소(참조) 를 함께 저장하는 노드(Node) 들이연결된 선형 자료구조입니다.[Data | Next] -> [Data | Next] -> [Data | Next] -> null 각 노드는 자기 자신 + 다음 노드를 가리키는 참조메모리 상에서 연속적으로 저장될 필요가 없음첫 번째 노드를 Head, 마지막 노드를 Tail 이라고 부름Array vs Linked List구분ArrayLinked List메모리연속적비연속적인덱스 접근O(1)O(n)중간 삽입/삭제O(n)O(1)*크기 변경어려움쉬움캐시 친화성좋음나쁨 핵심 차이Array는 접근이 빠름Linked List는 삽입/삭제가 유리기본 연산1. 탐색(Search)Head부터 시작..

Data Structure & Algorithm 2025. 12. 20. 20:06

위상 정렬이란?위상 정렬(Topological Sort) 이란,방향 그래프(Directed Graph)에서 모든 간선의 방향을 거스르지 않도록 정점을 나열하는 정렬 방식이다.조금 더 쉽게 말하면,"선행 조건이 있는 작업들을, 그 순서를 지키면서 나열하는 방법" 이다.왜 필요한가?현실 세계와 소프트웨어에는 의존성(dependency) 이 매우 많다.대표적인 예과목 수강 순서 (선수 과목)프로젝트 빌드 순서 (컴파일 의존성)작업 스케줄링패키지 설치 순서Spring Bean 생성 순서이 모든 문제의 본질은 같다."무엇을 먼저 해야 하는가?"이 질문에 대한 알고리즘적 해답이 바로 위상 정렬이다.사용 가능한 그래프 조건위상 정렬은 아무 그래프에서나 사용할 수 없다.반드시 만족해야 할 조건방향 그래프(Directe..

Data Structure & Algorithm 2025. 12. 15. 04:05

동적 프로그래밍이란?문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘문제 풀이 순서문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색(Brute-Force Search) 접근을 시도한다.근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 것 같다.이럴 때, 모든 경우를 빠르게 탐색하는 방법으로 동적 프로그래밍 접근을 시도한다.동적 프로그래밍 접근 순서풀고 싶은 가짜 문제 정의가짜 문제를 풀면 진짜 문제를 풀 수 있는가?초기값은 어떻게 되는가?점화식 구해내기진짜 문제 정답 출력하기예제피보나치 수열가짜 문제 정의D[i] : i 번째 까지 피보나치 수열의 합.진짜 문제를 풀 수 있는가?피보나치 수열 A[1...N]에..

Data Structure & Algorithm 2023. 8. 27. 14:43

탐욕 알고리즘이란? 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법니다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법니다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차 : 현재 상태에서의 최적의 해담을 선택한다. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한..

Data Structure & Algorithm 2023. 5. 22. 22:45

백트래킹 알고리즘이란? 백트래킹 알고리즘은 모든 가능한 경로를 탐색하는 데 사용되는 알고리즘입니다. 다만, 이때 모든 가능성을 탐색한다는 것은 그 경로가 해결책으로 이어질 가능성이 있을 때만 해당 경로를 따라가는 것을 의미합니다. 만약 그 경로가 해결책ㅇ로 이어질 가능성이 없다면 그 즉시 해당 경로는 버림(pruning)되며 다른 경로를 탐색합니다. 백트래킹은 주로 결정 문제에서 사용되며, 이러한 문제는 해결책이 존재하는가? 또는 모든 해결책을 찾을 수 있는가?와 같은 질문에 대답하는 데 사용됩니다. 백트래킹 알고리즘의 작동 방식 백트래킹 알고리즘은 깊이 우선 탐색(DFS)와 비슷한 방식으로 작동합니다. DFS와 마찬가지로 백트래킹도 트리 또는 그래프의 모든 경로를 탐색하지만, 백트래킹은 어떤 경로가 해..

Data Structure & Algorithm 2023. 5. 21. 22:00

버블 정렬, 삽입 정렬, 선택 정렬은 단순한 알고리즘들이지만 정렬하는데 시간이 많이 든다는 커다란 단점이 있다. 즉 자료가 많을때 이들 정렬 방법들을 부적절하고 보다 빠른 정렬 알고리즘이 필요하다. 이번에는 좀 더 빠른 정렬 방법중 하나인 합병 정렬(merge sort)에 대해 살펴보겠다. 합병 정렬? 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 이 정렬 방법은 분할 정복(divide and conquer) 기법에 바탕을 두고 있는데, 분할 정복 기법이란 하나의 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 방법을 말한다. 분할 정복 기법은 대개 순환 호출..

Data Structure & Algorithm 2019. 8. 25. 01:28