꾸준하게 거북이처럼

프로그래머스 알고리즘 문제에서 최대 공약수, 최소 공배수 관련 문제를 만났는데 이전에 까먹은 관련 알고리즘을 까먹지 않기 위해서! 기록하고자 한다! (파이썬 기준) GCD(greatest common divisor) 두 수의 최대 공약수를 의미하고 LCM(Largest Common Multiple) 두 수의 최소 공배수를 의미한다. 유클리드 알고리즘 두 수의 최대 공약수를 구하는 알고리즘이다. 2 개의 자연수 a,b에 대해 a> b 일때, a % b == r 라고 한다면 (r > 0), a 와 b의 최대공약수 == r과 b의 최대공약수 이다. 이를 이용해서 b % r == r' 일때 r % r' == xxx.... 이렇게 반복하다가 나머지가 0 일때 나누는 수가 a 와 b의 최대공약수다. 최대 공약수를 ..

알고 있으면 좋은 2차원 배열 회전 알고리즘엠 대해서 알아보려고 한다. 가끔 문제에서 90도로 회전한 2차원 배열이 필요할 때가 있다. 오른쪽으로 90도 회전하기 Before After 1 (0, 0) (0, 2) 2 (0, 1) (1, 2) 3 (0, 2) (2, 2) 규칙을 보면 - 회전 전의 column 번호와 회전 후의 행 번호가 일치한다. - 회전 후의 열은 n - 1 에서 회전 전의 행을 뺀 값과 같다. 코드 def rotate_90(m): N = len(m) res = [[0] * N for _ in range(N)] for r in range(N): for c in range(N): res[c][N-1-r] = m[r][c] return res 90도로 바꾸는 함수를 몇 번 반복하면 180..

list를 사용하는 일이 엄청 많기 때문에 list에서 자주 사용하는 내장 함수의 시간 복잡도를 정리해봤다. 시간 복잡도가 O(1)인 연산 len(a) a.append(x) a.pop() 시간 복잡도가 O(k)인 연산 a[i : j] 시간 복잡도가 O(n)인 연산 x in a a.count(x) a.index(x) a.pop(0) => 시간 초과 나올 수 있으니, deque를 이용해서 popleft를 사용하면 O(1) 시간 복잡도로 맨 앞 요소를 뺄 수 있다. del a[x] min(a), max(a) a.reverse() 시간 복잡도가 O(nlogn)인 연산 a.sort() 참고자료 Python list 연산에 따른 시간 복잡도 python list 연산에 따른 시간 복잡도 시간 복잡도가 O(1)인 연..

항상 코딩테스트를 칠 때도 그렇지만, 개발할 때 최대한 효율적인 코드를 짜야하고 효율적이라는 것은 빠르게 동작하는 것으로 봐도 무방하다. 나중에 도움이 될 것 같아서 입력 수에 따른 시간 복잡도 설계를 어떻게 둘지 팁을 알아봤다. 입력된 수가 N일 때, 시간 제한이 1초(1억번 연산) 라고 가정. N의 범위가 500일 때, => 시간 복잡도가 O(n^3)인 알고리즘까지 설계 가능. N의 범위가 2000일 때, => 시간 복잡도가 O(n^2)인 알고리즘까지 설계 가능. N의 범위가 100,000일 때, (10만) => 시간 복잡도가 O(nlogn)인 알고리즘까지 설계 가능. N의 범위가 10,000,000일 때, (1000만) => 시간 복잡도가 O(N)인 알고리즘까지 설계 가능. 참고자료 [Coding ..