PS/자료구조 & 알고리즘
그래프(Graph) 그래프는 정점들과, 정점들을 연결하는 간선들로 구성된 자료 구조이다. 최단 경로 찾기, 네트워크 구성, 검색 엔진, 스케줄링 등 다양한 분야의 컴퓨터 과학에서 응용되어 사용되고 있다. 그래프 탐색 그래프 구조에서 정점(Vertex)과 간선(Edge)을 따라 이동하는 과정이다. 그래프 탐색는 주로 시작 정점에서 출발하여 인접한 정점을 탐색하는 방법을 사용하며, 그 종류는 다음과 같다.깊이 우선 탐색(DFS, Depth-First Search): 가능한 한 깊숙한 곳까지 이동한 후 다시 돌아와 다음 가능한 경로를 탐색한다.너비 우선 탐색(BFS, Breadth-First Search): 시작 정점에서 가까운 정점부터 차례로 방문하며 넓게 탐색한다. 시작 정점이 1일 때 두 가지 방법의 ..
그래프(Graph) 그래프는 정점들과, 정점들을 연결하는 간선들로 구성된 자료 구조이다. 최단 경로 찾기, 네트워크 구성, 검색 엔진, 스케줄링 등 다양한 분야의 컴퓨터 과학에서 응용되어 사용되고 있다. 그래프 이론 그래프의 정의 정점(Vertex)와 간선(Edge)의 집합표현 : G = (V, E) (V=정점의 집합, E=간선의 집합) 그래프의 종류 방향그래프 : 간선에 방향이 있는 그래프표현 : (a, b) = 정점 a와 b를 연결하는 간선무방향그래프 : 간선에 방향이 없는 그래프표현 : = 정점 a와 b를 연결하는 간선 가중치 그래프 : 간선에 가중치가 부여된 경우 그래프 용어차수(Degree) : 정점에 인접한 간선의 수방향그래프 : 진입차수와 진출차수로 구분경로(Path) : 시작 정..
그리디와 우선순위 큐 그리디 알고리즘은 매번의 선택의 순간에서의 최선인 답을 도출하면서 결과를 도출하는 방법이다. 매 순간에 최선의 해답을 판단해야 할 때, 우선순위 큐가 유용하게 사용될 수 있다.우선순위 큐는 그리디에서 매 순간의 최적의 선택이 이전의 결정에 의해 영향을 받을 경우, 그 선택의 후보군들을 저장해 둘 수단으로서 유용하게 사용될 수 있다.PS문제에서 우선순위 큐와 그리디와 함께 사용되는 경우가 매우 많다. 이러한 방법들을 사용한 문제들을 풀어보도록 하자. 그리디 알고리즘의 개념https://sjh9708.tistory.com/216 [알고리즘/JAVA] 그리디 (Greedy) : 개념 (동전, 단어 수학, 허프만 코딩)그리디 알고리즘 (Greedy) 나는 미래를 위해서 지금 어떤 행동을 ..
이진 탐색 (Binary Search)정렬된 배열 또는 리스트를 반으로 나누어 가면서 원하는 값을 찾는 알고리즘이다. 배열이나 리스트가 정렬되어 있어야만 사용할 수 있다.이진 탐색은 시간 복잡도가 O(log n)으로 매우 빠르다. 따라서 큰 데이터 집합에서도 빠르게 원하는 값을 찾을 수 있다 이진 탐색의 과정탐색 범위 설정: 탐색 범위를 설정한다. 일반적으로는 전체 배열이나 리스트의 처음과 끝을 사용한다.중간 값 찾기: 설정된 범위에서 중간에 위치한 값을 찾는다.중간 값과 비교: 중간 값과 Key(찾고자 하는 값)의 크기를 비교한다.탐색 범위 업데이트: 중간 값과 Key의 크기에 따라 탐색 범위를 업데이트한다. 중간 값이 Key값보다 작을 경우 : 중간 값의 오른쪽 부분을 탐색 범위로 재설정한다.중간..
분할 정복법 (Divide and conquer) 큰 규모의 문제를 풀기 위해 하위 문제로 나누어 풀이하고 이들의 해답을 결합하여 최종 해답을 얻는 방법이다.문제를 가장 작은 단위의 문제로 분할한 후, 해당 문제들을 결합하여 부분 해답을 도출, 또 다시 부분 해답을 결합하는 과정을 통해서 최종적으로 큰 규모의 문제를 풀이한다. 분할 정복법의 과정1. 분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.2. 정복(Conquer): 나눈 작은 문제를 각각 해결한다.3. 통합(Combine): (필요하다면) 해결된 해답을 모은다. 분할 정복법의 조건 1. 문제의 분할이 쉽게 가능해야 한다.주어진 문제를 작은 부분 문제들로 나눌 수 있어야 한다. 또한 문제를 분할하는 과정이 너무 복잡..
그리디 알고리즘 (Greedy) 나는 미래를 위해서 지금 어떤 행동을 해야 가장 효율적일지 모른다. 하지만 눈앞에 보이는 상황에서 현재의 최선을 다하려고 한다.그리고 이것은 그리디 알고리즘을 설명하는 말이다. 그리디 알고리즘은 매번의 선택의 순간에서의 최선인 답을 도출하면서 결과를 도출하는 방법이다.해당 방법은 매 순간에서는 최선일 수 있고 적당히 좋은 값을 찾는 것이 목표이지, 전체적으로 보았을 때에는 항상 최적이라는 보장이 없다. 그리디의 최적 조건 그리디가 항상 최적해를 보장하지 못한다고 하였다. 따라서 그리디를 이용하여 최적해를 구해야 하는 경우에 따져봐야 하는 조건이 있다. 1. 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 미쳐서는 안 된다.2. 최적 부분 구조: 작은 부분 문..
동적 계획법 최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다. Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다. 동적 계획법(다이나믹 프로그래밍, DP)에 대한 자세한 설명은 아래의 포스팅을 살펴보자.https://s..
동적 계획법 최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다. Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다. 동적 계획법(다이나믹 프로그래밍, DP)에 대한 자세한 설명은 아래의 포스팅을 살펴보자.https://s..
누적합 (Prefix Sum) 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적 합을 계산하여 이를 배열에 저장해 두는 것이다. 이후에 특정 구간의 합을 구할 때는 해당 구간의 끝 지점까지의 누적 합에서 시작 지점까지의 누적 합을 빼는 것이다. 해당 알고리즘은 배열 또는 리스트의 요소가 고정되어 있을 때 구간 합을 반복적으로 계산해야 하는 경우 유용하게 사용될 수 있다. 1차원 배열의 누적합 (백준 11659) 다음 문제를 보면, 1차원 배열이 주어지며, 그 이후로 주어지는 시작 인덱스와 마지막 인덱스의 쌍에 대해서 그 구간의 합을 구하는 문제이다.진짜 단순하게 각 입력에 대해서 일일이 반복문을 돌려..
