본문 바로가기
반응형

백준58

백준 10866. 덱 🅰 백준 10866. 덱 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ✏️ 문제 풀이 덱을 풀기 위한 가장 기본적인 문제이다. 덱에대한 개념이 궁금하다면 ? [Deque] queue(큐)와 stack(스택)을 둘 다 사용할 수 있는 deque(덱) * Deque란? - 덱은 Double-Ended Queue의 줄임말로 큐의 양쪽에 데이터를 넣고 뺼 수 있는 형태의 자료구조이다. 하나의 자료구조에 queue와 stack을 사용할 수 있다 생각하면 된다. 덱(Deque)은 어떤 쪽으로 thsd-.. 2021. 11. 5.
백준 2824. 최대공약수 🅰 백준 2824. 최대공약수 2824번: 최대공약수 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 www.acmicpc.net ✏️ 문제 풀이 이 문제는 아래처럼 조건이 매우 까다롭다. 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,0.. 2021. 11. 5.
백준 1991. 트리순회 [트리의 정석 문제] 🅰 백준 1991. 트리순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ✏️ 문제 풀이 전위, 후위, 중위순회를 출력하는 문제이다. ✏️ 소스코드 package tree; import java.util.*; import java.io.*; public class Main_실버1_1991_트리순회 { private static class Node { char data; Node left = null; Node right = null; Node() { } Node(char data) { this... 2021. 10. 22.
백준 2056. 작업 🅰 백준 2056. 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net ✏️ 문제 풀이 순서가 주어지므로 위상정렬의 개념을 이용하여서 풀었다. 일단 위상정렬이랑 비슷하지만 선행관계가 없는 작업들은 동시에 수행되기 때문에 이 부분을 생각해내는데 시간이 조금 걸렸다. pq에 저장되는 정점들은 comparable을 이용하여 수행시간이 작은 순으로 정렬을 시켜서 하나씩 뽑아낸다. pq에는 들어오는 간선이 없는 정점부터 저장을 해서 탐색을 시작한다. cur = pq.poll() 한 정점이 걸리는 시간을 an.. 2021. 9. 29.
백준 1766. 문제집 🅰 백준 1766. 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ✏️ 문제 풀이 백준 2252 줄 세우기 문제랑 99% 동일한 문제이다. 다른점이란 가능하면 쉬운 문제를 먼저 풀어야 한다는 조건이 하나 더 생겼을 뿐이다. 이를 해결하기 위해서는 queue대신 PriorityQueue를 사용하여 들어오는 정점들을 오름차순으로 저장해서 순서대로 탐색하면 된다는 점이다. 아래에는 2252 줄 세우기 문제랑 해설이 동일하다. 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것.. 2021. 9. 28.
백준 2252. 줄 세우기 🅰 백준 2252. 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ✏️ 문제 풀이 위상정렬의 개념을 이용해서 풀면 쉽게 풀리는 문제이다. 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것으로, 어떤 일을 하는 순서를 찾는 알고리즘이다. 중요한 것은 큐에 넣을 때 연결된 간선이 하나밖에 없는 정점만 넣어줘야 한다는 것이다. 먼저 인접리스트, 큐, 연결된 간선 수를 체크해줄 check배열을 선언하였다. 먼저 그래프를 생성하기 위해 인접리스트를 생성해주고, .. 2021. 9. 28.
백준 5557. 1학년 🅰 백준 5557. 1학년 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net ✏️ 문제 풀이 2차원 배열을 이용해서 각 수식을 순서대로 +, - 해서 dp[][] index에 저장한다. 행은 각 수식의 수만큼 만들고 계산되는 수식은 0~20 사이에 있기 때문에 열은 0~20으로 생성한다. dp[N+1][21] 계산해서 나오는 값들은 index로 표현할 수 있기 때문에 각 숫자마다 +연산을 한 값이 20보다 작거나 같으면 dp[i][j+number[i]] += dp[i-1][j], -연산을 한 값이 0보다.. 2021. 9. 27.
백준 1495. 기타리스트 🅰 백준 1495. 기타리스트 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net ✏️ 문제 풀이 기타리스트 문제에서는 행을 각 곡의 개수, 열을 0~M(최대 볼륨)으로 설정한 다음 dp를 수행한다 점화식은 D[i][j] = D[i+1][j+V[i+1]] = 1, D[i+1][j-V[i+1]] = 1이 될 수 있다. i+1에 데이터를 저장할 때 0~M사이에 있으면 dp에 저장을 하면서 마지막 곡까지 반복수행한다. 마지막 곡의 볼륨조절이 끝난 후 그 행에 있는 볼륨 중 최대값을.. 2021. 9. 27.
백준 12920. 평범한 배낭 2 🅰 백준 12920. 평범한 배낭 2 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net ✏️ 문제 풀이 평범한 배낭문제와 비슷하지만 다른점은 "한 물건을 두개 이상 챙기는 것도 가능하다." 이 부분이다. 처음 이 부분을 해결하기 위해 물건이 2개이상 있는 경우에는 for문을 이용하여 2개,3개,4개...k개 만큼을 넣었을 때의 가치를 비교하여 최적의 가치를 찾아서 제출했다 하지만 6%때 시간초과가 떠서 최악의 경우를 생각해보니 가방의 무게가 10,000이고 100개의 물품.. 2021. 9. 27.

티스토리툴바