[TIL] - 2023.04.13

👥 이진 탐색

- 배열이 정렬되어 있어야 하며, 하나의 배열에서 반반 쪼깨서 값을 찾는 탐색이다.
- 시간 복잡도는 O(logN)이다

이진 탐색의 기본 틀

from sys import stdin as s

s = open('input.txt','rt')

N, M = list(map(int,s.readline().split()))

arr = list(map(int,s.readline().split()))

def binary_search(array, target,start,end):
    if start > end:
        return None
    mid = (start + end) //2

    if array[mid] == target:
        return mid
    elif array[mid] >target:
        return binary_search(array,target,start,mid-1)

    else :
        return binary_search(array,target,mid+1,end)


result = binary_search(arr,M,0,N-1)
if result == "None":
    print("존재하지 않습니다.")
else:
    print(result + 1)

반복문으로 작성한 이진 탐색 틀

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

    return None


n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result is None:
    print('원소가 존재 X')
else:
    print(result + 1)

브루트 포스 문제 리스트

NO	LV	유형	제목	비고
1110	B1	브루트 포스	더하기 사이클	성공
9095	S3	브루트 포스	1,2,3 더하기	성공
1182	S2	브루트 포스	부분 수열의 합	성공

---

 

 작은 일에 최선을 다하라

" 행복은 작은 일을 통해 깨닫게 된다. 그리고 이것은 결코 작은 일이 아니다. "

- 제논, 디오게네스의 강의에서 인용, 탁월한 철학자들의 삶 7. 1. 26

좋은 사람이라는 평판은 그가 한 말 때문이 아니다. 그가 행한 바람직한 행동 때문에 만들어진다. 이는 마법 같은 단 한번의 행동이 이루어 내는 것이 아니라 바람직한 선택의 누적이 만들어 내는 것이다.

 눈 앞에 있는 일에 집중하라

" 매일매일 닥쳐올 모든 일을 로마인들처럼 강건한 망므으로 처리하라. 엄격하고 단순한 위엄, 애정과 자유, 그리고 공평무사함으로 대하라, 이것 외에 다른 사항은 생각하지 말라. 합리적 이성이 감정에 휘둘리지 않도록 하고, 잡념에 매이지 않으며, 극적인 상황과 자만심, 공정한 몫에 대한 불평을 잠재워라. 마지막인 것처럼 주어진 일에 접근하라. 이 몇가지를 배우는 것만으로도 풍요로운 삶과 독실한 인생을 완성할 수 있을 것이다. 이를 끊임없이 실천할 수 있다면 신도 우리에게 더 많은 것을 요구하지 않는다. "

- 마르쿠스 아우렐리우스, 명상록, 2.5

수많은 장애물 앞에서 다른 사람을 신경 쓰지 않고 묵묵히 나의 길을 걸어갈 수 있어야 한다.
마자막인 것처럼 주어진 과제에 도전하라.
사념이 끼어들지 않는 한 우리에게 주어진 과제는 언제나 단순하다.

 모든 것을 알 필요는 없다.

" 발전하고자 한다면 외적인 문제(재물,평판)에 무감각해야 하고 그 속에서 어리석음을 볼 수 잇어야 한다. 많이 알고 있는 것처럼 보이는 것을 경계하라. 누군가 당신을 중요한 사람으로 간주한다면, 스스로를 불신하라 "

- 에픽테토스, 엥케이리디온, 13a

잠재적 위협에 더 이상 흥분하지도 분노하지도 않으려면 얼마나 더 휴식을 취해야 할까?

당장 눈앞의 일에 집중하자. 눈 앞에 있는 일에 집중을 하면서 작은 일도 최선을 다하자. 잔잔한 호수에 한 방울 한 방울 떨어지는 물방울이 큰 물결이 될 것이다.

 

---

 

 

 

DFS, BFS랑 브루트포스 하는 방법 익숙치 않았는데 여러 문제를 풀다보니 시험 1주차 문제들 전부 완전 탐색으로 해결했고, 다음 이분 탐색, 스택, 큐, 분할 정복 문제도 마찬가지로 여러 문제들을 풀어보면서 일단 문제에 익숙해져야 할 것 같다.