알고리즘(14)
-
Stack(스택)
Stack(스택) - 가장 나중에 추가한 데이터가 가장 먼저 출력되는 후입선출(Last In First Out) 형식으로 데이터를 저장하는 구조이다. - stack에서 데이터를 추가하는 것을 push라고 하고 stack의 top 에서 데이터를 추출하는 것은 pop이라고 한다. # stack 선언 stack = [] # push 0 (1) stack.append(1) stack.append(2) stack.append(3) stack.append(4) print(stack) #[1, 2, 3, 4] stack.pop() print(stack) #[1, 2, 3] stack.pop() print(stack) #[1, 2] stack.pop() print(stack) #[1]
2023.02.23 -
큐(Queue)
Queue 구현 방법 - Array list 사용해서 - Linked list 사용해서 Queue( 큐 ) - 먼저 저장된 데이터가 먼저 출력(First In First Out) - 큐의 뒤쪽에 데이터를 추가하는것을 enqueue라고 한다. - 큐의 앞쪽에서 데이터를 꺼내는 것을 dequeue라고 한다. 파이썬에는 잘 구현된 Queue가 있다. 그것은 deque로 Linked list로 구현되어 있다. from collections import deque queue = deque() # enqueue() - Queue에 앞에부터 데이터가 들어감 queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) print(queu..
2023.02.23 -
Linked List
Linked List -Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조 -각 Node에는 데이터와 다음 노드의 주소값이 들어가있다. -메모리에는 각 Node가 비연속적으로 저장되어 있지만 각 노드에는 다음 노드의 메모리 주소를 알기에 논리적으로는 연속성을 갖고있다.(물리적으로 비연속, 논리적으로 연) -메모리가 연속적으로 있지 않으니 메모리 사용에는 자유로우나 각 노드당 데이터뿐만 아니라 다음 노드의 메모리 주소를 저장해야 하니 데이터 하나당 차지하는 메모리가 더 커진다. VSCode에서 Linked List를 구현해보자 #Node는 Linked List에서 각 데이터와 다음 Node를 가리키는 데이터가 들어있는 객체이다 #Node가 연결되어서 하나의 Linked List가 되는거다. ..
2023.02.19 -
Sort & Two Pointer
파이썬에는 기본적으로 오름차순으로 sort를 해주는 메소드가 있다. sort의 시간복잡도는 O(nlogn)이다. Tow Pointer 보통 sort와 tow pointer는 같이 사용된다. 예를 들어서 설명하겠다. [9, 3, 2, 6] 위와 같은 list가 있다. 위의 list를 오름차순으로 정열하면 [2, 3, 6, 9] ^ ^ Tow pointer를 한글로 하면 두지점이다. 두 지점을 왼쪽 끝과 오른쪽 끝에 두 지점이 있다고 생각하자. list 내에 있는 숫자를 더해서 우리가 원하는 값이 있는지 확인을 할거다. 더해서 10이 있는지 확인을 하면 왼쪽과 오른쪽 두지점을 일단 더한다. 11이 나오고 우리가 원하는 값 10보다 더한값이 크다. 그럼 왼쪽에 오른쪽에 있는 포인트를 한칸 왼쪽으로 이동한다 [..
2023.02.19 -
리스트(List)
List [1,2,3] [2,1,3] [3,1,2] 위에 있는 리스트는 전부 다른 리스트이다. 같은 숫자로 이루어져있지만 순서가 다르기 때문이다. 하지만 위에 있는 예시가 Set이라면 전부 같은거다 왜냐하면 순서가 상관없기 때문이다. List 구현방법 -Array list (Array, Dynamic array >>> Array List는 Dynamic array로 되어있고 Dynamic array는 Array로 되어있음) ex) 파이썬에서 list -Linked list(Node) 배열의 특징 -고정된 저장 공간 -순차적으로 데이터 저장 -배열을 선언하면 size가 정해지고(static array) size만큼 연속된 메모리를 할당 받아 data를 순서대로 저장하는 자료구조 시간복잡도도 int arr[..
2023.02.19 -
시간복잡도
43, 12, 43, 22, 11 위의 다섯개의 숫자가 있다. 이 숫자를 오름차순으로 정열하는 코딩을 할거다. 작성한 코딩을 실행하면 결과가 나올때까지 걸리는 시간이 runnint time이다. cpu는 코딩을 한줄한줄 처리해 나가는데 각 소스마다 걸리는 시간이 있다. 예를들어 반복문이 한번 실행하는데 1n 걸린다고 하면 반복문을 열번 돌리면 10n이 걸린다. 이 반복분을 이중 반복문으로 10번하면 100n^2이 걸린다. 이중 반복문 말고 다른 소스의 걸리는 시간이 3n + 4 걸린다고 하면 전체 걸리는 시간은 100n^2 + 3n + 4가 된다. 시간복잡도는 빅오로 나타내는데 최고차수만 나타낸다. 빅오로 나타내면 O(n^2)가 된다. 3 >>> O(1) 3n^2 + 2n + 4 >>> O(n^2) 2n..
2023.02.18