본문 바로가기

알고리즘171

다익스트라 알고리즘 완벽 가이드: 2차원 행렬부터 우선순위 큐까지, 자바 구현으로 배우는 최단 경로 찾기 1.다익스트라?가중치(weight)가 부여된 방향 없는 혹은 방향 있는 그래프에서, 특정 시작 정점(start)으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘에츠허르 다익스트라가 고안하였다.특징간선의 가중치가 음수가 아닐 때만 사용 가능우선순위 큐(Priority Queue)를 활용해 효율적으로 구현2. 그래프 기본 개념정점(Vertex): 그래프를 구성하는 노드간선(Edge): 정점과 정점을 연결하는 선, 가중치(weight)를 가짐경로(Path): 한 정점에서 다른 정점으로 이동하는 과정최단 경로(Shortest Path): 여러 경로 중 가중치 합이 가장 작은 경로graph LR A((A)) --2--> B((B)) A((A)) --5--> C((C)) A((A)) --7-.. 2025. 4. 26.
세그먼트 트리에 대해 알아보자: 해결하는 문제와 데이터 구조, 작동 방식, 사용 사례, 자바 코드 개요세그먼트 트리는 효율적인 데이터 관리와 빠른 쿼리를 가능하게 해주는 데이터 구조이다. 특히, 누적 합 계산이나 특정 구간의 최대값, 최소값을 빠르게 처리해야 하는 경우 유용하게 쓰인다. 💡 이 글에서는 세그먼트 트리가 해결하는 문제와 그 이유, 작동 원리와 활용 사례에 대해서 살펴본다.문제 상황 🧐다음과 같은 배열 {1, 3, 5, 7, 9}를 생각해보자. 이에 대해서 다음과 같은 연산을 해야 하는 상황이다.구간 합 구하기예를 들어, 배열의 2번째부터 4번째 숫자의 합을 계산하려면 3 + 5 + 7 = 15이다.값 업데이트배열의 특정 값을 바꿔야 한다면 어떻게 될까요? 예를 들어, 5를 6으로 변경한다면 배열은 {1, 3, 6, 7, 9}로 변한다.이 배열에 대해, 직관적으로 구간 합을 구하거나 .. 2024. 12. 21.
백준 5639 이진 검색 트리 (JAVA 자바 풀이) https://www.acmicpc.net/problem/12873 📌 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 .. 2024. 11. 23.
요세푸스 문제의 마지막 남은 사람을 수학적 귀납법으로 도출한 점화식으로 찾아보자 이 글의 작성 배경요세푸스 문제를 다양한 방법으로 풀어보면서 배열, 큐, 링크드 리스트, 세그먼트 트리 등 여러 알고리즘적 접근을 시도해 보았다. 각 방법에서 최적화를 시도했지만, 시간 복잡도는 여전히 \( O(n^2) \) 정도였고, 세그먼트 트리를 사용해도  \( O(n \log n) \) 이 최대였다. 조금 더 최적화할 방법이 뭔가 있을 것 같은데... 고민하다가 문제를 가상의 순환 구조로 해석하면 어떤 규칙이나 패턴이 존재하지 않을까 하는 의문이 생겼다. 그러던 중, 점화식 풀이법을 알게 되며 이 방식에 주목하게 되었다. 점화식을 활용한 풀이법은 흥미로웠지만, 문제는... 어려웠다. 😭 특히, 이 점화식을 어떻게 유도할 수 있는지, 그 논리적 근거와 직관이 어떻게 도출되는지, 그리고 실제로 이 .. 2024. 10. 13.
[백준] 기념품 (자바 풀이) https://www.acmicpc.net/problem/12873  📌 문제백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다. 하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다. 따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다. 게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다. 다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다. 이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다. 게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사.. 2024. 10. 12.

티스토리툴바