백준46 [백준 1517번] 버블 소트 난이도: 플래티넘 V 문제 링크: https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 분할-정복 (divide & conquer) 문제입니다. n은 최대 50만이므로, 모든 원소에 대해 모든 다른 원소와 비교해 보는 식으로 하면 시간 초과가 납니다 (O(N^2)). 재귀 방식으로 배열을 구간별로 나누어 접근하도록 합니다. 나눈 구간에 대해 정렬하기 전 swap 횟수를 세고, 정렬되는 값을 별도의 배열에 기록한 후 (arr2).. 2021. 9. 17. [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. [백준 3687번] 성냥개비 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 제가 느끼기에 이 문제는 DP와 그리디를 이용하는 부분으로 나뉩니다. 그리디를 이용하는 부분은 최댓값을 구하는 부분으로, 상대적으로 더 쉽습니다. 성냥개비가 짝수개 있을 때는, 모두 1을 만들면 됩니다 (자릿수를 크게 함). 1을 만드는 데 성냥개비가 2개 소모되므로, 총 (성냥개비 개수 / 2)개의 1을 출력합니다. 성냥개비가 홀수개 있을 때는, 맨 앞자리에 7을 출력하.. 2021. 9. 9. [백준 11049번] 행렬 곱셈 순서 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 제가 자신없어 하는 편인 DP를 이용하는 문제입니다. 2차원 배열 dp[i][j]를 만드는데, 이때 dp[i][j]는 행렬 i에서 j까지 곱했을 때의 최소 곱연산 횟수라고 정의합니다. 맨 처음에는 배열 matrix에, matrix 1번부터 n번까지 각각의 row와 column의 길이를 입력받습니다 (저는 pair를 이용함(. 다음으로, 주어진 모든 m.. 2021. 9. 8. [백준 13422번] 도둑 난이도: 골드 IV 문제 링크: https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 시간 제한 1초인 문제입니다. 문제의 요구점을 간단히 짚고 넘어가자면 다음과 같습니다. 배열 (집)은 원형으로 이루어져 있으며, 총 n개 (n은 10만 이하의 자연수)로 이루어져 있다. m은 도둑이 한번에 털어야 하는 집의 갯수이며, 총 n개 이하의 자연수로 이루어져 있다. 또한, 도둑은 서로 인접한 집만 털 수 있다. 각 경우의 수에 대해, 도둑이 턴 m개의 집의 금액의.. 2021. 9. 7. [백준 5430번] AC 난이도: 골드 V 문제 링크: https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 각 테스트 케이스별로 입력은 다음과 같이 들어옵니다. RDD 4 [1,2,3,4] 즉 맨 첫줄과 세 번째 줄은 string 형식이고, 두 번째 줄은 int 형식이 됩니다. 이 문제를 해결하려면 두 가지 포인트를 신경써야 합니다. 1. 입력받은 string 형태의 수열을 실제 int형 배열로 변환하기 2. 시간 제한 문제 1의 경우, 예전에 제가 블로그에 올렸던 C++에서 문자열을 쉽게 자르는 방법이 있습니다 (링크). 문자.. 2021. 9. 6. 이전 1 2 3 4 5 6 7 8 다음
