이진탐색
-
알고리즘) 2019 카카오 개발자 겨울 인턴십, 징검다리 건너기알고리즘/프로그래머스 카카오 2020. 5. 7. 00:24
2019 카카오 개발자 겨울 인턴십 징검다리 건너기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 투 포인터 알고리즘으로 풀다가 효율성 13번만 시간 초과가 뜨길래 이진 탐색으로 풀었다. 이진탐색이기에 left, mid, right를 무엇으로 잡을 것인지가 핵심이다. 1. 돌의 stepping 수(=건널 수 있는 사람의 수) 최소값, 최대값을 각각 left, right에 넣어준다. 2. while문을 돌면서 mid 값 (건널 수 있는 사람의 수 예상 답)과 비교하면서 건널 수 있을 경우에는 answer을 저장해주고 최소인 left를 mid+1로 저장..
-
알고리즘) 프로그래머스 BinarySearch, 징검다리알고리즘/프로그래머스 고득점 Kit 2020. 4. 25. 15:35
프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색) 징검다리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분 검색에서 mid값은 문제에서 요구하는 답으로 설정하는 것이 기본이다. 이 문제에서 원하는 답은 n개의 바위를 제거한 뒤 각 지점 사이의 거리의 최솟값이다. 따라서 left와 right, mid는 거리로 설정한다. 1. 돌위치를 돌면서 이전 돌과 거리를 비교한다. 2. 구한 거리가 가정 답안인 mid보다 작으면 최솟값이 mid가 될 수 없으므로 돌을 제거해준다. (counting을 해줌) 3. 거리가 크거나 같다..
-
알고리즘) 프로그래머스 BinarySearch, 입국심사알고리즘/프로그래머스 고득점 Kit 2020. 4. 24. 00:37
프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색) 입국심사 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분 검색에 대한 이해가 완전히 되지 않아서 다른 분들의 로직을 보고, '아! 이렇게 하는거였지' 느꼈다.. 갈길이 아직도 멀다... 제한사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.심사관은 1명 이상 100,000명 이하입니다. 제한사항을 따로 적은 이유는 주로 데이터 타입과 대략적인 ..
-
알고리즘) 프로그래머스 BinarySearch, 예산알고리즘/프로그래머스 고득점 Kit 2020. 4. 24. 00:06
프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색) 예산 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr (2020.04.24) 풀이1 이진 탐색(Binary Search)라는 생각없이 푼 풀이다. 사실 문제를 보고 이진 탐색을 써야지!! 이런 느낌이 안들어서 자연스럽게 푼 문제다. 로직은 아주 간단하다. 1. 예산의 액수에 따라 오름차순으로 도시를 정렬해준다. 2. 남은 예산으로 평균을 구했을 때 해당 도시의 예산 요청액이 더 적으면 허가해준다. 3. 만약, 요청한 예산이 남은 예산을 나눠줄 수 있는 금액보다 크다면 남은 총액..