-
[교육용] STL, 자료구조 및 문제풀이 꿀팁
원래 이번 포스트는 탐색으로 쓰려고 했는데 그래프 그리기 귀찮아서 stl을 쓰기로 했어요 ㅠㅠ stl만 다루는 건 아니고, 문제풀이에 사용되는 몇 가지 스킬들에 대해서도 이야기하려고 해요. 원래 map, set, list 등등 많이 다루려고 했는데 포스트가 교내대회 교육용이기도 하고… 출제범위 밖이기도 하고… 귀찮기도 하고… 그리고 제일 중요한 건! 이 포스트에서는 stl의 사용법에 대해서 다루지 않습니다. 대신 stl을 어떻게 사용해야하는지, stl의 활용법에 대해서 다룹니다. 문법에 대한 건 http://www.cplusplus.com 여기에 다 나와있어요 >_< 그리고 또 어차피 stl 컨테이너가 다...
-
[교육용] 이분 탐색
안녕하세요! 이번 포스트에서는 binary search에 대해 이야기 해보겠습니다. binary search, 이분 탐색은 어떤 정렬된 범위 내에서 우리가 원하는 값을 빠르게 찾기 위한 탐색 방식입니다. 예시 문제 https://www.acmicpc.net/problem/1920 수 찾기 n개의 정수열 중에 어떤 숫자 X가 존재하는지 판단하는 문제입니다. 평범하게 구현했을 때, X가 존재하지 않는 최악의 경우 n개의 모든 숫자를 돌아보아야 하므로 시작복잡도는 O(n)이 됩니다. 하지만 이분 탐색을 이용하면 O(n)을 O(log n)으로 줄일 수 있습니다. 이게 얼마나 빨라진 거냐면, 2^100번 돌아야하는 작업을 100번만 돌아서 끝낼 수...