코딩테스트 복기 - 당장 필요한 값을 구하지 않고 나중에 필요할 때 값을 구하는 테크닉2

1. 문제 n명의 아이는 연속 A[i]일 이내 칭찬을 듣지 못하면 기분이 안좋아진다. (i = 1,2,3,...,n) 선생님이 1일부터 m일까지 매일 1명의 아이 B[i]번 아이에게 칭찬을 해준다. (i = 1,2,...,m) 이미 기분이 안좋아진 아이에게 칭찬을 해줘도 아이는 기분이 좋아지지 않는다. 1일부터 m일까지 각 날마다 기분이 좋은 아이의 수를 구하고자 한다. 0일차에는 모든 아이에게 칭찬을 해줘서 기분이 좋은 상태라고 가정한다. 예를 들어 4명의 아이는 2일, 3일, 1일, 2일 이내에 칭찬을 들어야한다. 선생님이 6일 동안 3번, 1번, 2번, 1번, 4번, 1번 아이에게 칭찬을 해줬다. 1일차에는 3번 아이에게 칭찬을 해줬다. 2일차에는 1번 아이에게 칭찬을 해줬는데, 2일 이내에 칭찬을..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 3. 26.
• textsms

-1 의 50만 거듭제곱을 -1**(500000)으로 하면 안되는 이유

파이썬에서 어떤 정수의 거듭제곱을 구한다면 **을 사용한다 print(3**2) 9 그런데 사실 -1의 거듭제곱은 홀수번 거듭제곱하면 -1이고 짝수번 거듭제곱하면 1이다. 그래서 단순히 n이 짝수인지 홀수인지에 따라 (-1)**(n)을 바로 계산할 수 있다 그래봤자 큰 차이 없는거 그냥 하면 되는거 아니냐? 라고 생각할 수 있는데, 한두번 계산하는건 크게 차이 없지만 n이 충분히 클때 (-1)**(n)을 여러번 계산하면 시간차이가 3~4배 정도로 차이가 난다

• format_list_bulleted Python
• · 2024. 2. 17.
• textsms

ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..

• format_list_bulleted Atcoder
• · 2024. 1. 7.
• textsms

시간을 줄이는 테크닉 - 파이썬에서 함수형 코드를 적극적으로 활용해야하는 이유(+ if __name__ == "__main__"의 활용?)

알고리즘 문제를 풀다보면, 함수형 코드로 작성하는데 시간안에 통과하지만, 그렇지 않았을때 시간 초과나는 경우가 있다 기분탓인줄 알았는데 17467번: N! mod P (2) (acmicpc.net) 17467번: N! mod P (2) 양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라. www.acmicpc.net 이렇게 쓰면 통과를 못하는데 n,p = map(int,input().split()) if n == p-1: answer = p-1 elif n > p - n: answer = 1 for i in range(n+1,p-1): result *= i result %= p answer = pow(answer,p-2,p) else: answer = 1 for i i..

• format_list_bulleted Python
• · 2023. 8. 13.
• textsms

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

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

Big O notation의 정의는 알고 쓰자

1. little O notation 두 함수 f(x)와 g(x)가 어떤 a에 대하여 $$\left| f(x) \right| \leq \varepsilon g(x)$$ 를 만족하는 모든 양의 상수 $\varepsilon$ 이 $0< \left| x-a \right| < \delta$에서 존재하게 하는 $\delta$가 존재한다면, $$f(x) = o(g(x))$$ x →a 라고 표현한다. 동일한 말로 g(x)가 0이 아닐때, $$f(x) = o(g(x))$$ x →a 는 $$\displaystyle \lim_{ x \to a} \frac{f(x)}{g(x)} = 0$$ 과 동치이다. 근데 일단 이거는 그냥 극한으로 이해하는게 편한것 같다 2. 직관적인 이해 $$\displaystyle \lim_{ x ..

• format_list_bulleted 프로그래밍 개론
• · 2022. 9. 16.
• textsms