문제 풀이/백준 (BOJ)

[백준/BOJ] 11505번: 구간 곱 구하기 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명 문제 풀이: https://www.acmicpc.net/problem/11505 풀이이 문제는 주어진 숫자 배열의 값들을 변경한 후에, 변경된 값이 반영된 배열의 부분곱을 구하는 문제입니다. 이번 문제는 세그먼트 트리( segment tree )를 사용하는 전형적인 문제입니다.세그먼트 트리는 주어진 데이터에 대한 빈번한 변경에도, 원하는 연산 값을 구하는데, 일정한 수행 능력을 보여주는 자료구조입니다.세그먼트 트리의 값은 수행하고자 하는 연산에 따라 달라지는데, 이 문제에선 원하는 연산이 부분곱을 구하는 것입니다. 세그먼트 트리에 관한 내용은 여기에서 볼 수 있습니다. [C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법세그먼트 트리( segment tree ) 소개세그먼..

2024. 8. 13.

문제 풀이/백준 (BOJ)

[백준/BOJ] 10868번: 최솟값 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/10868 풀이이 문제는 입력된 숫자 배열에서 주어진 구간의 최소 값을 구하는 문제입니다. 이번 문제는 세그먼트 트리( segment )를 사용하는 전형적인 문제입니다.세그먼트 트리는 주어진 데이터에 대한 빈번한 변경에도, 원하는 연산 값을 구하는데, 일정한 수행 능력을 보여주는 자료구조입니다.세그먼트 트리의 값은 수행하고자 하는 연산에 따라 달라지는데, 이 문제에선 원하는 연산이 부분 최소 값을 구하는 것입니다. 세그먼트 트리에 관한 내용은 여기에서 볼 수 있습니다. [C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법세그먼트 트리( segment tree ) 소개세그먼트 트리는 주어진 대량의 데이터에..

2024. 8. 13.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2042번: 구간 합 구하기 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2042 풀이이 문제는 주어진 숫자 배열의 값들을 변경한 후에, 변경된 값이 반영된 배열의 부분합을 구하는 문제입니다. 이번 문제는 세그먼트 트리( segment tree )를 사용하는 전형적인 문제입니다.세그먼트 트리는 주어진 데이터에 대한 빈번한 변경에도, 원하는 연산 값을 구하는데, 일정한 수행 능력을 보여주는 자료구조입니다.세그먼트 트리의 값은 수행하고자 하는 연산에 따라 달라지는데, 이 문제에선 원하는 연산이 부분합을 구하는 것입니다. 세그먼트 트리에 관한 내용은 여기에서 볼 수 있습니다. [C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법세그먼트 트리( segment tree ) 소개세그먼트..

2024. 8. 13.

알고리즘

[C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법

세그먼트 트리( segment tree ) 소개세그먼트 트리는 주어진 대량의 데이터에 대하여, 빈번한 변경을 거쳤을 때도, 일정한 연산 수행 능력을 보여주는 자료구조라고 할 수 있습니다. 이 자료구조의 기본적인 아이디어는 이미 계산되어 있는 결과의 일부분이 변경되었다고 해서, 모든 계산 과정을 다시 거칠 필요가 없다는 생각입니다.예를 들어, 일단 100개의 숫자들의 합을 계산한 경우,50번째 이전의 데이터들이 변경되었다고 해서, 50번째부터 100번째까지의 계산도 다시 수행할 필요가 없습니다. 이렇듯, 일부 조각의 부서지면, 그 부분만을 재계산함으로써, 이전과 같은 성능을 내는 자료구조가 세그먼트 트리입니다. 시간 복잡도이 자료구조는 일단 구성되면원소의 숫자가 N개 일 때,O( logN )의 수행 속도 ..

2024. 8. 13.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1854번: K번재 최단경로 찾기( 다익스트라 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1854 풀이이 문제는 1번 도시에서 다른 도시까지 갈 수 있는 경로에 걸리는 시간 중에서 k번째 시간을 출력하는 문제입니다. 여기서는 한 도시에서 다른 도시까지 가는 데 걸리는 시간이 양수이므로, 다익스트라( Dijkstra ) 알고리즘을 사용합니다.다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘은 그래프에 음수 가codingembers.tistory.com 그렇지만, 단..

2024. 8. 12.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11404번: 플로이드 ( 플로이드-워셜 알고리즘) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11404 풀이이 문제는 모든 도시에서 다른 도시에 도달하는 최단 거리를 출력하는 문제입니다.여기서는 플로이드-워셜( Floyd-warshall ) 알고리즘을 사용합니다. 다익스트라( Dijkstra ) 알고리즘이나 벨만-포드( Bellman-Ford ) 알고리즘이 한 도시에서 다른 도시까지의 최단 거리를 구하는 데 사용하는 알고리즘이라면, 플로이드-워셜 알고리즘은 모든 도시에서 다른 도시까지의 최단 거리를 한 번에 구하는 알고리즘입니다. 플로이드-워셜 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 플로이드-워셜 알고리즘플로이드-워셜( Floyd-Warshall ) 알고리즘 소개플로이드-워셜..

2024. 8. 12.

알고리즘

[C++] 최단 거리를 구하는 플로이드-워셜 알고리즘

플로이드-워셜( Floyd-Warshall ) 알고리즘 소개플로이드-워셜 알고리즘은 주어진 그래프에서 모든 정점 간에 최단 거리를 구하는 알고리즘입니다.이 알고리즘은 정점 간의 거리가 음수로 주어져도 최단 거리를 구할 수 있습니다. 시간 복잡도정점의 개수가 V일 때,이 알고리즘은 시간 복잡도는 $O(V^3)$입니다. 이 알고리즘 구현이 알고리즘의 아이디어는 A -> C로 가는 최단 거리는 A->B로 가는 최단 거리와 B->C로 가는 최단 거리의 합으로 만들어진다는 것입니다. 예를 들면, 위 그래프의 A에서 C까지의 최단 거리는 A에서 B까지의 최단거리와 B에서 C까지의 최단거리의 합인, 1 + 5 = 6이 됩니다. 이 아이디어를 구현하기 위해 플로이드-워셜 알고리즘은 인접 배열을 통해 그래프를 표현합니다..

2024. 8. 12.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11657번: 타임머신 ( 벨만-포트 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11657 풀이이 문제는 1번 도시에서 출발하여, 다른 도시까지 이동하는 데 걸리는 가장 빠른 시간을 출력하는 문제입니다. 이러한 문제를 푸는데 적용할 알고리즘으로 다익스트라( Dijkstra )와 벨만-포드( Bellman-Ford ) 알고리즘이 있습니다.그런데, 주의할 점은, 이동하는 데 걸리는 시간이 음수인 경우가 있다는 것입니다. 다익스트라 알고리즘의 경우 음수 입력 데이터에 따라 문제를 해결하지 못할 수도 있습니다.따라서, 벨만-포드 알고리즘을 사용합니다. 벨만-포드 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘벨만-포드( Bellma..

2024. 8. 10.

알고리즘

[C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘

벨만-포드( Bellman-Ford ) 알고리즘의 소개벨만-포드 알고리즘은 출발 정점으로부터, 도달이 가능한 모든 정점까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘의 장점은 음수의 가중치를 가진 순환 경로가 있는 경우, 그러한 순환 경로가 있다는 것을 판단할 수 있다는 것입니다. 같은 목표를 가진 다익스트라( Dijkstra ) 알고리즘은 이러한 경우, 잘못된 결과를 내고, 문제 해결에 실패합니다.다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다...

2024. 8. 10.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1753번: 최단 경로 ( 다익스트라 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1753 풀이이 문제는 출발 노드로부터 도달이 가능한 모든 노드들까지의 최단 거리를 구하는 문제입니다. 이 문제를 해결할 수 있는 알고리즘으로 다익스트라( Dijkstra )와 벨만-포드( Bellman-Ford) 알고리즘이 있습니다.그런데, 간선의 가중치가 양수인 경우, 다익스트라 알고리즘이 좀 더 빠릅니다. 다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘은 그래프에 음수..

2024. 8. 10.