https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net [풀이] - 자료구조 유형의 문제입니다. - 처음에는 이중 우선순위 큐라는 문제를 읽고 우선순위 큐를 두개선언하는 방식을 생각했습니다. - 하나는 정방향, 하나는 역방향으로 선언하는 방식으로 말이죠. - 그런데, 이렇게 구현을 하려다보니 문제가 발생합니다. - 바로, 연산을 모두 마치고 나면, 두개의 큐에 남아있는 데이터가 다릅니다. - 그래서, TreeMap 자료구조를 이용해서 풀겠습니다.(..
https://www.acmicpc.net/problem/1172 1172번: 선인장 Automorphisms 첫째 줄에 그래프 G의 정점의 개수 N과 간선의 개수 M이 주어진다. N은 200보다 작거나 같은 자연수이고, M은 0보다 크거나 같은 정수이다. 다음 M개의 줄에 간선의 정보가 주어진다. 간선의 정보 www.acmicpc.net [풀이] - 다이나믹 프로그래밍 유형의 문제입니다. - 먼저, 숫자의 범위가 int, long, BigInteger 어디에 속하는지 유의해야 합니다. - int 범위 : -2,147,483,648 ~ 2,147,483,647 - long 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 - BigInteger :..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] - BFS 유형의 문제입니다. - 사다리 혹은 뱀이 있는 곳에 대한 값을 배열에 저장합니다. - 이렇게 값을 받은 배열은 BFS 메소드 내부에서 다음 위치로 이동할 때 사용하게 됩니다. - BFS 메소드 내부에서 유의할 점은 100이 넘지 않아야 한다는 것입니다. 그렇기에, 100을 넘지 않는다는 조건문을 추가해서 Queue에 추가해줍니다. ..
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net [풀이] 배열 혹은 비트마스크를 이용한 문제입니다. 처음에는 Java의 Set 자료구조를 이용했는데 시간초과가 발생했습니다. (M이 1
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net [풀이] - 분할 정복 및 재귀 유형의 문제입니다. - 문제의 풀이 과정은 다음 프로세스입니다. 1. 해당 배열이 1 혹은 0으로만 채워져 있는지 확인합니다. 2. 만약, 하나의 숫자로만 채워져 있을 경우에는 재귀를 그만하고 종료합니다. 3. 만약, 하나의 숫자로만 채워져 있지 않을 경우에는 재귀를 반복합니다. - 한 변의 길이는 2의 n제곱승입니다. 따라서, n을 2로..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net [풀이] - 다이나믹 프로그래밍 유형의 문제입니다. - 피보나치 수열의 식을 기억하시나요? 피보나치 수열의 식처럼 비슷한 점화식을 구현할 수 있습니다.(저도 규칙을 찾는게 쉽지는 않았습니다.) - dp[n] = dp[n-2] + dp[n-3]의 식을 구현하면 됩니다. - 최대 n의 값은 100이므로 dp 배열의 크기는 101로 선언하여 값을 할당했습니다. - 테스트 케이스 횟수만큼 dp 배열에서 각 값..
