YANGORITHM

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 부분수열은 연속적인 부분수열을 의미하는 것이 아니었다. 1, 2, 3, 4의 수열이 있으면 (1, 4), (1, 3, 4) 같이 떨어져 있어도 부분수열이 된다. 이것 때문에 헷갈린 문제다. 배열 각각의 원소를 포함하거나 포함하지 않거나의 2가지 경우로 배열의 모든 인덱스를 탐색하면 된다. 길이가 최대 20이므로 최대 2^20번의 경우가 나온다. 재귀 ..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 풀이 어떤 수를 제곱수들로 표현을 할 때 , 무조건 큰 수의 의 제곱수들로만 나타내는 것은 답이 아니다. 예를 들어 43 = 25..

문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 풀이 동전의 종류가 n개이고 구하고 싶은 가치가 k 일때 f(n, k)를 n번째 동전부터 사용하여 k를 나타내는 최소의 동전 수 로 한다. 이런 식으로 f(n+1, k)... 를 불러서 문제를 해결 할 수 있다. 동전의 수를 N 이라하고 각 동전의 가치를 coin[i]로 하면 면 다음과 같은 점화식을 구할 수 있다. 동전의 범위는 0부터 N-1까..

문제 https://www.acmicpc.net/problem/1935 1935번: 후위표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다) www.acmicpc.net 풀이 후위표기식으로 된 식을 계산하는 문제이다. 1. 피연산자를 만나면 스택에 push한다. 2. 연산자를 만나면 스택에 있는 두 ..

문제 https://www.acmicpc.net/problem/1918 1918번: 후위표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. www.acmicpc.net 풀이 중위 표기식을 후위 표기식으로 바꾸는 문제이다. 스택을 이용하는 대표적인 문제이다. 식에 존재하는 연산자는 + - * / 인데 * / 가 + - 보다 우선순위가 높다. 그리고 같은 우선순위라면 먼저 나오는게 더 우선순위가 높게 된다. 이 점을 이용하여 알..

문제 https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 문제 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 점수가 된다. 배열이 주어졌을 때, 최대의 점수를 갖는 부분배열을 골라내는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N이 주어진다. 다음 줄에는 A[1], …, A[N]을 나타내는 정수들 www.acmicpc.net 풀이 이유 : 가운데를 걸치는 부분배열에서 최대값을 구할 때 시간초과가 났다. 최대 부분 배열을 고르는 알고리즘은 분할 정복..

문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 풀이 길이가 N인 수를 만드는 개수를 구하는 문제이다. 사용할 수 있는 숫자는 00이랑 1이다. 즉 전에 만들었던 숫자에 00이나 ..

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 www.acmicpc.net 풀이 구멍이 비어 있는 경우 그 구멍을 사용한다. 모든 구멍을 사용 중이면 꽃혀 있는 것들 중에서 가장 나중에 사용하는 것을 ..

문제 https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 숫자 야구를 푸는 알고리즘은 크게 2가지가 있다. 1. 배열에 숫자들을 넣고 조건과 비교해서 조건과 맞지 않는 숫자들을 제거 2. 123부터 시작해서 조건과 맞는 숫자 후보들을 증가 배열에 숫자를 넣을 경우 0이 들어가거나 중복되는 수가 들어가는 것은 빼야한다. 배열에 숫자..

문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 www.acmicpc.net 풀이 A와 B 사이에 거리를 구하는 문제이다. 그래프 탐색인 bfs를 이용해서 A에서 B까지 거리를 구하면 된다. 만약 가는 경로가..