본문 바로가기
반응형

BOJ

 (328)
[BOJ] 백준 11047 동전 0 (Swift) 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 그리디 알고리즘을 사용하여 풀이할 수 있습니다. K가 0이 될 때 까지, K를 가장 큰 동전부터 나눈 몫을 더해주면 동전의 최소 개수를 구할 수 있습니다. 문제의 조건 중 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라는 조건이 있기 때문에, 그리디 알고리즘이 성립하게 됩..
[BOJ] 백준 25682 체스판 다시 칠하기 2 (Swift) 문제 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 2차원 배열의 누적 합을 사용하여 풀이할 수 있습니다. M * N 보드를 올바른 체스판과 비교하여 다르다면 1로, 같다면 0으로 2차원 배열을 만들어 줍시다. 그 이후 만들어준 2차원 배열의 누적 합을 구하면, 올바른 체스판과 다른 것의 갯수를 알 수 있습니다. 2차원 배열의 K * K 범위 안의 누적 합 중 가장 작은 값을 출력해주면 됩니다. 소스코드 후기 2차원 배열의 누적합 알고리즘을 이런 방식으로 활용할 수 있다는 것을..
[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번째 물건을 배낭에 넣으려고 하고, 배낭이 버틸 수 있는 무게..
반응형

티스토리툴바