[언그래머] 코딩테스트 챌린지_22_순위 검색 (알고리즘: 이분 탐색) 카카오 기출 문제, 프로그래머스 Lv.2

안녕하세요, 여러분~!

송아지할때 송아 김송아입니다.

 

 

슬슬 은행 채용시즌이 다가오고 있죠! (사실 이미 다가온 것 같긴 한데)

요즘 은행들도 당연하게 코딩테스트를 트렌드에 맞게 출제하고 있어서!!

최신 트렌드를 우리가 알아둬야 할 것 같으니🙈

 

 

응 2024년에 2024년 트렌드 공부하는 나 @퍼블리

 

 

 

오늘 추천드리고 싶은 알고리즘은 바로!

요즘 들어 많이 들리고 있는 유형이죠,

이진 탐색 (Binary search) 입니다.

 

 

 

이진 탐색은 효율적인 업앤다운(Up & Down) 이라고 볼 수 있습니다.

술자리에서 업앤다운 게임 해본사람 손?

 

 

이건 무슨 게임이여...? 007빵...? 공동묘지ㅣ...? @응사

 

 

분할과 정복의 쉬운 예제로 나오기도 하는 알고리즘이죠.

위키 백과에서 소개하는 예시가 저는 개인적으로 마음에 듭니다!

사전을 찾을 때 사전을 펴서 찾는 단어가 없으면, 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하면 된다는 겁니다.

 

 

 

그럼 눈치가 빠르신 분들은 눈치 채셨나요?

이진 탐색은 자료가 순서에 따라 정렬되어 있어야 한다는 것이 중요합니다.
아니, 그래야만 의미가 있습니다!

텍스트보다 그림이 최고죠? 위로 올라가서 gif를 다시 한번 보고 오세요!!

 

 

 

 

 

그래서 오늘의 문제는 대망의,,2022 카카오 블라인드 코딩테스트 문제입니다.

 

'순위 검색'이라는 문제에요!

 

프로그래머스

 

 

이 문제는 들어가보시면 아시겠지만, 효율성 테스트를 채점하는 문제입니다.

정확도 테스트도 있지만 그건 솔직히 그냥 테스트 케이스 통과하는 거라서! 대부분 효율성 테스트가 문제라고 보시면 됩니다ㅎ.ㅎ

 

문제를 풀어보시면 느낌적으로 재귀함수를 돌리고 싶다는 생각이 드실거에요.

맞습니다. 이진 탐색은 그냥 고민하면 재귀함수로 풀 수 있을거에요! 당연합니다!

대신 그럼 효율성 테스트에서 떨어질거라는 함정^_^

 

 

ps. 지난 번에도 말씀드렸죠. 재귀함수로 풀 수 있는 문제들이 효율성 테스트가 있다면 대부분 걸릴거라구요!
그럼 그럴 때 해답은 DP(동적 프로그래밍)으로 풀면 된다고 했었죠?👀

 

 

 

이번 문제는 턱별히 카카오 문제 해설 링크도 같이 남겨두도록 할게요.

궁금하신 분들은 아래 링크에서 해설을 참고해주세요!

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 - tech.kakao.com

 

 

+ 참고로, 최근 카카오 문제 뿐 아니라 코딩테스트 (알고리즘) 문제는 이것보단 난이도가 낮아졌습니다.

대신 SQL 테스트가 어려워졌죠 하하하하하하! 쿨럭쿨럭

 

 

-

 

 

요즘따라 시간이 너무 순삭하는 느낌이 들어요.

아침 찰칵, 점심 찰칵 이런 느낌으로 사진 찍는 듯 지나가버리는,,

 

다들 하루하루 더 현재에 집중하시는 날들이 되시길 바라며!

그럼 우리는 눈깜짝하면 돌아올 금요일에 만나요🩵