반응형 DEVLOG88 파이썬(Python) 자료형(List, Set, Dictionary) 연산자 시간복잡도 (Big-O) 정리 저는 최근 코딩테스트를 준비하면서 자료구조 및 알고리즘을 다시 공부하고 있습니다. 문제를 풀다보면 종종 시간복잡도를 고려하지 않으면 오답처리 되는 경우가 있습니다. 저는 주로 파이썬(Python) 혹은 C++을 이용하는데, 오늘은 파이썬 주요 연산자의 시간 복잡도를 알아보겠습니다. Lists Operation Example Big-O Notes Index l[i] O(1) Store I[i] = 0 O(1) Length len(l) O(1) Append l.append(2) O(1) Pop l.pop() O(1) same as l.pop(-1) Clear l.clear() O(1) similar to l = [] Slice l[a:b] O(b-a) l[1:5] : O(1) l[:] : O(len(l)-0.. 2019. 9. 3. [BOJ 11047] 동전 0 파이썬 풀이 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 해설 2019/09/03 - [DEVLOG/Algorithms] - [BOJ 11399] ATM 파이썬(Python) 풀이 [BOJ 11399] ATM 파이썬(Python) 풀이 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제.. 2019. 9. 3. [BOJ 11399] ATM 파이썬(Python) 풀이 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제해설 전형적인 그리디 알고리즘 문제입니다. 그리디 알고리즘은 쉽게 말해서, 미래를 고려하지 않고 현 시점에서 최선의 선택을 하는 알고리즘을 말합니다. 정답 코드 N = int(input()) times_list = list(map(int, input().split())) times_list.sort() sum = 0 cnt = 0 for t in times_list: cnt += t sum += cnt print(sum) 예제로 주어진 [3, 1, 4, 3, 2]를 오름차순으로 정렬하여 [.. 2019. 9. 3. [BOJ] 파이썬(Python) 주의사항 및 Tips float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠. 반례 찾기 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다. 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등으 ㅣ최소 케이스가 잘 나오는지 확인하는 것이 좋습니다. 이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이.. 2019. 9. 1. 이전 1 ··· 10 11 12 13 14 15 16 ··· 22 다음 반응형
