본문 바로가기
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.
[Beakjoon/백준] 2579 파이썬 문제: https://www.acmicpc.net/problem/2579 사용 알고리즘: DP  - 1번째 계단에 올라가는 법은 1가지 밖에 없음dp[1] = stairs[1]  - 2번째 계단에 올라가는 법1번째 계단 -> 2번째 계단 : dp[2] = stairs[1] + stairs[2] -> 무조건 최댓값이 더 큼2번째 계단:  dp[2] = stairs[2] - 3번째 계단에 올라가는 법1번째 계단 -> 3번째 계단: dp[3] = stairs[1] + stairs[3] 2번째 계단 -> 3번째 계단: dp[3] = stairs[2] + stairs[3]이 경우에는 계단에 부여된 점수에 따라 상황이 달라질 수 있음-> dp[3] = max(stairs[1] + stairs[3], stairs[2.. 2024. 5. 14.
728x90
반응형

티스토리툴바