http://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # 조건 수빈이는 동생과 숨바꼭질하고 있다. 현재 점 N에 있고, 동생은 점 K에 있다. 수빈이는 걷거나 순간이동을 하는데 걷는다면 1초 후에 X-1 또는 X+1로 이동 순간이동을 하면 0초 후에 2 * X로 이동 수빈이와 동생의 위치가 주어질 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하여라 # 접근 방법 및 Solution 현재 점 N..

http://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net # 조건 동생 N명과 숨바꼭질 수빈이는 현재 점 S에 있고, 동생은 A1, A2 .. An 수빈이는 걸어서 이동을 할 수 있는데, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X+D나 X-D로 이동 가능 수빈이의 위치가 동생이 있는 위치와 같다면 동생을 찾았다고 한다. 모든 동생을 찾기 위해 D의 값을 정하는데 가능한 D의 최댓값을 구하여라. # 접근 방법 동생들의 ..

최대 공약수 숫자 a,b가 주어졌을 때, 공통되는 약수 중 최대 값을 의미한다. 구하는 방법 a,b 각각의 약수를 구해서 공통되는 약수 중 가장 큰 값을 찾는 방법 찾지 않아도 되는 약수들까지 구해야하기 때문에 비효율적이다. 유클리드 호제법 숫자 a,b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 것을 의미한다. 따라서, a를 b로 계속 나누어서 b에 a로 나눈 나머지를 대입시켜서 b가 0이 될 때까지 반복을 하면, 남는 a의 값이 바로 최대 공약수이다. def gcd(a, b): while b > 0: a, b = b, a % b return a 최소 공배수 서로 다른 수 a,b의 배수 중에서 공통되는 배수 중 가장 작은 값을 의미 최소 공배수는 a,b의 곱..

http://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net # 조건 트리는 사이클이 없는 무방향 그래프 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있다. 이 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하면 트리에 존재하는..

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로 가는 경로를 선택하게 되기 때문이다. 벨만 - 포드 알고리..