Stunning-PS 팀 블로그

Binary Search 알고리즘이란? 특징 Binary Search 알고리즘 작동 방법 Binary Search 알고리즘 구현 방법 시간복잡도 Binary Search 문제(leetcode 35) Binary Search 문제 모음 참고자료 Trie 알고리즘이란? 트라이는 사실 알고리즘이라기 보단 문자열에서의 검색을 빠르게 해주는 자료구조입니다 구성은 Tree 형태로 만들어지며 문자열에 관한 코딩 문제들에 kmp와 더불어 자주 쓰입니다 검색어 자동완성, 사전에서 찾기, 문자열 검사 부분에서 주로 사용됨 특징 탐색은 빠르나(...

이진 탐색이란? 알고리즘 동작 순서 이진 탐색 코드 예제. 수 찾기 이진 탐색이란? 정렬돼 있는 배열에서 특정한 값을 찾는 알고리즘 단순 완전탐색과 달리 중간에 있는 임의의 값을 선택한 후 찾고자 하는 값과 비교하며 탐색하는 알고리즘 알고리즘 동작 순서 13 15 25 35 51 65 75 찾을 값 : 65 임의의 가운데 값 35를 선택 65 > 35 이므로 35보다 우측에 존재 배열의 범위를 좁힘 51 65 75 좁힌 범위에서 가운데 값을 선택 후 비교 ...

Binary Search 이진탐색이란? 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교한다. x가 중간값보다 작으면 중간 값을 기준으로 좌측의 데이터들을, x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 예시 이미 정렬되어있는 10개의 데이터 중에서 4인 원소를 찾는다고 해보자. 이진 탐색의 시간 복잡도 단계마...

Binary Search 알고리즘이란? 특징 Binary Search 알고리즘 작동 방법 Binary Search 알고리즘 구현 방법 시간복잡도 Binary Search 문제(leetcode 35) Binary Search 문제 모음 참고자료 Binary Search 알고리즘이란? 정렬된 배열의 탐색에 적합한 알고리즘으로, 정렬된 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지 여부를 알아내어 탐색의 범위를 반으로 줄여가는 방법 예) 10억 명중에서 특정한 이름 검색 Binary Sea...

Two-Pointer 알고리즘 Two-Pointer 문제 코드 Two-Pointers Two Pointers는 뜻 그래도 2개의 포인터를 조작해 문제를 해결하는 알고리즘이다. 풀고자 하는 문제에 맞게 2개의 포인터를 1차원 배열에 위치시켜 문제의 해를 찾아나가는 과정이라고 보면된다. Two-Pointer 알고리즘 같은 경우 개념이나 이론이 크게 존재하지 않기 때문에 문제를 통해 이해하는 것이 가장 좋디 Two-Pointer 문제 2003번: 수들의 합 2 문제 내용 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이...

투포인터 (Two Pointers) 특정한 합을 가지는 부분 연속 수열 찾기 그림과 함께 설명하기 코드 시간복잡도 c.f> 슬라이딩 윈도우 투포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도. 특정한 합을 가지는 부분 연속 수열 찾기 투포인터 알고리즘의 대표적인 부분. ...

Two-Pointer 알고리즘이란? Two-Pointer 알고리즘이란 해석 그대로 2개의 포인터를 두고 검색을 한다는 의미로, 주로 정렬된 리스트에서 서로 다른 두개의 포인터를 이용해 순차적으로 접근하면서 원하는 타겟값에 도달할때까지 포인터를 조작하는 알고리즘이다. Two Pointer를 활용하는 대표적인 문제로 아래가 존재한다. 정렬된 리스트 li 에서 합이 xx가 되는 순서쌍을 모두 구하여라 li = [ 1, 2, 4, 6, 11, 14, 16, 19 ] 해당 문제를 해결 하기 위한 방법은 크게 이중 for문을 사용하는 방법과 Two-pointer를 사용하는 방법이 존재한다. 이중 for문 ...

KanpSack Problem 문제 접근 방법 1. 모든 경우의 수를 넣어보기 (brute force) 2. 넣을 수 있는 가장 무거운 물건부터 넣어보기 (Greedy) 3. 동적 계획법 사용하기 조합 최적화란? 현실세계에서 발생하는 최적화 문제는 대부분 효율적인 알고리즘을 가지지 않는 NP-Hard 문제에서 어떻게 최적화를 할지에 관한 것. 보통 문제 공간이 크기 때문에 조합 최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데에 중점을 둔다. KanpSack...