본문 바로가기

백준

(329)

[BOJ] 백준 11660 구간 합 구하기 5 (Swift) 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 2차원 배열의 구간 합을 구하는 문제입니다. 구간 합을 한 번 구해볼까요? 다음 수는 1 + 2 + 2 + 3 으로 8을 채워줘야 합니다. 채울 수의 위, 왼쪽을 보면 3으로 구간합이 이미 채워져 있습니다. 이 두 수의 3은 1 + 2, 1 + 2 로 채워져 있는데, 1이 중복되고 있습니다. 따라서 중복된 1을 빼주어야 합니다. 3 + 3 - ..

[BOJ] 백준 10986 나머지 합 (Swift) 문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 누적 합을 응용하는 문제입니다. 하나씩 전부 확인해서 구한다면 $O(n^2)$의 시간복잡도가 들 것입니다. 먼저 누적 합을 구해줍시다. 구한 누적합 배열을 array라고 칭하겠습니다. 그렇다면 (i, j) 구간의 합이 m으로 나누어 떨어지는지 확인하는 과정은 $(array[j] - array[i - 1]) mod m == 0$ 인 경우 겠..

[BOJ] 백준 16139 인간-컴퓨터 상호작용 (Swift) 문제 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 풀이 누적 합을 사용하여 풀이할 수 있습니다. 저는 문자의 갯수가 나오는 누적합을 구하기 위해 Dictionary를 Array로 감싸주었습니다. "mandos" 라는 문자열이 있다면, array[0] = ["m": 1] array[1] = ["m": 1, "a": 1] 과 같은 형태로 만들어 주었습니다. 그 이후 누적 합을 구하는 것 처럼, ..

[BOJ] 백준 2559 수열 (Swift) 문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이 누적 합을 사용해서 풀이할 수 있습니다. 구간이 고정되어 있기 때문에, 슬라이딩 윈도우를 사용해서도 풀이할 수 있습니다. 구간의 크기가 k이고 누적 합을 사용하면, 누적합 배열의 array[i + k] - array[i]로 구간의 온도의 합을 구할 수 있습니다. 슬라이딩 윈도우를 사용하면, 초기의 합은 array[0] ~ array[k - 1] 합이 될 것이고, 이 합에서 ..

[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] 백준 12865 평범한 배낭 (Swift) 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 잘 알려진 Knapsack 문제입니다. 다이나믹 프로그래밍 기법을 사용하여 풀이할 수 있습니다. 물건을 쪼갤 수 만 있다면.. 그리디 알고리즘으로도 풀리겠지만 그럴 수 없으므로 다이나믹 프로그래밍으로 풀어야 합니다. 먼저, 정의를 하자면 $f(n, k)$ = n번째 물건을 배낭에 넣으려고 하고, 배낭이 버틸 수 있는 무게..

[BOJ] 백준 9251 LCS (Swift) 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 이 문제는 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 라는 잘 알려진 알고리즘을 사용하여 풀 수 있습니다. 다른 훌륭하신 분들이 설명을 기깔나게 해준 블로그들이 많아서.. 풀이는 생략하겠습니다.. 소스코드 후기 잘 알려진 알고리즘이고, 저번에 한 번 공부를 했어서 복습을 하는 겸 풀었는데 잘 기억이 안났던..

[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만 확인해도 교차하는..

이전 1 ··· 14 15 16 17 18 19 20 ··· 42 다음

티스토리툴바