📜 진행 내용
- [강의수강] 자료구조, 알고리즘 2-4 ~ 2-9
- [강의수강] 웹 퍼블리싱 정복반 1-1 ~ 1-5
💡 배운내용
< 자료구조, 알고리즘 >
2-7. 이진 탐색
이진 탐색 (Binary search)
: 찾고자하는 타겟을 처음부터 끝까지 순차적으로 탐색(단순 탐색/선형시간)해서 찾는게 아니라, 범위의 절반값부터 비교를 시작한다.
👉 예) 1~100에서 찾을 경우
1. 범위의 절반인 50부터 시작
2. 타겟과 절반값 50을 비교해서 타겟이 더 높으면 51~100 사이에서 찾기
3. 타겟과 절반값 50을 비교해서 타겟이 더 낮으면 1~49 사이에서 찾기
-
이진 탐색의 시간 복잡도 : O(logN)
- 1번 탐색시 범위가 반으로 줄어들기 때문에 N / 2
- 2번 탐색시 범위가 다시 반으로 줄어듦 → N / 4 =
- 3번 탐색시 범위가 다시 반으로 줄어듦 → N/8 =
- ······ k번 탐색시 범위가 반으로 줄어듦 →
▶ 횟수 시도시 정답을 찾을 수 있음
-
이진탐색은 리스트의 원소들이 정렬되어 있어야만 사용할 수 있다!
-
이진탐색은 단순 탐색보다 빠르고, 찾으려는 리스트의 원소 개수가 증가하면 상대적으로 더 빨라진다.
2-8~9. 재귀 함수
- 재귀 함수 : 자기 자신을 호출하는 함수!
-
사용하는 이유 : 재귀함수를 이용하면 간결하고 효율성 있는 코드로 작성할 수 있다.
-
사용시 주의 : 재귀는 (반복문 while 처럼) 탈출 조건을 만들어주어야 무한루프에 빠지지 않는다!
예시 코드)
function count_down(number) { **if (number < 0)** { // ** 이 조건이 없으면 음수 영역까지 계속 내려가서 반복됨. return; } console.log(number); // number를 출력하고 count_down(number - 1); // count_down 함수를 number - 1 인자를 주고 다시 호출한다! } console.log(count_down(60));
-
< 프로그래머스 - 코딩 테스트 >
-
오늘 프로그래머스 코딩 테스트 문제는 따로 풀지 못했는데, 같은 팀원분이 0단계의 양꼬치 문제 풀이 중 이해가 안가는 풀이가 있다고 해서 비트 연산자 <<, >> 에 대해 찾아보게 됐다.
-
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/120830
-
나의 풀이
function solution(n, k){ const kService = Math.floor(n / 10) return n * 12000 + (k-kService) * 2000 } -
문제의 다른 풀이
function solution(n, k) { // 음식 가격 const lamb = 12_000; const drink = 2_000; // 양고기를 10인분 이상 먹었다면 if (n >= 10) { // 10인분 당 음료수 하나 서비스 k -= (n / 10) << 0; } }-
풀이상
k -= (n / 10) << 0코드는 서비스될 음료수 갯수를 총 음료수 갯수에서 뺀다는 의미같은데,<< 0이 부분이 무슨 의미인지 정확히 몰랐다.
-
<<, >> 의 비트연산자에 대해 찾아본 결과 아래와 같이 정리되었다.
-
2진법 : a << b
-
10진법 : a * 2^b
-
a << 1
: 비트를 전부 왼쪽으로 1비트씩 이동
: 결과값은 처음 값에 2를 곱한 것 -
a >> 1
: 비트를 전부 오른쪽으로 1비트씩 이동
: 결과값은 처음값에 2를 나눈 것 -
a >> 0
: 비트를 이동시키지않음
: 결과값은 처음값에 1을 곱한 것
👉 다만 <<, >> 기호는 Int값으로만 표현되기 때문에, 소숫점 이하 자리는 버려지게 된다.
👉 결론적으로 << 0은 Math.floor()와 같은 기능을 하는 코드였다.
-
-
-
※ 아는 개발자분께 여쭤보니, 실제로는 많이 쓰이지 않는 연산자 기호이며, 속도는 좋을지 몰라도 가독성이 좋지 않다는 첨언을 받았다.
⁉️ 어려웠던 내용
- 재귀 함수
- 알고리즘 적용해서 문제 풀기..
❎ 한 번 더 공부할 내용
- 재귀함수, 이진탐색 복습, 문제 다시 풀어보기
🎯 문제와 해결
- 같은 팀원분이 물어본 문제에 대해, 비록 내가 기존에 알고있던 지식 선에서 설명은 못했지만, 자료를 찾아보고, 또 지인들의 조언을 듣고 정리한 내용을 그 팀원분께 공유하면서 나도 같이 공부하게 되어 좋았다.
🔗 출처
- 스파르타코딩클럽 - 자료구조, 알고리즘 강의
