Computer Science/Datastructure & Algorithm4 이분탐색(Binary Search) vs 투포인터(Two Pointer) 알고리즘 코딩테스트에 자주 나오는 개념인데, 갑자기 둘 간의 차이가 뭐지 하는 의문이 들어서 정리하게 됐다. 완전탐색 시 시간초과가 나는 경우, 이분탐색이나 투포인터 알고리즘을 시도해보자. *이분탐색 vs 투포인터 알고리즘 이분탐색(이진탐색): mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감 투포인터: left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음 이분탐색(이진탐색, Binary Search) 투 포인터(Two Pointer) 시간복잡도 O(log N) O(N) 가정 데이터가 정렬되어 있어야 함 X 방식 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감 양끝단에서 한칸씩 이동하면서 알맞는 값을 찾음 -참고문헌 더보기 okky.kr/article/548.. 2021. 4. 18. adjacency matrix로 구현된 graph를 DFS할 때 time complexity Question. Answer. C 2021. 2. 14. Q. 문자열을 뒤집는 모든 방법 Q. 문자열 뒤집는 방법을 아는 대로 말하면? 이러한 질문을 면접 때 받은 적이 있다.정말 아는 대로 말하면 되는데, 당시에 투포인터 solution을 말하지 못했다. java, python 등 대부분 문자열을 뒤집는 함수가 내장되어 있는데, 안에를 뜯어보면 투포인터로 구현되어 있다. 그리고 나중에 다른 지원자들과 복기를 했을 때, 투포인터 solution을 말한 사람이 거의 없었다.또, 지원하는 언어의 특징에 맞게 대답한 사람도 거의 없었다. -출제 의도1) 간단한 알고리즘조차 잘 구현 못하는 지원자는 거르고 싶다2) 지원하는 언어에 어울리는 해결방식으로 이 간단한 문제를 해결하는지 보고 싶다. -고득점 비결1) inplace로 뒤집을 수 있는 방법 말하기(=투포인터 이용 solution)2) 지원하는.. 2021. 2. 1. 최단경로 알고리즘 (1) - 다익스트라 알고리즘 *최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 *최단경로 알고리즘의 종류 1) 다익스트라 알고리즘 2) 플로이드 워셜 알고리즘 3) 벨만 포드 알고리즘 코딩테스트에 자주 나오며 면접에서도 꼭 알아둬야 하는 개념이다. *최단경로 문제 형태 Q. 한 지점에서 다른 특정 지점까지의 최단 경로(거리, 시간, 비용, etc)를 구해야 하는 경우 Q. 모든 지점에서 다른 모든 지점까지 최단 경로(거리, 시간, 비용, etc)를 모두 구해야 하는 경우 각 주제에 대해 다음 순으로 포스팅하려 한다. 1) 다익스트라 알고리즘 -> 2) 플로이드 워셜 알고리즘 -> 3) 벨만 포드 알고리즘 *다익스트라 알고리즘 1. 정의 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른.. 2021. 1. 16. 이전 1 다음 728x90
