Redddy's Devlog

List Operation Example Big-O Notes Index a[i] O(1) Store a[i] = 0 O(1) Length len(i) O(1) Append a.append(5) O(1) Pop a.pop() O(1) a.pop(-1)과 동일 Clear a.clear() O(1) a = [] 과 유사 Slice a[a:b] O(b-a) a[:] : O(len(a)-0) = O(N) Extend a.extend(...) O(len(...)) 확장 길이에 따라 Construction list(...) O(len(...)) 요소 길이에 따라 check ==, != |1 == |2 O(N) 비교 Delete del a[i] O(N) Remove a.remove(...) O(N) Containme..

a = [1,2,3,4,5,6,7,8,9,10] a 리스트에서 내가 8이라는 값의 위치를 찾는 방법은 여러가지이다. 그중에서 순차탐색과 이진탐색을 설명하겠다. 순차탐색 (Sequential Search) 순차탐색은 그냥 말그대로 처음부터 이게 8인지 아닌지 확인해가면서 찾는 것이다. 즉 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 만약 찾고자하는 데이터가 제일 끝에 있다면, 데이터 개수가 N일 때 최대 N번의 비교 연산을 수행함으로 최악의 경우 시간 복잡도는 O(N) 이다. 이진탐색 (Binary Search) 이진탐색은 절반씩 쪼개가면서 찾는 것이다. 이때 a list가 정렬되어 있어야만 사용가능하다. 1~10 의 데이터 중 8의 위치를 찾으려면 ..

a = [1,2,3,4,4,4,5] 위에 a 리스트에서 4를 지우고 싶다. 물론 a.remove(4)를 하면 되지만 그럴 경우 4 하나만 지워지고 두개의 4가 아직 남아있다. 이럴때 해결방법!! a = [1,2,3,4,4,4,5,5,6] remove_set = {4,6} result = [i for i in a if not in remove_set] print(a) >> [1,2,3,5,5] remove_set 이라는 set을 만들어준다음 a가 remove_set에 포함되어 있다면 result에 담지 않는 것이다!

프로그램 내에서 바로 시간 복잡도를 측정할 수 있는 외장함수가 있다. time 을 import 해서 시작 부분에 시간을 start_time에 넣고 코드 마지막에 end_time을 넣어 그때의 시간을 측정한다음 뺄셈을 해준다. 그러면 그 사이 코드가 수행된 시간을 알 수 있다.

브루트 포스 (Brute-force) 는 '무차별 대입' 이라는 의미이다. 말 그대로 모든 경우의 수를 대입해보는 것이다. 완전탐색 전략을 사용하여 확실하게 답을 구하는 알고리즘이지만 단점은 시간복잡도에 있다. 모든 경우를 돌아보기 때문에 문제에서 시간초과가 발생 할 수 있다. 다음 문제를 보자. N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는? 브루트 포스를 사용한다면 2중 for문을 돌면서 두 수를 골라 더해서 최댓값을 갱신하면 '두 수를 뽑는 모든 경우'를 살펴보게 되고, 답을 확실하게 구할 수 있다. 이때 시간 복잡도는 O(N^2)이 된다. 버뜨 list 사용해서 최댓값 찾고 그 두개를 더하면 시간복잡도는 O(NlogN)이다. 브루트 포스로 문제를 풀 때는 반복문을 사용할 때도 있고, ..

컴퓨터는 기본적으로 2진법을 사용한다. 2진법이란 0과 1로 모든 숫자를 표현하는 것이다. 우리가 평소에 사용하는 진법은 0부터 9까지 사용하는 10진법이다. 하지만 주위에 12진법 또는 60진법도 눈에 띈다. 시간에서 hour가 12진법, minute 이 60진법이다. 이제 코딩에서 진법을 변환하는 방법을 알아보자. 2진수 : 0b 8진수 : 0o 16진수 : 0x 이렇게 접두사가 붙는다. a = int(100, 2) 이것은 2진수인 100을 10진수로 바꾼다는 의미이다. a를 출력해보면 4가 출력된다. a = int(100, 8) 이는 8진수 100을 10진수로 바꾼다는 뜻이다. a를 출력해보면 64가 출력된다. format(a, 'b') 이것은 10진수 a를 2진수로 바꾼다는 의미이다. b를 o로 ..