http://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net # 조건 위 그림은 크기가 5인 정수 삼각형 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하여라 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능하다. 삼각형의 크기는 1 이상 500이하 # 접근 방법 DP를 이용하여 각 수에 누적합을 구해주고 가장 큰 수를 출력해주면 된다. 입력을 층마다 받기 때문에 2차원 리스트를 사용한다 ..

http://www.acmicpc.net/problem/1918 # 조건 수식은 일반적으로 중위 표기법, 전위 표기법, 후위 표기법으로 나타낼 수 있다. 이 문제에서는 후위 표기법으로 나타내는데 연산자가 피연산자 뒤에 위치하는 방법 예를 들어 a+b c를 후위 표기식으로 바꾸면 abc +가 된다. 바꾸는 방법 주어진 중위 표기식을 연산자의 우선 순위에 따라 괄호로 묶어준다. 그런 다음 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다. # 접근 방법 문제에 나와있는 방식을 스택을 이용해서 구현해주면 된다. 입력받은 표기식에서 토큰을 읽는다. 토큰이 피연산자이면 토큰 출력 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 ..

http://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net # 조건 이진 검색 트리는 아래와 같은 조건을 만족하는 이진 트리 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽) 후위 순회 (왼쪽-오른쪽-루트) 아래 이진 검색 트리의 전위 순회 결과 50 30 24 5 28 45 98..

http://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net # 조건 N개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스 A번째 도시에서 B번째 도시까지 가는데 드는 버스의 최소비용을 출력하라 # 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진..

최단 경로를 구하는 알고리즘에는 다익스트라 (dijkstra algorithm) 벨만-포드 (Bellman-Ford algorithm) 플로이드 워셜 ( 아직 공부 x ) 이 존재한다. 다익스트라 참고 - 2022.09.23 - [ALGORITHM/알고리즘 알아보기] - [알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘은 그리디(greedy)를 기반으로 우선순위 큐를 사용하여 최단 경로를 사용하는데 그리디가 기반이기 때문에 간선의 가중치가 음수 인 것이 존재하면 안 된다. 위와 같은 경로에서 A->D로 이동하는 최소 비용을 고려할 때, 다익스트라 알고리즘의 경우 근시안적 관점을 유지하기 때문에, 가중치가 감소하는 것을 고려하지 않고 B에서 D로 가는 경로를 선택하게 되기 때문이다. 벨만 - 포드 알고리..

http://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net # 조건 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램 작성 모든 간선의 가중치는 10 이하이다. # 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(..

http://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net # 조건 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 입력 트리가 입력으로 주어진다. 첫 줄 -> 트리 정점 개수 V ( 2

백준 1149_RGB 거리 조건 집이 N개가 있고, 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각 집을 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하라. 1번 집의 색은 2번 집의 색과 같지 않아야한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i (2

http://www.acmicpc.net/problem/3425 3425번: 고스택 각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 www.acmicpc.net # 조건 창영이는 스택을 조금 변형해서 고스택을 만듦 숫자만 저장 가능하며 아래 10가지 연산을 수행할 수 있다 편의상 스택의 가장 위에 저장된 수 첫 번째 NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다. SWP: 첫 번째 ..