반응형 Programming405 [C/C++] 백준 #2357 최솟값과 최댓값(세그먼트 트리) 세그먼트 트리를 구현해서 푸는 문제가 참 많습니다. 옛날에는 세그먼트 트리가 Platinum 등급에 있었는데, 이제는 모두 Gold 등급으로 떨어졌습니다. https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최소값과 최대값을 주어진 범위안에서 찾는 알고리즘은 모두 \(O(N)\) 입니다. 미리 테이블을 만들어서 하는 것도 어렵죠. 세그먼트 트리만이 올바른 방법이라고 볼 수는 없습니다. 데이터를 \(\sqrt{N.. 2023. 4. 27. [C/C++] 백준 #2352 반도체 설계(가장 긴 증가하는 부분수열) 가장 긴 증가하는 부분수열 문제는 백준 사이트에서 자주 접할 수 있는 문제입니다. 이 알고리즘을 잘 이해하면, 풀 수 있는 문제들이 많이 있습니다. 증가하는 부분수열 중 하나를 출력하라면 조금 골치가 아프겠지만, 현재 이 알고리즘을 이용해서 부분수열도 출력할 수 있습니다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 반도체에서 서로 라인이 겹치지 않도록 설계하는 것은 중요한 문제입니다. 실제로는 다층기판을 이용하기 때문에.. 2023. 4. 27. [C/C++] 백준 #2346 풍선 터뜨리기(데크 자료구조) #2346 풍선 터뜨리기 문제는 자료구조를 사용하면 좋습니다. 제 경우에는 데크 자료구조를 이용하여 문제를 풀었습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 데크 자료구조는, 큐와 스택 모두 사용하여도 성능이 좋습니다. 그래서 큐 대신에 많이 사용되는 편입니다. 구현은 데크를 이용하여 적절한 삭제만 해주시면 됩니다. 데크 자체가 앞과 뒤 연산에는 효율적이지만, 중간에 데이터를 넣는 작업이나 빼는 .. 2023. 4. 27. [C/C++] 백준 #2331 반복수열(구현) #2331 반복수열 문제는 단순하게 구현만하면 됩니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 이 문제에서 구현의 초점은 바로 자리수를 가져오는 것과 그것을 p제곱하는 것입니다. A란 숫자가 있으면, p값이 바뀌지 않는다면, 모든 자릿수를 p제곱한 후의 합은 항상 같은 숫자가 됩니다. 저는 개수를 세기 위해서 배열에 count를 하게 했습니다. 배열의 최대 개수는 9의 5제곱은 59049이므로 이것을 4개 더한 236196보다 크게 잡아주면 됩니다. 제가 구현한 소스입니다. //---------------------------.. 2023. 4. 26. [C/C++] 백준 #2316 도시 왕복하기 2(포드-폴커슨 알고리즘) 도시를 디니면서 어떤 조건을 만족하는 문제들은 조건에 따라서 푸는 방법들이 다양합니다. NP-Hard 문제인 세일즈맨 문제와 같이 특정 알고리즘이 없는 문제도 있지만, #2316 문제와 같이 문제를 변행해서 기존의 알고리즘을 적용할 수 있는 문제도 있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 이 문제는, 1번 도시에서 2번 도시로 이동을 하는데, 한번 방문했던 도시는 다시 방문하지 않고, 몇번 왔다갔.. 2023. 4. 25. [C/C++] 백준 #2312 수 복원하기(수학) 소인수 분해하는 것은 어렵지 않게 할 수는 있습니다. 물론 소수를 구해서 하면 더 좋겠지만, 소수를 별도로 구하지 않아도 소인수 분해를 할 수 있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 소인수 분해를 할 때에는 n의 숫자의 제곱근까지만 하면 됩니다. 예를 들어서 12를 소인수 분해하기 위해서는 2부터 시작합니다. 12의 제곱근은 3보다는 크고 4보다는 작겠죠. 즉, 3까지만 하면 됩니다. 하지만, 제 알고리즘은 그 전에 끝나게 됩니다. 12를 2로 계속 나누면, 2번 나눌 수 .. 2023. 4. 20. 이전 1 ··· 5 6 7 8 9 10 11 ··· 68 다음 728x90
