Coding Test

1991 - 트리 순회https://www.acmicpc.net/problem/1991 문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)입력첫째 줄: 이진 트리의 노드의 개수 N (1 둘째 줄부터 N개의 줄: 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어짐노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드/ 자식 노드..

1644 - 소수의 연속합https://www.acmicpc.net/problem/1644문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다ex. 3 : 3 (한 가지)/ 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) / 53 : 5+7+11+13+17 = 53 (두 가지)But, 연속된 소수의 합으로 나타낼 수 X 자연수: 20 : 7+13 -> 7과 13이 연속 X한 소수는 반드시 한 번의 덧셈에 사용될 수 있음 -> 3+5+5+7과 같은 표현 적합 X입력: 자연수 N (1 출력: 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수풀이에라토스테네스의 체소수가 아닌 수(합성수) 지워나가면서 소수만 남기는 방식=> 주어진 숫자 N까지 모든 소수 빠르..

7662 - 이중 우선순위 큐https://www.acmicpc.net/problem/7662문제이중 우선순위 큐(dual priority queue): 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조/ 차이점: 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은/낮은 데이터 중 하나 삭제데이터 삽입/삭제(우선순위 높은/낮은 것 삭제) 연산입력첫째 줄: 입력 데이터의 수를 나타내는 정수 T각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수 나타내는 정수 k (k k줄에는 연산을 나타내는 문자('D', 'I')와 정수 n 주어짐I n: 정수 n을 Q에 삽입/ D -1: Q에서 최솟값 삭제/ D 1: Q에서 최댓값 삭제최댓값(최솟값)을 삭제하는 연산에서 최..

2161 - 카드 1https://www.acmicpc.net/problem/2161문제각각의 카드는 차례로 1부터 N까지 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 순서대로 카드가 놓여 있음제일 위에 있는 카드 버림 -> 그 다음, 제일 위에 있는 카드를 제일 아래 있는 카드 밑으로 옮김ex. N = 4/ 제일 위에서부터 1 2 3 4 순서1 버림 -> 2 3 4 / 2 아래로 -> 3 4 2 / 3 버림 -> 4 2 / 4 아래로 -> 2 4 / 2 버림 -> 4=> N이 주어졌을 때, 제일 마지막에 남게 되는 카드?입력: 정수 N (1 출력: 버리게 되는 카드들 순서대로 출력코드import java.io.*;import java.util.*;// 카드1public cla..

2276 - 암기왕https://www.acmicpc.net/problem/2776문제연종이 하루 동안 본 정수들을 수첩1에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종이에게 M개의 질문을 던졌다. 연종이가 봤다고 주장하는 수들을 수첩2에 적어 놓았다.=> 수첩2에 적혀있는 순서대로, 각각의 수에 대하여 수첩1에 있으면 1/ 없으면 0 출력입력첫째 줄: 테스트케이스 개수 T 수첩 1에 적어 놓은 정수의 개수 N (1 수첩 1에 적혀 있는 정수들이 입력으로 들어옴수첩 2에 적어 놓은 정수의 개수 M (1 수첩 2에 적어 있는 정수들이 입력으로 들어옴출력수첩 2에 적혀있는 M개의 숫자 순서대로 수첩 1에 있으면 1/ 없으면 0 출력풀이이진 탐색리스트 정렬되어 있을 때 시간..

2293 - 동전 1https://www.acmicpc.net/problem/2293문제n가지 종류의 동전/ 각각의 동전이 나타내는 가치는 다름동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶음각각의 동전은 몇 개라도 사용할 수 있음사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우입력첫째 줄: n (1 n개의 줄에는 각각의 동전의 가치가 주어짐 (자연수) (출력: 경우의 수 (풀이이전 결과 이용해서 다음 결과 구해야 함=> 작은 문제의 해를 저장하면서 큰 문제 해결: DP `dp[i]`: i원을 만드는 경우의 수`dp[0] = 1`: 0원을 만드는 경우는 아무 동전도 사용 X => 1가지`dp[j] += dp[j - i]`: 현재 금액 j를 만드는 방법은, j - i원 만든 다음..