시간 복잡도란? 주어진 문제를 해결하기 위한 연산 횟수 일반적으로 파이썬 프로그램에서는 2,000만 번 ~ 1억 번의 연산을 1초의 수행시간으로 예측 할 수 있음 시간 복잡도 정의 빅 - 오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수 빅 - 세타(Θ(n)) : 보통일 때(average case)의 연산 횟수 빅 - 오(Ο(n)) : 최악일 때(worst case)의 연산 횟수 코드예제 import random findNumber = random.randrange(1,101) #1~100까지 랜덤값 생성 for i in range(1,101): if i == findNumber: print(i) break # 빅 - 오메가 : 1번 # 빅 - 세타 : 50번 (N/2) # 빅 -오 : 1..
전체 글
1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 👾접근 주어지는 수의 범위가 절댓값이 1,000,000,000 이하인 정수인 점 과 정수 중복도 가능하다는 점을 알고 있어야 한다..(이거 고려못하고 중복없는 양의 정수로 풀어서 헤맸다) 즉, 체크되는 수를 제외한 두 수의 합이 체크되는 수와 같기만 하면 된다. 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn) 이 되어야 함 => 정렬과 투포인터 사용해보기 리스트를 정렬한 후 좋은 수 여부를 체크할 위치를 지정하고 해당 인덱스를 제외하고 양쪽 끝 인덱스로 s 와 ..
1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 🐱🏍접근 입력받은 자연수 리스트를 오름차순으로 정렬한 후 양끝에서부터 포인터를 지정하여 두 수의 합을 구하는 방식으로 구현 시작 인덱스(s)는 리스트의 0번 인덱스에서부터 종료 인덱스(e)는 리스트의 마지막 (N-1)번 인덱스에서부터 시작 투 포인터 이동원칙 - lst[s] + lst[e] > M : e -= 1 - lst[s] + lst[e] < M : s += 1 - lst[s] + lst[e] == M : cnt +=1;..
투포인터 2개의 포인터로 알고리즘의 시간 복잡도를 최적화할 수 있음 2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 🐬접근 N의 최댓값이 10,000,000 이므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한시간 2초를 초과함. 따라서 O(n)의 시간 복잡도 알고리즘을 써야함. 연속된 자연수이므로 투포인터를 활용해 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현할 수 있음 시작 인덱스(s)를 1씩 증가시킨다(오른쪽으로 1칸 움직인다) = 연속된 자연수에서 왼쪽 ..
구간합 다른 문제 구간합1 구간합2 10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 🐲접근 (A+B) % C = ((A%C)+(B%C))%C 해당 구간 합의 나머지 연산 값 = 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 합 배열 S 가 있다고 할 때, S[i] % M == S[j]%M 이면 (S[i] + S[j])%M == 0 : 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[i] 와 S[j] 가 같은 (i,j) 쌍을 찾으..
