🔗문제 보러가기 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 👨‍💻풀이 과정 세그먼트 트리(Segment Tree) 첫 입문 문제로 풀었습니다. 첫 시도고, 조금 변형된 문제인지라 결국 다른 분들의 풀이를 참고하여 풀었지만, 세그먼트 트리라는 개념과 어느정도 친숙해진 그런 계기가 아니었나 싶습니다. 백준 문제를 풀면서 느낀 거지만, 다양한 알고리즘 문제들을 접해볼 수 있다는 게 되게 좋은 것 같습니다. 아직 접해보고 풀어봐야 할 문제들이 많지만 하나씩 천천히 해봐야죠...

🔗문제 보러가기 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 👨‍💻풀이 과정 위상 정렬과 다이나믹 프로그래밍을 통해 풀었습니다. 처음에는 DFS로 풀 수 있을 것 같단 생각에 도전하려고 했는데, 중복되는 계산이 너무 많아 시간 초과가 날 것 같단 생각이 들어 그 풀이는 포기했습니다. 아무튼, 제가 어떻게 풀었는지 천천히 설명해 드리도록 하겠습니다. 1. 간선 정보 및 진입 차수 설정 하위 부품에서 상위 부품으로 간선이 가리키도록 방향을 설정하였고, 필요한 부품 개수 정보도 같이 ..

🔗문제 보러가기 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🧑‍💻풀이 과정 기본적인 틀은 다익스트라 알고리즘인데, 최단 경로에 해당하는 각 도시들 번호를 어떻게 저장할 지가 문제였습니다. 분기가 이루어지는 각 경로마다 자기가 거쳐 온 도시 정보를 가지고 있을까 생각했다가, 메모리가 너무 많이 들 것은 물론 복사 비용이 만만치 않을 것 같아 포기했습니다. 그래서 결국 다른 분의 풀이를 참고했는데, 배열을 통해 이전 노드로 가는 길을 추적하는 참신한 방법을 사용하여 푸셔서 놀랐..

🔗문제 보러가기 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 🧑‍💻풀이 과정 위상 정렬을 사용해 풀 수 있는 문제인데, 사이클(Cycle) 감지 조건을 하나 더 넣어야 하는 문제입니다. 순서를 정하는 게 불가능한 경우는 각 가수들의 순서에 사이클이 있는 경우가 됩니다. 이는 모든 노드를 돌기 전에 큐(Queue)가 비었을 경우로 탐지 할 수 있습니다. ✏️소스 코드 및 결과 #include #include #include using namespace std; #define FAST_IO..

🔗문제 보러가기 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🧑‍💻풀이 과정 동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다. 진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다. *constructionTimes[i] : i 번째 건물의 건설 시간 *answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간 answers[o..

🔗문제 보러가기 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 🧑‍💻풀이 과정 위상 정렬(Topological Sort)에 대해 공부한 후, 풀어보려고 골랐던 문제 중 하나입니다. 위상 정렬 알고리즘을 그대로 적용하되, 쉬운 문제부터 풀어야 하니 우선순위 큐(Priority Queue)를 대신 사용해주면 끝인 문제입니다. 이 외에는 더 이상 설명할 내용이 진짜로 없기에, 아래에 코드를 첨부하도록 하겠습니다. ✏️소스 코드 및 결과 #include #include #include..