yimjiyoung / daily-datastructure-algorithm Goto Github PK

def rotate1(arr):
    return list(zip(*arr[::-1]))
# 참고: https://stackoverflow.com/questions/8421337/rotating-a-two-dimensional-array-in-python

def rotate2(arr):
  n = len(arr) # 행 길이 계산
  m = len(arr[0]) # 열 길이 계산
  result = [[0] * n for _ in range(m)] # 결과 리스트
  for i in range(n):
    for j in range(m):
      result[j][n - i - 1] = arr[i][j]
  return result

• zip(*iterable): 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수

>>> list(zip([1, 2, 3], [4, 5, 6]))
[(1, 4), (2, 5), (3, 6)] # 리스트의 같은 인덱스의 요소끼리 묶임
>>> list(zip([1, 2, 3], [4, 5, 6], [7, 8, 9]))
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
>>> list(zip("abc", "def"))
[('a', 'd'), ('b', 'e'), ('c', 'f')]

• * : Unpacking Argument Lists. 리스트의 각 요소를 argument로 넘겨준다

function getAllSubsets(array) {
    const subsets = [[]];
    
    for (const el of array) {
        const last = subsets.length-1;
        for (let i = 0; i <= last; i++) { // 기존 subset 배열에 자신을 추가한 새로운 배열 만들어 push
            subsets.push( [...subsets[i], el] ); 
        }
    }
    
    return subsets;
}

Here is an example for [1, 2, 3]

• Start with an empty subset: []

• Create new subsets by adding "1" to each existing subset. It will be:[] [1]

• Create new subsets by adding "2" to each existing subset. It will be:[], [1] [2], [1, 2]

• Create new subsets by adding "3" to each existing subset. It will be: [], [1], [2], [1, 2] [3], [1, 3], [2, 3], [1, 2, 3]

참고 : https://stackoverflow.com/questions/42773836/how-to-find-all-subsets-of-a-set-in-javascript

가장 긴 증가하는 부분 수열 구하기 - 다이나믹 프로그래밍

• D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
• DP 테이블의 값은 모두 1로 초기화한다.
• 모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j] + 1) if arr[j] < arr[i]

소수: 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수

# 소수 판별 함수
def is_prime(x):
  # 2부터 x의 제곱근까지의 모든 수를 확인하여
  for i in range(2,  int(math.sqrt(x)) + 1):
    # x가 해당 수로 나누어떨어진다면
     if x % i == 0:
          return False # 소수가 아님
  return True

에라토스테네스의 체

1. 2부터 N까지의 모든 자연수 나열
2. 남은 수 중에서 아직 처리하지 않는 가장 작은 수 i 찾기
3. 남은 수 중에서 i의 배수 모두 제거
4. 더 이상 반복할 수 없을 때까지 2, 3번 과정 반복

// 에라토스테네스의 체
  const isPrime = new Array(maxNum).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(maxNum); i++) {
    if (isPrime[i]) {
      let j = 2;
      while (i * j <= maxNum) {
        isPrime[i * j++] = false;
      }
    }
  }

두 개의 변수를 한꺼번에 대입하는 방법을 같은 값을 대입하더라도 a, b = -1, -1 방식으로 하는 방법밖에 몰랐는데 알고보니 a=b=1도 된다는 것을 이 글을 통해 발견 ! 그러나 이와 같이 대입할 때에 a = b = []와 같이 mutable 객체를 다룰 때는 주의하라고 한다. mutable vs immutable에 대해 대충 레퍼런스 차이?라고만 기억하고 있는데 더 자세히 알아둬야 하는 개념인 것 같아 이후 공부해보기로 !

bisect

bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
bisect_right(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

• 시간복잡도 : log(N)
• 참고: https://docs.python.org/ko/3/library/bisect.html

특정 범위에 속하는 원소의 개수 구하는 함수

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index