파이썬 알고리즘 기본기 곱셈 연산에서 주의할 점 배우기(세그먼트 트리 문제)

1. 문제 5676번: 음주 코딩 (acmicpc.net) 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 특정 구간의 수열의 곱이 양수인지 음수인지 0인지 판단하거나 특정 인덱스의 원소를 바꾸는 쿼리를 수행하는 문제 2. 곱셈의 시간복잡도 매우 큰 수를 곱할수록 프로그램의 시간복잡도가 높아진다. 이게 몇번만 연산하면 별로 차이 없어보이지만 10만번이나 반복연산해야한다면, 눈에띄게 느려진다 매우 큰 4개의 수를 곱하는 과정을 10만번 반복했는데 평균적으로 0.03초 걸린다면... 단순히 1,2,3,4 4개..

• format_list_bulleted 세그먼트 트리
• · 2022. 12. 10.
• textsms

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제 2. 풀이 가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다 1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다 그래서 한번 해보면 from sys import stdin n = int(stdin.readline()) dp = [0] * 1000001 dp[1] = 1..

• format_list_bulleted 정수론
• · 2022. 9. 9.
• textsms

매우 큰 수를 나머지 연산으로 줄일 수 있는 마법(백준-개미)

1. 문제 https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 좌표평면 안에서 개미가 대각선 방향으로 움직이는데, 벽면에 부딪힐 경우, 반사되어 움직인다. 일정한 속력으로 움직일 때, 평면의 크기, 처음 좌표가 주어지고 시간 t가 주어질때, t시간 후에 개미의 위치를 구해본다면..? 2. 풀이 시간 t의 범위가 2억이나 되니까, 일반적인 1칸씩 가는 반복연산으로는 도저히 0.15초만에는 불가능 그렇다고 벽면까지 한번에 가는 방법으..

• format_list_bulleted 애드 혹 알고리즘
• · 2022. 8. 30.
• textsms

분할정복을 이용한 거듭제곱 빠르게하기

1. 분할정복 문제를 더 이상 나눌 수 없을 때까지 더 작은 문제로 나누면서 이 작은 문제들을 각각 풀면서, 병합하여 전체 문제의 답을 구하는 알고리즘 divide - conquer - combine 방식으로 설계한다. 문제가 분할이 가능하면 2개 이상의 작은 문제로 나눈다(divide) 나누어진 문제가 분할이 가능하면, 또 다시 문제를 분할하고 그렇지 않으면 문제를 푼다(conquer) 푼 문제들을 통합하여 전체 문제의 답을 구한다(combine) 당연하지만 divide를 잘 하면 나누어진 문제를 푸는 것은 매우 쉬우므로 divide를 잘 하는 것이 중요하다 재귀알고리즘을 많이 사용하게 되는데, 이 때문에 오히려 효율적이지 못할 수 있다. 2. 응용 - 거듭제곱 n번의 거듭제곱은 자신을 n번 곱하므로 ..

• format_list_bulleted 분할 정복
• · 2022. 8. 15.
• textsms

반드시 알아야하는 유용한 파이썬(Python) 수학 연산

문자간 덧셈을 하면 문자끼리 이어붙여줌(concatenation) **은 거듭제곱 연산 %는 나눗셈의 나머지를 구해줌 +=은 증가 연산으로 a+=1은 a = a+1 -=은 감소 연산으로 a-=1은 a = a-1

• format_list_bulleted Python
• · 2022. 1. 19.
• textsms