problem_solving2 Egg Drop Puzzle Egg Drop Puzzle http://datagenetics.com/blog/july22012/index.html 달걀이 2개 있을 때 100층 높이의 탑의 달걀이 떨어지는 어느 장소를 달걀을 최소 횟수로 떨어뜨리며 찾는 문제이다. 달걀이 1개 밖에 없다고 생각해보자 1층 부터 100층까지 모든 층에서 달걀을 던져 볼 수 밖에 없다. 달걀이 무한개라고 생각해보자 2진 탐색으로 했을 때 최소 횟수로 알 수 있다. log2 100 = 6.644 .. 정도가 된다. 이 횟수보다 최소로 알아 낼 수는 없다. 돌아와서 달걀이 2개 있다고 생각해보자 10칸씩 전진한다고 생각해보자 100층에서 달걀이 깨진다면 10,20, …, 90, 100 에 떨어뜨려보고 10번만에 알 수 있다. 그런데 달걀이 99층에서 깨진다.. 2020. 5. 30. LeetCode 1. Two Sum https://leetcode.com/problems/two-sum/ 문제 이해 input / output input: int array, int output: 정답쌍의 index 내용 첫번째로 주어진 int 형 배열 속에서 서로 다른 두 수를 더해 두번째로 주어진 수가 되는 쌍의 index를 반환한다 제약조건 정답은 유일하다 같은 수를 2번 사용할 수 없다 의문 input 배열의 크기는 얼마나 크게 들어올까 ? 0과 음수도 input으로 들어올 수 있을까 ? 같은 수가 2번 이상 들어올 수 있을까 ? O(N^2) broute-force 방법으로 접근하면 얼마나 걸릴까요? 간단하게 이중 loop를 수행한다면 N^2 의 시간복잡도로 해결 가능합니다. 첫번째 수(i) 를 고르고 i+1 번째 수부터 두번째 수.. 2020. 4. 30. 이전 1 다음
