https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 요약 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오. 문제 해..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 요약 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀 있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 문제 해결 아이디어 간단하게 이진 탐색으로 풀었는데 속도가 많이 나왔다. 속도를 줄일 수 있는 아이디어를 얻어야 할듯... 완성된 코드 package week3; import java.io.Buf..
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 요약 N개의 정수가 들어 있는 배열이 입력된다. 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 문제 해결 아이디어 배열의 크기가 크지 않으므로 모든 순서를 다 조합해서 최댓값을 찾는다. 후보의 순서가 중요하기 때문에 순열으로 뽑는다. 완성된 코드 package week3; import java.io.Bu..
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 요약 길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 1번 칸이 있는 위치는 "올리는 위치", N번 칸이 있는 위치는 "내리는 위치"이다. 컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올리는 위치에만 올릴 수 있고, 내리는 위치에 도달하면 그 즉시 내린다. 로봇을 올리는 위치에 올리거나 어떤 칸으로 이동하면 내구도는 1만큼 감소한다...
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 요약 입력으로 N과 N*N 배열에 들어가는 능력치가 주어진다. N/2명씩 스타트 팀, 링크 팀을 만들어서 팀에 속한 팀원끼리 만나면 발휘되는 능력치를 더하고, 두 팀의 능력치가 최소가 되는 값을 출력한다. 문제 해결 아이디어 당연히 처음에는 nCn/2의 문제라고 생각했다. 하지만 순열 조합 부분집합을 재귀로 구하는 문제의 쟁점은 가지치기! 즉 어떻게 최소한으로 돌릴 것인가를 생각해 봐야 한다. 생각해 보니 만약 ..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 요약 상담원은 오늘부터 N+1째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 매일매일 상담을 잡아 놓았지만 상담마다 완료하는 데 걸리는 기간과 받을 수 있는 금액이 다르다. 1일에 하는 상담이 3일 걸린다면, 4일부터 또 다른 상담이 가능하다. 이런 경우에 N일 동안 상담원이 얻을 수 있는 최대 수익은? 문제 해결 아이디어 먼저 입력받은 상담을 선택하느냐, 하지 않느냐 두 가지의 선택지가 있는 것이라고 생각하고 부분집합으로 풀겠다는 아이디어를 떠올렸다. 하지만 단순 부분집합은 아니고, 상담마다..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 요약 한 쌍의 괄호 기호로 된 "()" 문자열을 VPS라고 부른다. 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES와 NO로 나타낸다. 문제 해결 아이디어 stack을 이용한다. stack이 비어있으면 무조건 넣고, 비어있지 않을 때에는 stack.peek(), 즉 가장 최근에 들어간 괄호가 현재 괄호와 같은지 확인 후 같으면 넣고,..
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 요약 재귀적인 패턴으로 별을 찍어 보자. 입력되는 N은 3의 거듭제곱이고, 출력되는 패턴은 공백으로 채워진 가운데의 (N/3)*(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 문제 해결 아이디어 크게 보면 계속해서 3*3의 반복을 돌면 된다. 그러면서 가운데는 비워주고, 가운데가 아니라면 계속해서 옆으로 밑으로 보내서 N==1이 되는 순간 별을 찍을 ..
