프로그래밍30 [Simulation] 백준 14719: 빗물 14719번: 빗물 (acmicpc.net) 처음에는 각 column 간의 차이를 위주로 접근하다가, 위에서부터 한 row씩 훑고 내려오면서 연산하는 방식으로 접근을 달리했다. 맨 위 row 부터 순회하면서, 만일 값이 1인 칸을 이미 만난 상태라면 이후 0인 칸을 만날 때마다 값을 더해준다. 만일 다시 값이 1인 칸을 만나면, 해당 값을 정답에 더해주고 0으로 초기화한다. 양 옆이 뚫려 있다고 생각해야 하므로, 다음 row로 내려갈 때 값을 0으로 초기화한다. 이 때 1인 칸을 만났는지 여부를 확인하는 flag(여기서는 isFill)을 false로 초기화 해 준다.#include #include using namespace std;int main(){ ios_base::sync_with_stdio.. 2024. 6. 8. [BruteForce] 백준 14888: 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 재귀함수 호출을 통한 완전탐색 문제이다. input A_1, A_2, ... , A_n 이 주어졌을 때, 다음과 같은 재귀호출을 통해 답을 구한다. #include #include #include using namespace std;int maxValue = -1000000000;int minValue = 1000000000;void recursion(int currentValue, int numIdx, vector&numbers, vector&operators){ if(numIdx>=numbers.size()) { maxValue = currentValue>maxValue?currentValue:maxValue; .. 2024. 6. 2. [Algorithm] 정렬 알고리즘 - selectionSort(선택 정렬) void selectionSort(vector &A){ for(int i=0;iA[j]){ minIdx = j; } } swap(i, minIdx, A); }}각각의 i번째 element에 대해, [i+1, N) 번째 element와 비교하여, 그 중 가장 작은 element와 i번째 element를 교체한다. 시간복잡도는 O(N^2)이다. 주어진 배열(혹은 vector나 list)의 element들이 무엇이든 간에 오직 해당 배열의 크기 N만이 시간 복잡도에 관여하므로, 최선/최악의 경우 모두 시간복잡도가 같다. 2024. 5. 10. [수학] 백준 1629: 곱셈 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 그냥 (A^B)%C를 연산하면 풀 수 없다. 일단 범위를 벗어난다. 그래서 다음과 같은 modulo 연산의 성질을 이용해야 한다. (X*Y)%Z = ((X%Z)*(Y%Z))%Z 위 성질을 통해 long long int의 범위 내에서 계속 결과값이 형성되도록 관리해 주어야 한다. 이를 반복문을 통해 B번 순회하면서 하고 있으면 O(N)의 시간복잡도에 걸리기 때문에 다음과 같은 지수함수의 성질을 응용한다. X^Y = X^(Y/2)*X^(Y/2) 이를 통해 시간 복잡도를 O(logN) 수준.. 2024. 4. 4. 이전 1 2 3 4 ··· 8 다음
