프로그래밍/백준 복기28 [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. [수학] 백준 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. [자료구조] 백준 1655: 가운데를 말해요 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 발상의 전환이 필요했다. 솔직히 한 번에 풀지 못했고(테스트케이스는 맞았으나, 시간초과가 남) 다른 사람의 풀이를 구글링하고 난 다음에야 문제를 풀 수 있었다. 처음에는, 매 입력마다 list를 정렬하고, 그 가운데 값을 출력하는 간단한 문제로 생각했다. 그러나 이 경우는 매번 전체 리스트를 순회하며 정렬하기 때문에 비효율적이었다. 그래서 구글링을 통해 알게 된 발상이, input을 받는 자료.. 2024. 3. 3. 이전 1 2 3 4 ··· 7 다음
