[Gold V] 트리와 쿼리 - 15681 [문제 링크](https://www.acmicpc.net/problem/15681)🗝️알고리즘 분류트리의 탐색깊이 우선 탐색(DFS)💻문제 정의트리가 주어졌을 때, 쿼리에 대한 답변을 출력하는 문제이다. 트리는 가중치와 방향성이 없고, 루트는 있다. 쿼리는 정점 U를 루트로 하는 서브트리의 정점의 개수를 구하는 것이다. 💡접근 및 설계루트가 있는 트리를 설계한 후, 쿼리로 부터 오는 정점 U가 루트가 되는 서브트리의 정점을 개수를 구해야 한다. 일반적인 dfs로 접근하였고, 각 정점마다 정점이 루트일 때, 서브트리의 개수를 포함시키도록 하였다. ✏️알고리즘 풀이visited = [False for _ in range(N+1)] # 방문 체크 표시 및 서브트..

[Gold V] 용액 - 2467 [문제 링크](https://www.acmicpc.net/problem/2467)🗝️알고리즘 분류두 포인터이분 탐색💻문제 정의주어진 용액들 중에서, 두 용액을 섞었을 때 그 합이 0에 가깝도록 하는 두 용액을 찾아내는 프로그램을 만드는 문제이다. 💡접근 및 설계두 포인터와 이분 탐색을 활용하여 알고리즘을 설계하였다. 용액을 크기별로 정렬하여 가장 큰 용액과 가장 작은 용액의 합을 구한다. 이후 이 합을 기준으로 start와 end 값을 조절하여 0에 가깝게 하는 용액을 찾아간다. ✏️알고리즘 풀이start, end = 0, N-1answer = abs(liquid[start] + liquid[end]) # 두 용액의 합result = [liquid[start], l..

[Gold V] 다각형의 면적 - 2166[문제 링크](https://www.acmicpc.net/problem/2166)🗝️알고리즘 분류기하학다각형의 넓이신발끈 공식💻문제 정의2차원 평면 위에 다각형을 이루는 N개의 점이 있다. 다각형을 이루는 순서대로 N개의 점이 주어질 때, 다각형의 넓이를 구하는 문제이다. 💡접근 및 설계기하학에서 다각형의 넓이를 구할 때 사용하는 신발끈 공식을 이용하여 문제를 해결하였다.삼각형을 예시로 하였을 때 다음과 같은 공식이 성립한다는 것이 신발끈 공식이다. 🗒️전체 코드# 2166 다각형의 면적N = int(input())xy = []for _ in range(N): xy.append(list(map(int, input().split())))xy.append..

[Gold IV] 최단경로 - 1753 [문제 링크](https://www.acmicpc.net/problem/1753)🗝️알고리즘 분류최단경로다익스트라💻문제 정의단방향 그래프가 주어진다. 간선에 대한 정보와 간선의 가중치가 함께 주어진다. 시작 정점이 주어지고, 시작 정점에서 부터 모든 정점에 도달하기 까지의 최소 가중치를 각 정점별로 출력한다. 도달하지 못하는 정점은 INF를 출력한다. 💡접근 및 설계최단 경로 알고리즘에 걸맞게, 우리가 한 번씩은 들어본 다익스트라 알고리즘을 구현하도록 한다. 파이썬에서는 우선순위 큐를 이용하여 다익스트라를 구현할 수 있다. 우선순위 큐를 활용하기 위해 최소힙을 이용하였다. ✏️알고리즘 풀이graph = [[] for _ in range(V+1)] weight ..

[Gold V] 평범한 배낭 - 12865 [문제 링크](https://www.acmicpc.net/problem/12865)🗝️알고리즘 분류다이나믹 프로그래밍냅색 문제💻문제 정의가방에는 최대 K만큼의 짐을 실을 수 있다. 각 짐의 무게 W와 짐의 가치 V가 주어지고, 가치의 최댓값을 구하는 문제이다.💡접근 및 설계유명한 배낭 문제(Knapsack Problem)이다. 프로그래밍을 배운지 얼마 안되었을 때 접해본 개념이다. 기억을 더듬으며 문제를 해결해보았다. 다이나믹 프로그래밍인 만큼, 문제를 세분화 해서 보는것이 중요하다. 현재의 짐을 담았을 때, 다음 짐을 담을 수 있는지를 판별, 담을 수 있다면 가치 합을 저장한다. 🗒️전체 코드# 12865 평범한 배낭import sysinput = sy..

[Gold II] 후위 표기식 - 1918[문제 링크](https://www.acmicpc.net/problem/1918)🗝️알고리즘 분류자료구조스택💻문제 정의주어진 중위 표기식을 후위 표기식으로 바꾸어 출력하는 문제이다.이 수식의 피연산자는 알파벳 대문자로 이루어지며, 수식에서는 단 한번만 등장한다. 또한 연산자가 맨 앞에 오거나, 곱하기가 생략되는 등의 수식은 주어지지 않는다. 💡접근 및 설계중위 표기식을 후위 표기식으로 바꾸기 위해선 먼저 연산자의 우선 순위를 알아야 한다. 문제에선 (, ), *, /, +, - 6개의 연산자만을 활용한다. 이들 중에서 가장 우선순위가 높은 것은 괄호((, )) 그 다음 곱셈(*), 나눗셈(/), 마지막으로 더하기(+), 빼기(-) 이다. 후위 표기법에선, 우..