C++156 [백준] 2250번 - 트리의 높이와 너비 (C++) 문제 및 풀이 문제) 백준 - 트리 - 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 중위 선회를 통해 해방 레벨에서의 최소 idx와 최대 idx를 memo 합니다. 그 후, 1부터 N까지 너비의 최댓값을 찾아 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/2250_%ED%8A%B8%EB%A6%A.. 2022. 3. 18. [백준] 2075번 - N번째 큰 수 (C++) 문제 및 풀이 문제) 백준 - 우선수위 큐 - N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net N * N개의 모든 수를 저장하고 정렬해서 N번째 큰 수를 구하기에는 메모리 제한이 12MB이기에 불가능합니다. 대부분의 정렬 문제는 우선순위 큐로 해결할 수 있습니다. 우선순위 큐를 최소 힙으로 사용하여 문제를 해결했습니다. Input을 최소 힙에 push 하면서 최소 힙이 N개가 되게 유지합니다. 그 후, top을 출력하면 해답을 구할 수 있습니다. C+.. 2022. 3. 17. [백준] 9935번 - 문자열 폭발 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net ans에 문자열을 더하면서 폭발 문자열의 끝과 확인하여 만약 같을 경우 폭발 문자열 전체를 확인하여 같을 경우 pop 합니다. C++ 소스코드) 2022. 3. 17. [백준] 1613번 - 역사 (C++) 문제 및 풀이 문제) 백준 - 플로이드 와샬 - 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 전/후 관계가 있는 역사 사건들이 주어질 때, 임의의 두 사건의 전/후 관계를 구하는 문제였습니다. 사건의 개수가 최대 400이므로 플루이드 와샬 알고리즘(O(N^3))으로 해결할 수 있습니다. >, < 관계를 1, -1로 저장하여 같은 전/후 관계끼리만 비교가 가능하므로 update 합니다. C++ 소스코드) 2022. 3. 16. [백준] 1963번 - 소수 경로 (C++) 문제 및 풀이 문제) 백준 - BFS - 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 주어진 첫 소수의 한 자리를 바꾸어 두 번째 소수를 만들 수 있는 최소 변환 수를 구하는 문제였습니다. 에라토스테네스의 체를 활용하여 10000 이하에 대하여 소수 판별(isPrime)을 진행합니다. 그 후 주어진 수의 첫자리부터 4번째 자리까지 변환하면서 소수이면서 방문하지 않은 수에 대하여 queue에 push 하여 BFS를 진행합니다. C++ 소스 코드) Full.. 2022. 3. 16. [백준] 14620번 - 꽃길 (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 꽃길 https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 백트래킹으로 꽃을 심어가면서 최소 비용을 구합니다. C++ 소스코드) 2022. 3. 13. [백준] 11568번 - 민균이의 계략 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 민균이의 계략 https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net 11053번 - 가장 긴 증가하는 부분 수열 문제와 같은 문제입니다. 현재 idx에서 만들 수 있는 가장 긴 부분 수열의 길이를 memoization하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/11568_%EB%AF%BC%EA%B.. 2022. 3. 11. [백준] 10159번 - 저울 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net N이 최대 100이므로 플루이드 와샬(O(N^3))로 충분히 해결할 수 있습니다. 대소 관계가 중요하므로 그 관계에 따라 1 또는 -1로 표현합니다. 만약 같은 t, i, j에 대하여 (i, t)와 (t, j)의 관계가 같으면 (i, j)의 관계로 표현합니다. C++ 소스코드) 2022. 3. 11. [백준] 21920번 - 서로소 평균 (C++) 문제 및 풀이 문제) 백준 - 수학 - 서로소 평균 https://www.acmicpc.net/problem/21920 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $A_{i}$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 서로소를 만족하는 수들의 평균을 구하는 문제였습니다. 유클리드 호제법을 통해 서로소를 판별합니다. C++ 소스코드) 2022. 3. 11. 이전 1 2 3 4 ··· 18 다음 반응형
