본문 바로가기

반응형

PS

(321)
[BOJ] 백준 11286 절댓값 힙 (Swift) 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소 힙과 최대 힙 2개를 사용해서 풀이할 수 있는 문제입니다. x가 양수라면 최소 힙에 넣어주고, x가 음수라면 최대 힙에 넣어줍시다. 그렇다면 최소 힙과 최대 힙에 절대값이 작은 수가 루트 노드에 위치할 것입니다. pop을 해줄 때, 최소 힙과 최대 힙이 둘다 비어있다면, 0을 출력하고 최소 힙만 비어있다면 최대 힙에서 pop, 최대 힙만 비어있다면 최소 힙에서..
[BOJ] 백준 1927 최소 힙 (Swift) 문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제 그대로 최소 힙을 사용해 풀이할 수 있는 문제입니다. Swift에서는 힙 자료구조를 지원하지 않기 때문에 직접 구현해주어야 합니다. 참고용으로 힙을 구현한 포스팅을 올려놓았습니다. https://dev-mandos.tistory.com/244 [자료구조] Heap에 대해 알아보고 구현해보기 (Swift) Heap이란? Heap은 트리를 사용하고, 트리 중 에서도..
[BOJ] 백준 11279 최대 힙 (Swift) 문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제 그대로 최대 힙을 사용해 풀이할 수 있는 문제입니다. Swift에서는 힙 자료구조를 지원하지 않기 때문에 직접 구현해주어야 합니다. 최대 힙을 구현하기만 하면 되는 문제.. 입니다. 참고용으로 힙을 구현한 포스팅을 올려놓았습니다. https://dev-mandos.tistory.com/244 [자료구조] Heap에 대해 알아보고 구현해보기 (Swift) He..
[BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 (Swift) 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 https://dev-mandos.tistory.com/217 [BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift) 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30,..
[BOJ] 백준 2110 공유기 설치 (Swift) 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리의 최대 값을 구해야 합니다. 이분 탐색을 떠올릴 수 있습니다. 이분 탐색을 하기위해 집의 좌표를 오름차순으로 정렬해줍시다. 거리에 주목을 하고, 1부터 집의 최대 거리 차이를 탐색하면서 공유기를 몇개 설치할 수 있는지 확인해봅시다. 공유기는 C개 만큼 설..
[BOJ] 백준 2805 나무 자르기 (Swift) 문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 조건을 만족하는 최대 값을 구하기 때문에 매개변수 탐색이라고 할 수 있습니다. 높이를 x로 설정한다면, 가져갈 수 있는 나무는 나무가 x보다 길다면 나무길이 - x 일 것이고 x보다 작다면 0일 것입니다. 따라서 max(나무 길이 - x, 0)으로 나타낼 수 있습니다. 가져갈 수 있는 나무가 m 이상이 된다면, 최대 높이를 구하기 위해 높이를 올려..
[BOJ] 백준 1654 랜선 자르기 (Swift) 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 조건을 만족하는 최대 값을 구하기 때문에 매개변수 탐색이라고 할 수 있습니다. 랜선들을 x로 나눈 몫의 합이 랜선을 만들 수 있는 갯수입니다. 이 몫의 합이 n보다 크거나 같다면, 조건을 만족하게 됩니다. 이것을 함수로 작성을 해주었고, start 값을 1로 end 값을 랜선의 최대 길이로 설정하여, 조건을 만족하는 최대길이를 찾아줍시다. 조건을 만족한다면,..
[BOJ] 백준 1920 수 찾기 (Swift) 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 Set 자료형에 넣어준 뒤, contains 메서드를 사용해 존재하는지 아닌지 확인해주면 되는 문제입니다. 소스코드 후기 여러가지 풀이방법이 있겠지만, 단순히 존재하는지 아닌지만 확인하기 때문에 Set 자료형을 사용하였습니다.

반응형