코딩테스트 - 패스트캠퍼스 챌린지 27일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 이분 탐색 (Binary Search)

학습 후기
이분 탐색
Left 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스
Right 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스
Reuslt 탐색한 x의 위치
탐색 목표 X이하의 원소 중에 가장 오른쪽에 있는 원소

이분 탐색 자주 하는 실수
1. 입력된 배열에 바로 이분 탐색을 하는데 정렬을 하지 않는 경우
2. L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우
3. L, R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우

이번 강의에서 푼 문제
https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

생각의 흐름
B에서 A[i] 이하 원소들을 빨리 찾기
이걸 빨리 해주는 게 뭐가 있을까?라고 생각해보기
이분 탐색을 사용하자.
전제 조건은 정렬이 되어 있어야 한다.
이를 위해서 전제 조건(정렬된 상태) 만족
이제 B가 정렬되어 있으니까 원하는 원소를 빠르게(log M) 탐색이 가능한다.
A의 원소마다 이분 탐색 (N logn M)

시간 공간 복잡도 계산하기
1. B 배열 정렬 한 번 > O(M log M)
2. 모든 A의 원소마다, B 배열에 대해 이분 탐색 필요 > O(N log M)
3. 총 시간 복잡도: O((N + M) log M)

문제를 풀기 전 항상 제약조건을 먼저 확인하고, 다음 시간 공간 복잡도를 계산하여 짤 가치가 있는 코드인지 알아보고 코드 작성에 들어간다. 코드를 써 내려가기 전에 주석으로 한 줄 한 줄 문제에서 필요로 하는 게 무엇이고 코드 록 작성해야 할게 무엇인지 적는다. 이제 코드로 구현하면서 함수화 할 수 있는 게 무엇인지 확인하고 할 수 있으면 따로 함수로 구현한다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.