점심시간에 점심대신 쇼파에서 잠을 잤다. 1시간 뒤 알람소리에 눈을 떴지만 졸음이 쉽게 가시지 않았다. 어제 11시에 잤는데도 졸린 것 보면 알게 모르게 수면부족이 있었던 모양이다. 생각해보니 부트캠프를 진행하면서 생기는 긴장감 때문인지 주말에도 일찍 일어났으니 피로가 쌓일만도 했다. 힘겹게 일어나서 페어와 코드리뷰를 하고, 창문을 열고나니 다시 정신이 맑아졌다.
이번주엔 알고리즘을 배우고 있는데 거의 하루종일 문제를 푸는데 시간을 쓰고 있다. 탐욕 알고리즘이나 구현문제를 만났을 땐 그문제에 대해 집중할 수 있어서 하루가 금방 지나가는 것처럼 느껴졌다. 거스름돈을 주는 방식처럼 개념도 익숙했다. 어떤 방식으로 문제를 풀어야하는지 느껴졌고, 바로 풀 수 있었다.
하지만 탐색알고리즘과 순열을 다루는 문제는 어떻게 풀어야할지 막막했다. 방법을 찾아보고, 새로운 개념을 배우고, 답을 보고, 동영상 강의를 들어봐도 익숙하지가 않다.
문제가 어려운게 아니라 아직 낯설기 때문에 풀지 못하는 것이라고 생각하면서도 자꾸만 조바심이 들어서 마음한켠이 무거워졌다. 그래서 오랜만에 블로그에 글을 남기기로 했다.
완전 탐색 알고리즘(Brute-Force Algorithm)
숫자로 된 자물쇠의 비밀번호를 까먹었을때 우리는 0000부터 9999까지 모든 경우의 수를 하나씩 해보면서 찾아낼 수 있다. 완전 탐색 알고리즘도 이와 비슷하다.
완전 탐색 알고리즘은 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법으로 공간복잡도와 시간복잡도의 요소를 고려하지 않기 때문에 비밀번호가 9999여서 10000번 시도하게 될 수도 있을거라는 것을 알면서도 달리 다른 방법이 없을 때 사용된다.
완전 탐색 알고리즘을 사용할 수 있는 방법에는 for문과 if문으로 일일이 모든 경우를 찾을 수도 있지만 순열과 재귀를 이용하여 찾을 수도 있다.
<완전 탐색 알고리즘의 종류>
순차 검색 알고리즘 (Sequential Search),
문열 매칭 알고리즘 (Brute-Force String Matching),
선택 정렬 알고리즘 (Selection Sort),
Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS),
버블 정렬 알고리즘 - Bubble Sort,
동적 프로그래밍 - DP(Dynamic Programing) 등
이진 탐색 알고리즘(Binary Search Algorithm)
우리가 구글에 검색을 하면 수많은 정보들 중에서 관련성이 높은 정보들을 찾아서 보여준다.
이때 찾는 과정은 탐색 알고리즘을 사용한다.
탐색 알고리즘은 크게 3가지 Linear Search Algorithm(선형 탐색 알고리즘), Binary Search Algorithm(이진 탐색 알고리즘), Hash Search Algorithm(해시 탐색 알고리즘)이 있는데 그중
이진 탐색 알고리즘을 배웠다.
탐색이란 데이터의 위치를 찾는 작업이다. 이진 탐색 알고리즘은 전체 값 집합이 정렬되어 있는 경우에 사용가능하며, 매 시도마다 탐색 범위가 절반씩 줄어들어서 값 집합이 아주 커도 빠르게 답을 찾을 수 있다는 장점이 있다.
int[] numbers = {5,20,35,42,53,67,71,94,127,155,182,200};예시를 들어서 설명해보자면, 위와 같은 배열이 있고 그중에서 182가 있는지 찾고 싶을 때 인덱스 0부터 numbers.length-1 까지 차례대로 확인해서 알아내는 방법이 있고 그렇게하면 11번만에 찾을 수 있다.
이진 탐색 알고리즘을 사용하면 아래와 같은 방식으로 이루어진다.
- 정렬된 배열의 가장 중간 인덱스를 지정한다. (6번째인 67을 지정)
- 찾으려고 하는 값이 지정한 중간 인덱스의 값인지 확인한다. (67==182인지 확인)
- 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다. (67<182)
- 값이 있는 부분과 값이 없는 부분으로 분리합니다.
{5,20,35,42,53,67}, {71,94,127,155,182,200}- 값이 있는 부분에서 다시 1단계부터 반복합니다.
한번더 반복하면 127이 기준이되어 확인하고 분리하고, 또 반복하면 182를 만나게 되므로 3번만에 찾을 수 있다.
이진탐색 알고리즘을 사용하려면 정렬이 되어 있어야 하니 정렬 알고리즘도 살펴봐야 할 것 같고, 재귀도 확실하게 쓸 줄 알아야 하고, 기본적인 수학도 알아야 탐색 알고리즘 문제를 수월하게 풀 수 있을 것 같다.
유튜브로 게시판 만들기 프로젝트는 유튜브가 5년전에 만들어진 것 이라서 부트스트랩 라이브러리의 스펙이 많이 바껴있다보니 따라해도 결과가 제대로 나오지 않고 있다. 이대로 강행해도 끝까지 완성할 수 있을지 미지수다보니 손이 잘 가지 않는다.
약간의 휴식과 앞으로 나아갈 방향을 다시 한번 점검해서 목표를 재설정해야 할 것 같다.
