YANGORITHM

문제 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/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 bfs 탐색을 이용하여 (1,1) 에서 (N, M) 까지의 거리를 알아내면 된다. bfs 탐색을 할 때는 큐에 집어넣을 때 방문했다고 설정해야한다. 만약 큐에서 꺼낼 때 방문했다고 설정하면 중복해서 큐에 들어가는 좌표가 생길 수 있다(그래서 메모리 초과가 일어났다). bfs 탐색의 level이 바뀔 때 마다 result 값을 증가시킨다. 코드 123456789101112131415161718192021222324252..

문제 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까지 거리를 구하면 된다. 만약 가는 경로가..

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 풀이 N번째 자리에 올 수 있는 수는 0 또는 1이다. ○ ○ ○ .... ☆ ● 에서 만약 ●에 0이 온다면 ☆에는 0 또는 1이 ..

문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아 www.acmicpc.net 풀이 상하좌우로 탐색하며 음식물이 있는지 없는지 검사하여 최대값을 찾으면 된다. 1. 2차원 배열을 돌면서 음식물이 있는 곳(1)..