1. 이분탐색이란 ? 이분 탐색(Binary Search)은 정렬된 배열에서 값을 찾는 효율적인 탐색 알고리즘배열을 절반으로 나누면서 목표 값을 찾기 때문에 시간 복잡도가 O(log n) : 조건은 배열이 반드시 정렬되어 있어야 한다는 점 !! 2. 이분 탐색 과정 배열의 중간 값을 확인한다.중간 값이 찾으려는 값보다 크면, 왼쪽 절반을 탐색한다.중간 값이 찾으려는 값보다 작으면, 오른쪽 절반을 탐색한다.값을 찾을 때까지 이 과정을 반복한다. 3.이분 탐색의 JavaScript 구현 JavaScript로 이분 탐색을 구현하는 방법은 두 가지가 있다. 재귀 함수와 반복문을 사용하는 방식 (1) 재귀를 이용한 이분탐색 구현 function binarySearch(arr, target, start = 0, ..
자료구조&알고리즘
A : DFS/BFS 가 뭔지 알아 ? Me : 그럼 ! DFS 는 그래프를 깊이 우선 탐색하는 것이고 , BFS는 그래프를 너비 우선 탐색하는거잖아 ! A: 자세히 설명해봐 뭔소린지 모르겠어 ! Me : DFS 는 특정 노드에서 시작해서 특정 노드와 연결된 모든 노드를 탐색한 후 다음 노드를 탐색하는거고 BFS는 특정 노드에서 시작해서 특정 노드와 인접한 노드들을 탐색한 후 그 다음 인접한 노드를 탐색하는거야 !! 그래프를 머리에 떠올려보면 DFS는 수직방향으로 BFS는 수평방향으로 진행한다고 생각해 나는 ! A: 오 ! 그럼 DFS/BFS 관련 문제는 다 풀수있겠네 ? Me: .... 아니 현재 나는 DFS 와 BFS의 개념은 알고 있지만 이를 이용한 문제는 잘 풀지 못한다. 문제를 읽고 어떤걸 사용..
Stack 에 대해 공부를 하고 Stack 문제로 유명한 유효한 괄호쌍 문제를 풀어보았다. 사실 예전에 비슷한 문제를 풀어본 적이 있어서 수월하게 풀 수 있을 줄 알았는데 1시간정도가 걸렸던 것 같다... 너무 기만했던 거 같고 다시 한번 풀어보면서 정리를 해봐야겠다. 문제는 코드스테이츠에서 제공하는 코플릿 문제를 풀었다. ( 아래에 해결과정과 느낀점이 있습니다 ) 문제 설명 입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요. 입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다. 1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다. 2. 열린 괄호는 올바른 순서대로 닫혀야만 한다. 3. 모든 닫힌 괄호는 그에 상응하는 같은 타입..
오늘은 자료구조 중 Stack 과 Queue에 대해 학습했다 . 데이터를 효과적으로 관리하기 위해 자료구조가 쓰이고 데이터의 특징을 잘 분석하고 사용해야 자료구조를 잘 활용할 수 있다. 사실 대학교를 다니며 귀에 딱지가 지도록 자료구조에 대해 배웠었는데 그 때에는 자료구조를 왜 써야하는지 크게 와닿지 않았던 것 같다 . 하지만 오늘 다시 복습을 하면서 자료구조의 필요성에 대해 깨달은 것 같다 !! ㅎㅎ Stack ? 데이터를 순서대로 쌓는 자료구조 입력과 출력이 하나의 방향, 스택의 최상단에서만 이루어지는 제한적 접근 LIFO (Last In First Out) 또는 FILO (First In Last Out) 데이터를 삽입 ( Push) 데이터를 추출 ( POP) 예 ) 브라우저의 뒤로가기 앞으로가기 ..
