PS

[Silver IV] 큐 - 10845 문제 링크 성능 요약 메모리: 69376 KB, 시간: 28 ms 분류 자료 구조, 큐 제출 일자 2023년 12월 31일 16:50:53 문제 설명 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐..

[Silver II] 창고 다각형 - 2304 문제 링크 성능 요약 메모리: 69108 KB, 시간: 12 ms 분류 브루트포스 알고리즘, 자료 구조, 스택 제출 일자 2023년 12월 27일 18:19:12 문제 설명 N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 비가 올 때 물이 고이지 않도록 지붕의 ..

[Silver II] 화학식량 - 2257 문제 링크 성능 요약 메모리: 69104 KB, 시간: 8 ms 분류 자료 구조, 스택, 문자열 제출 일자 2023년 12월 25일 23:17:40 문제 설명 우리가 널리 사용하는 H2O(물), CH3COOH(아세트산)과 같은 화학식은 알파벳과 숫자, 그리고 괄호로 구성된다. 먼저 알파벳은 원자를 나타내는 것으로 H는 수소(Hydrogen), C는 탄소(Carbon), O는 산소(Oxygen) 원자를 뜻한다. 또한 원자를 나타내는 알파벳 뒤에 따르는 숫자는 그 원자가 몇 개 포함되어 있는지를 뜻한다. 따라서 COOHHH 분자는 CO2H3로 나타낼 수 있다. 이 문제에서, 숫자는 항상 2 이상 9 이하로만 입력으로 주어진다. 따라서 CO23과 같이 숫자가 두자리인..

[Silver III] 천재 수학자 성필 - 15815 문제 링크 성능 요약 메모리: 69104 KB, 시간: 8 ms 분류 자료 구조, 스택 제출 일자 2023년 12월 28일 09:12:55 문제 설명 평행 세계의 성필은 숫자와 연산자를 만든 당대 최고의 수학자이다. 그리고 놀랍게도 이 숫자와 연산자는 현재 우리가 사용하는 것과 같다. 하지만 수식은 연산자가 피연산자 가운데 위치하는 우리와는 다르게 연산자가 피연산자 뒤에 위치한다고 한다. 우리 세계의 식을 성필의 식으로 바꾸는 방법을 간단히 설명하자면 이렇다. 우선 주어진 식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다. 예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그다..

[Silver III] 1로 만들기 - 1463 문제 링크 성능 요약 메모리: 87324 KB, 시간: 56 ms 분류 다이나믹 프로그래밍 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 연산의 최솟값을 구하는 문제이기 때문에 DP와 관련이 있을 것이라 예상하였고, 몇 가지의 수를 나열하여 규칙을 찾고자 하였..

[Gold V] 탑 - 2493 문제 링크 성능 요약 메모리: 106148 KB, 시간: 380 ms 분류 자료 구조, 스택 문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에..

[Silver III] 피보나치 - 9711 문제 링크 성능 요약 메모리: 79720 KB, 시간: 988 ms 분류 다이나믹 프로그래밍, 수학 문제 설명 피보나치 수열은 아래와 같이 표현된다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다. P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 입력 첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 P와 Q가 주어진다. 출력 각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다. x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다. 풀이 i) 첫 시도에서는 P의 최대..

[Gold V] 비밀번호 만들기 - 17218 문제 링크 성능 요약 메모리: 69100 KB, 시간: 8 ms 분류 다이나믹 프로그래밍, 문자열 문제 설명 최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자. 입력 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는..