백준 링크 https://www.acmicpc.net/problem/10868 풀이 세그먼트 트리를 이용해 쿼리마다 범위 내의 최솟값을 구한다 세그먼트 트리 : https://www.acmicpc.net/blog/view/9 노드마다 노드 번호, 구간, 구간 내의 최솟값을 나타내며 실제로 tree배열에는 각 구간의 최솟값을 저장한다 init() : 재귀로 1번 노드부터 하위 노드로 이동하면서 리프노드에 도달 시 범위가 실제 값을 나타내므로 값 저장 올라오면서 자식 노드 2개의 최솟값을 부모에 저장 => 모든 범위의 최솟값을 저장한다 query(node, start, end, a, b): 각 노드의 구간을 start, end가 나타내며 a, b는 최솟값을 찾고자 하는 범위이다 현재 노드의 구간과 a,b구간..

백준 링크 https://www.acmicpc.net/problem/1766 풀이 우선관계가 주어진 문제는 위상정렬을 이용한다 위상정렬: BFS와 비슷하지만 in-degree(현재 노드로 올 수 있는 간선의 개수)를 저장하면서 0일때만 방문 낮은 번호의 문제부터 풀어야 하므로 -를 붙여 최소힙을 만든다 코드 #include using namespace std; int n,m; vector prob[32005]; int ind[32005], check[32005]; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int a,b; for(int i=0;i> a >>b; prob..

백준 링크 https://www.acmicpc.net/problem/1916 풀이 우선순위 큐(힙)을 사용한 다익스트라를 이용해 O(ElogV)로 풀 수 있었다 다익스트라: Dist[i] : 시작부터 i까지의 최단거리 Check[i] : I 방문했으면 true 1. Check[i] = false 인 I 중 dist 가장 작은 노드 선택(노드 V) => 우선 순위큐로 시간 단축 2. V와 연결된 모든 간선(from, to, cost) 검사, dist[to] > dist[from]+cost 이면 dist[to] 갱신 3. 1,2 반복 참고https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%..

백준 링크 https://www.acmicpc.net/problem/2294 풀이 DP문제이다 d[i] : i원을 만드는 최소 동전 개수 각 동전을 입력받을때마다 (현재 동전) n >> k; for (int i = 0; i > a[i]; for (int j = a[i]; j

백준 링크 https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc www.acmicpc.net 풀이 기본적인 스택문제이다 스택이 비어있지 않고, top이 'C'이며 현재 문자가 ')'이면 pop 그외에는 push 마지막에 스..