여름 언덕에서 배운 것

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 📚 문제 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다. 예제 입력 1 예제 출력 1 9 0 12345678 1 2 0 0 0..

📌 우선순위 큐란? FIFO 형식의 큐와 달리 들어오는 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐를 구현하는 방법 배열로 구현 연결리스트로 구현 힙(Heap)을 이용 1) 배열 및 연결리스트 배열이나 연결리스트를 이용해서 우선 순위 큐를 구현하는 경우 간단하게 구현이 가능하다는 장점이 있다. 하지만 배열의 경우에는 여러가지 단점이 존재한다. 데이터 삽입 및 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야하는 연산을 계속해야 한다. 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다. 2) 힙 배열의 shift 연산, 연결리스트의 삭제 및 삽입 하는 경우 순회하는 시간복잡도에 비해 힙을 통한 삽입 삭제는 부모와 자식 간에만 비교 하기 ..

📚 문제 못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로 이어지게 됩니다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다. 예제 입력 예제 출력 10 12 4 4 📝 문제 해결 이 문제는 가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …]와 같이 끊임없이 존재한다. 이때 못생긴 수에 2, 3 혹은 5를 곱한 수 또한 ‘못생긴 수’에..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📚 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 떄, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1..