728x90 반응형 백준 알고리즘55 [백준 11659] 구간 합 구하기 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 특정 구간의 합을 구하는 문제이다. 리스트 li가 있을때 li[i]에 처음부터 인덱스 i까지의 값을 모두 더한 값을 저장한다. 이렇게 계속 누적 합을 구한다면 구간 합을 빠르게 구할 수 있다. 예를 들어 두 번째부터 다섯 번째까지 구간 합을 구한다면 처음부터 다섯 번째까지의 합에서 처음부터 첫 번째까지의 합을 빼면 된다. 위의 정의에 의하면 li[5] - li[1]가 된다... 2023. 2. 15. [백준 3053][파이썬] 택시 기하학 https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 이 문제는 원에 대한 새로운 정의를 내리고 그 넓이를 구하는 문제이다. 택시 기하학에 따른 원의 정의는 곧 마름모꼴이 된다. 이 부분만 파악하고 나면 이 문제는 그냥 실수의 소숫점을 다루는 문제가 된다. 1. 파이값 구하기 math 라이브러리를 import하고 math.pi를 불러오면 된다. import math print(math.pi) 출력 3.141592653589793 2. 실수의 소숫점 자릿수 지정 이제 소숫점.. 2023. 2. 13. [백준 1018][파이썬] 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 처음에는 그래프 문제라고 판단을 하여 BFS로 이웃한 사각형 같을 경우 다른 것으로 바꿔버리는 방식으로 풀었다. 그러나 예외 사항이 너무 많아서 다른 방식을 고민해보았다. 생각을 해보다가 간단한 방식이 떠올랐다. 8x8 체스판의 경우 무조건 두 가지 경우의 수만 존재한다. WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWB.. 2023. 2. 11. [백준 2231][파이썬] 분해 합 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1. 길이가 N+1이고 모든 값이 0인 리스트 생성 ( li [ i ]의 값은 i의 생성자가 됨 ) 2. 반복문으로 1부터 N까지 3번 과정을 반복. 3. 분해 합을 구하고 리스트의 해당 인덱스 값이 0일 때만 그 값을 생성자로 변경 3번에서 값이 0일 때만 값을 생성자로 변경하는 이유는 반복문으로 1부터 증가하면서 분해 합의 생성자를 변경하기 때문에 가장 먼저 값이 .. 2023. 2. 9. 이전 1 ··· 6 7 8 9 10 11 12 ··· 14 다음 728x90 반응형
