[BOJ] 백준 11659 구간 합 구하기 4 (Swift)
문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 이 문제는 누적 합을 구해서 쉽게 풀이할 수 있습니다. [5, 4, 3, 2, 1] 배열의 누적합을 구한다면 [5, 9, 12, 14, 15] 가 될 것입니다. 2 ~ 4번까지의 합은 4 + 3 + 2 로 9가 됩니다. 누적합 배열을 보시면 4번째 요소가 의미하는 것이 1 ~ 4까지의 합이고, 1번째 요소가 의미하는 것은 0 ~ 1까지의 합입니다. 4번째 요소 -..
[BOJ] 백준 2565 전깃줄 (Swift)
문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 교체하는지 어떻게 알 수 있을까요? (1, 5), (2, 4)를 보시면 교차하고 있는 형태입니다. (1, 3), (2, 4)은 어떨까요? 두 전깃줄이 교차하고 있지 않습니다. (a1, b1), (a2, b2) 일 때, a1 b2 인 경우 교차한다고 할 수 있습니다. 연결되어 있는 위치를 입력받은 후, a를 기준으로 오름차순으로 정렬해준다면 b만 확인해도 교차하는..
[BOJ] 백준 11054 가장 긴 바이토닉 부분 수열 (Swift)
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제는 가장 긴 증가하는 부분 수열 문제를 응용하는 문제입니다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 3..
[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift)
문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 수열 A = {10, 20, 10, 30, 20, 50} 경우에 가장 긴 증가하는 부분 수열을 찾아봅시다. 첫번째 요소인 10만 봤을 때, 자기 자신도 수열이기 때문에 길이는 1입니다. 두번째 요소에서 이전 요소들을 확인해봅시다. 10 보다 20이 크기 때문에 (10의 길이 + 1)이 증가하는 부분 수열의 길..
[BOJ] 백준 2156 포도주 시식 (Swift)
문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 계단 오르기 문제와 비슷한 문제였습니다. 하지만 계단 오르기와 다르게, 마지막 포도주를 꼭 먹어야 하지는 않습니다. [1, 99, 100, 2] 와 같은 경우 99와 100을 먹는게 가장 큰 값입니다. 마지막 2를 먹을 필요가 없습니다. [100, 99, 1, 2, 100, 1] 로 포도주가 나열되어 있다고 가정합시다. 첫번째 포도주 까지 있다면, 첫번째 포도주를 마셔야 무조건 가장 많이..
