이분탐색의 올바른 사고방식 익히고 lower_bound, upper_bound 가볍게 복기하기

1. 이분 탐색(binary search) False 구간, True 구간 2개의 partition으로 분할된 구간에서, 분할 경계의 위치를 O(logN)에 찾는 알고리즘이다. STL로 구현된 lower_bound와 upper_bound는 가장 유명한 이분 탐색 함수중 하나이다. 정렬된 배열에서 x의 lower bound는 정렬 상태를 유지한 채 x를 삽입할 수 있는 첫번째 위치이고 upper_bound는 마지막 위치이다. 위 그림에서 lower_bound(20)은 20을 넣을 수 있는 첫번째 위치로, 1번에 넣을 수 있다.. upper_bound(20)은 20을 넣을 수 있는 마지막 위치로, 4번에 넣을 수 있다..(원래 4번은 5번으로 이동하겠지) 이분 탐색적 설명으로는, lower_bound는 x보..

• format_list_bulleted 이분 탐색
• · 2023. 3. 29.
• textsms

자다가도 일어나서 바로 구현할 수 있어야하는 최단경로를 찾는 다익스트라 알고리즘 파헤치기 1편

1. 최단경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소인 경로 최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 다양한 종류가 있지만 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다 예를 들어 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우", "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우" 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 "노드"로 표현되고, 지점간 연결된 도로는 그래프에서 "간선"으로 표현된다. 2. 다익스트라 최단경로 알고리즘 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 시작 정점에서..

• format_list_bulleted 최단거리 알고리즘
• · 2022. 10. 3.
• textsms

이진 탐색 정복기1 -기본 이론 순차 탐색?-

리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘에 대하여 1. 순차 탐색 가장 기본적인 탐색 방법 n개의 데이터가 있을 때, 데이터를 차례대로 하나씩 확인하여 어떠한 처리를 해준 그 자체가 바로 순차 탐색이다. 순차 탐색(sequential search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 정렬되지 않은 리스트에서 데이터를 찾아야할때 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다 2. 순차 탐색으로 'IU'를 찾는 과정 1) 먼저 첫번째 데이터 'Daehyuck'는 찾고자 하는 문자열 'IU'와는 다르다. 따라서 다음 데이터로 이동 2) 두번째 데이터 'Taeyeon'은 찾고자 하는 'IU'와는 ..

• format_list_bulleted 이분 탐색
• · 2022. 9. 8.
• textsms