파이썬/알고리즘3

• 

  [자료구조] 파이썬 Queue 라이브러리 파이썬에서 미리 정의된 Queue 클래스를 사용할 수 있다. 총 3가지 유형의 Queue를 사용할 수 있는데, 각각 FIFO 큐, LIFO 큐, 우선순위 큐 라고 한다. Queue() 일반적인 큐, FIFO import queue queue = queue.Queue() queue.put(1) queue.put(4) queue.put("hello") print(queue.get()) print(queue.get()) print(queue.get()) 먼저 put된 요소가 먼저 get 선입선출 LifoQueue() import queue lifo_queue = queue.LifoQueue() lifo_queue.put(1) lifo_queue.put(4) lifo_queue.put("hello") print.. 파이썬/알고리즘 2023. 10. 27.

• [알고리즘] 구간 합 구간 합(prefix sum) 배열이나 리스트에서 특정 구간의 합. 1차원 리스트에서 i 인덱스 부터 j 인덱스 까지의 합을 구하는 데 사용. 구간 합 알고리즘을 활용하려면 누적 합 배열을 알아야한다. 합 배열 만약 배열의 0부터 N까지의 합을 구한다면 시간 복잡도는 O(N)이다. 합 배열을 사용하면 O(1) 안에 해결할 수 있다. S[3] = A[0] + A[1] + A[2] + A[3] S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i] 배열: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 위 배열의 S[5]를 구하면 1 + 2 + 3 + 4 + 5 + 6 = 21 배열의 합을 구하는 시간 복잡도는 O(N)이다. 만약 합을 반복하여 구해야한다면 O(N^.. 파이썬/알고리즘 2023. 10. 21.

• [알고리즘] 자료구조, 배열과 리스트 기본 자료구조로서의 배열과 리스트에 대해 알아본다. 배열 배열은 메모리 공간에 연속적으로 존재한다. 각 인덱스는 연속된 메모리 주소를 갖는다. 인덱스로 값에 접근할 수 있다. 특정 인덱스의 값을 삽입하거나 삭제하려면 인덱스 주변의 값들도 이동시켜야한다. 배열의 크기는 선언할 때 지정할 수 있다. 선언된 배열의 크기는 변경할 수 없다. 리스트 인덱스가 없다. 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 노드로 이루어져 있다. 노드는 값과 다음 값의 주소를 가리키는 포인터로 이루어져있다. 포인터를 사용하기 때문에 데이터를 삽입하거나 삭제하는 연산이 빠르다. 선언할 때 크기를 지정하지 않아도 된다. 포인터를 저장할 공간이 필요하다. 파이썬의 리스트 파이썬의 리스트는 기본 자료구조로서의 리스트와.. 파이썬/알고리즘 2023. 10. 21.