지금 당장 좋은 것 고르기 문제 알아보기 1. 가장 큰 순서대로, 가장 작은 순서대로와 같이 기준을 알게 모르게 제시해준다. -> 대체로 이 기준은 정렬 알고리즘을 사용해 만족시킬 수 있으므로 정렬 알고리즘과 같이 짝지어 출제되는 경우가 많다. 2. 그리디로 풀 수 있는 문제인지 파악하기 -> 미리 알고리즘을 간단히 계획해보고 그리디로 풀었을 때 최적해를 반환하는지 판단해야 한다. 3. 현재 선택이 이후의 선택에 영향을 주지 않는다. 4. 매 순간 최적의 해가 문제 전체의 최적의 해이다. 특징 계산속도가 빠르고 풀이가 간단하다 -> 제한 시간이 짧고 조건이 성립할 때 유용

투 포인터 알고리즘 (Two Pointer Algorithm)은 리스트에서 두 개의 포인터를 사용해 원하는 결과를 찾거나 특정 조건을 만족시키는 알고리즘이다. 보통 O(N)에 문제를 해결할 수 있어 유용하다! 두 포인터를 한 방향으로 진행: 두 포인터를 리스트의 시작 위치에서 같은 방향으로 움직인다. 일반적으로 시작 위치와 끝 위치에서 시작하고, 필요에 따라 포인터를 이동시키면서 조건을 만족하는 부분을 찾는다. 두 포인터를 반대 방향으로 진행: 두 포인터를 배열이나 리스트의 양 끝에서 서로 반대 방향으로 움직인다. 이 방식은 주로 두 요소의 합, 차 등을 비교하거나 반대 방향에서 수렴해가는 문제를 해결할 때 사용됩니다. 백준 1940번 https://www.acmicpc.net/problem/1940 1..

합 배열을 만들어 두고 이를 통해 구간 합을 구할 수 있다. 구간합: s[j]-s[i-1] => i~j까지의 구간 합 예제 풀이 import sys N,M=map(int, sys.stdin.readline().split()) num=sys.stdin.readline().split() li=[] for i in range(M): new=(sys.stdin.readline().split()) li.append(new) sectionsurplus=[0,int(num[0])] for i in range(0,len(num)-1): sectionsurplus.append(int(num[i+1])+int(sectionsurplus[i+1])) for i in range(M): A=int(li[i][1]) B=int(..

N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘으로 설계하면 풀이 가능 N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘으로 설계하면 풀이 가능 N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘으로 설계하면 풀이 가능 N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘으로 설계하면 풀이 가능 파이썬은 1초에 2,000만에서 1억정도의 연산을 처리할 수 있다.

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 결론 미리 보기 파이썬에서 string slicing은 시간복잡도 N(len(str))이므로 특정 인덱스의 글자에 접근할 때는 list로 만들어 접근하는 것이 시간복잡도 O(1)로 빠르다! 가장 직관적으로 짤 수 있는 코드는 아마 아래의 코드일 것이다. import sys N=int(sys.stdin.readline()) st='' for i in range(N): st+=str(i+1) for ..