YANGORITHM

문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 풀이 스택을 이용해서 폭발 문자열과 관련된 인덱스를 저장하고 erase 배열에는 폭발할 문자열의 인덱스를 체크한다. 문자열과 폭..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 풀이 n번째 줄까지 값을 더했을 때 최대값을 찾아야하는 문제이다. i번째 줄에서 선택할 수 있는 숫자는 i-1번째에 있는 숫자들 ..

문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 수열을 확인하기 위해 스택을 이용해서 해결하는 문제이다. 스택은 top에 값만 확인할 수 있는 성질을 이용하면 문제를 해결할 수 있다. 만약 스택에 현재 입력된 숫자가 없다면 스택의 top이 현재 입력된 숫자까지 되도록 수들을 push한다. push 순서는 오름차순이므로 순서대로 숫자를 넣어주면 된다. 만..

문제 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net 풀이 10의 배수들이 끝자리가 0이 된다. 10은 2x5로 이루어진다. 따라서 조합의 결과 값에서 2와 5의 개수를 구하면 된다. 2와 5의 각 개수 중 적은 값이 만들 수 있는 0의 수가 된다. nCm = n! / (m! * (n-m)!) 이므로 nCm을 한 이후에 2와 5의 개수를 구하면은 시간초과가 발생한다. 따라서 각각을 따로 구한다. 1. n!에서 2, 5의 개수 2. m!에서 2, 5의 개수 3. (n-m)!에서 2, 5의 개수 1번에서 2, 3번에 대해 각각 뺄셈을 진행한 후에 2..

문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모 www.acmicpc.net 풀이 에라토스테네스의 체를 이용해서 1000000 이하의 소수를 먼저 구한다. 에라토스테네스의 체를 이용하면 c 배열에 각 ..

문제 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 풀이 pair와 vector를 이용해서 입력 값을 저장한다. pair에 인덱스와 움직일 숫자를 넣어서 vector에 저장을 한다. 그 다음 부터는 vector에 맨 앞에 저장되어 있는 값을 출력하고 바꿔주면 된다. 움직일 숫자가 양수이면 vector의 앞에 있는 값을 뒤로 보내주고, 음수면 vector의 뒤에 있는 값을 앞에 넣어준다. 1. vector의 front 값의 인덱스를 출력 후 삭제 2. front 값의 움직일..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 풀이 그래프 상에서 최단경로를 찾는 문제이다. 간선의 가중치는 음수가 존재하지 않으므로 다익스트라 알고리즘을 이용하여 문제를 해결한다..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 최소 스패닝 트리의 가중치가 -2147483648보다 크거나 같고, 2147483647보다 작거나 같은 데 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 알고리즘은 크루스칼과 프림 알고리즘이 있다. 1. 프림 알고리즘은 정점 집합을 기준으로 트..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 풀이 트리에서 지름은 거리가 가장 먼 두 점 사이를 의미한다. 이를 구하기 위해 먼저 임의의 노드에서 가장 거리가 먼 노드를 구..

문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열 www.acmicpc.net 풀이 1. 1 보다 큰 양수는 2개를 곱했을 때 더한 것 보다 무조건 크다. 그러므로 1보다 큰 두 수는 묶어야 한다. 1은 다른 ..