본문 바로가기
728x90
반응형

Algorithm4

[알고리즘] 이진 탐색(Binary Search) 이진 탐색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.  처음에 중간의 값을 임의의 값으로 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교하여 찾고자 하는 값을 찾아간다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.   이제 이진 탐색 맛보기를 해보자! 단어가 아주 많이 있는 영어사전에서 Program 이라는 단어를 찾는다고 가정해보자. 단, P 로 시작하는 단어의 첫 페이지로 가지 않고, 사전을 펼치는 작업을 반복해서 찾아보자. 물론, 펼치는 횟수가 적을 수록 좋다. 어떤 페이지를 펼치는 것이 좋을까?가장 좋은 방법은 전체 페이지의 반이 되는 페이.. 2024. 8. 18.
[Algorithm/알고리즘] 투포인터(Two Pointer) 알고리즘 투포인터 알고리즘(Two Pointers Algorithm)1차원 배열에서 두 개의 점 위치를 기록하면서 원하는 것을 처리하는 알고리즘병합정렬(merge sort)의 기초구간합을 구할 때 매우 유용 (완전 탐색으로 시간초과가 난다면 투포인터를 써보자!) 두 포인터를 보통 start, end 포인터라고 하며, 부분 배열의 처음과 끝을 가르키는 역할을 한다. 맨 처음은 항상 start = end = 0 이며, start 포인터는 end 포인터보다 뒤에 있을 수 없다. (start  1. 현재 부분합이 M 이상이거나, 이미 배열의 마지막칸에 있다면 start 포인터를 한 칸 앞으로 옮긴다 ( 이 방향 →)2. M 보다 작다면 end 포인터를 한 칸 앞으로 옮긴다 ( 이 방향 →)3. 현재 부분합이 M 이라면 .. 2024. 7. 24.
[Algorithm/알고리즘] 누적합 알고리즘 Prefix Sum A = [1, 2, 3, 4, 5]# 부분합 = [1, 3, 6, 10, 15]  위와 같은 배열 A 가 있다. 이 배열의 각 부분합을 구해야 할 때 구할 수 있는 방법이 2가지 있다.    1. 각 인덱스를 반복해서 돌면서 구하기 ans = 0for i in range(start, end+1) ans += A[i]위 코드의 시간 복잡도는 O(N) 이며, 각 부분합을 구하기 위해서는 배열의 크기만큼 위 코드를 반복해야 한다.  ans = 0for j in range(배열의 크기): for i in range(start, end+1) ans += A[i] 그러므로 총 시간 복잡도는 O(NM) 이 된다. (M: 배열의 크기인 임의의 수)  2. 누적 합  누적 합 아이디어는 배열 A 에 들어있는 값이 바뀌.. 2024. 7. 9.
스택(stack), 큐(queue) 스택 (stack)데이터 값을 저장하는 기본적인 구조로 일차원의 선형 (linear) 자료구조(배열/리스트와 유사하게) 값을 저장하는 연산과 저장된 값을 꺼내는 연산이 제공됨but 매우 제한적인 규칙: LIFO (Last In First Out) -> 가장 최근에 저장된 값이 가장 먼저 나감stack 용어Top: 스택에 가장 최근에 넣은, 스택의 맨 위에 있는 데이터Push: 스택에 데이터를 넣는 행위Pop: 스택의 맨 위에 있는 데이터를 삭제하는 행위empty/full: 스택에 데이터가 꽉 찼는지, 스택에 데이터가 없는지 확인size(len): 스택에 들어있는 데이터의 개수 리턴stack 시간 복잡도 (Big-O 시간)삽입: O(1)삭제: O(1)검색: O(N) # stack 구현class Stack.. 2024. 1. 10.
728x90
반응형

티스토리툴바