알고리즘(5)
-
이분 탐색 알고리즘 (binary search)
안녕하세요! 뤀카입니다. 오늘은 또다른 기초 알고리즘 '이분탐색' 에 대해서 알아보겠습니다! 어려운건 언제하냐고요? 기초가 어느정도 끝나면 고난이도 ps랑 고급 알고리즘 알려드릴테니까 걱정 마십쇼. 그나저나, 이분탐색 알고리즘은 탐색 횟수를 줄이는 시간초과 개선용이라고 해야되나? 암튼 시간 단축에 유용한 알고리즘입니다. 이 알고리즘은 후에 고난이도 문제에도 많이 나오므로 마스터를 하셔야 편합니다. 자 어떻게 하냐고요? 예시로 1부터 100까지 아무 수나 골랐다 칩시다 (저희가 맞춰야 해요). 그럼 부르트 포스로 하면 최악의 경우 100번이나 하게 될것입니다. 이제 이걸 이분탐색을 쓴다고 하면, 범위를 50 → 25 → 12 → 6 → 3 → 2 → 1순으로 비교를 하게됩니다. 그니까 전체에서 절..
2025.07.13 -
투 포인터 알고리즘 (two pointer)
투 포인터란? 배열에서 두 개의 인덱스를 사용하여 원하는 조건을 만족하는 구간이나 쌍을 찾는 알고리즘 기법입니다. 보통 정렬된 배열에서 많이 사용되며, 시간복잡도를 O(n^2) → O(n)이나 O(n log n) 수준으로 줄일 수 있습니다. 예시 문제로는 백준의 2470번 두 용액이 있는데요, 한번 풀이를 보면서 익혀 보시죠.🔗 문제 링크 풀이는 총 3단계로 나눌 수 있는데요,요약하면 다음과 같습니다. 풀이 핵심 요약배열을 정렬양쪽 포인터 사용: 왼쪽 + 오른쪽 값을 비교하며 움직임절댓값이 작은 쪽으로 갱신무슨 소리냐고요?좀 더 쉽게 알려드릴게요.배열을 정렬하고, 쭉 돌면서 왼쪽이랑 오른쪽 값을 비교하면 되요.그리고, 더 작은 쪽을 한칸 앞으로 옮기는거죠.그렇게 해서 두개가 서로 만나면 종료!참 쉽죠잉..
2025.07.09 -
컨벡스 헐(Convex Hull) 알고리즘
안녕하세요! 뤀카입니다. 오늘은 심화 기하학 알고리즘인 볼록 껍질(Convex Hull) 알고리즘에 대해서 알려드리겠습니다.볼록 껍질은 주어진 점들을 이어서 가장 큰 도형을 만드는 알고리즘입니다. 쉬워 보인다고요? 안 쉽다니까요 직접 해보세요쉽진 않습니다. 어느 정도 난이도냐면 최저가 P5이고요, 최고는... R1입니다. 참고:파이썬 설명이 많이 없더라고요. 그래서 파이썬으로 배우느라 고생해서....파이썬으로 글 쓰는 거입니다. c++은 나중에 올려드릴게요. 자 이제 본격적인 설명 하겠습니다.자 대표적으로는 그라함 스캔이 있는데요, 다음은 시뮬레이션 영상입니다.https://www.youtube.com/watch?v=Ps1idzOx6LA 어떻게 저렇게 하냐고요?ccw를 사용하면 됩니다. CCW는 점 A..
2024.11.09 -
누적합 알고리즘(prefix sum)
이 알고리즘은 "값의 변경이 없을때" 빠르게 구간합을 구하기 위한 알고리즘으로 시간 복잡도는 O(N) 입니다.일단 배열 a를 받아 줍니다. 예시)a = [0] + list(map(int,input().split())) #zero index사용 x 그 후, 1부터 a의 길이 번 반복하여 전에있는 값을 더해 줍니다. 예시)a = [0] + list(map(int,input().split())) #zero index 사용 xfor i in range(1,len(a)): #index error을 방지 하기 위하여 1부터 시작 a[i] += a[i-1] # 자신에다가 뒤에 닜는 값을 더함 이때 a가 [1,2,3,4,5]라고 가정하면, 다음과 같이 변경 됩니다.[1,3,6,10,15] 이제 이걸로 구간합을 구하..
2024.10.24 -
DFS 알고리즘
안녕하세요? 오늘은 기초 알고리즘 중 하나인 DFS(깊이 우선 탐색)을 알아보도록하겠습니다. dfs는 백트래킹의 사용되는 알고리즘으로 스택(리스트)를 필수적으로사용해야 합니다. dfs는 한마디로 루트노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.쉽게 말하면 미로 찾기를 할 때 한 방향으로만 가다가 벽이 나오면 이전에 있는 갈림길 중 가장 가까운 갈림길로다시 돌아가는 것을 의미합니다. 다음은 예시 코드입니다. step 1 : 함수 정의def dfs(now): # 함수정의. now = 현재 정점 print(now,end=' ') #현재 정점 프린트 visited[now] = 1 # 무한 루프 돌지 않게 방문 채크 for ..
2024.10.23