2020 동계 모각코 1주차 목표와 회고

30 Dec 2020

Reading time ~1 minute

1주차 (12월 30일)

목표

인프런 파이썬 강의 1시간 수강
수강 후 내용 실습
알고리즘 <이진탐색> 문제풀기 (백준 2805번, 백준 1920번)

회고

인프런 파이썬 강의 40분 수강
배운 내용 jupyter notebook을 사용해서 실습
알고리즘 <이진탐색> 문제 : 백준 2805번("나무 자르기") -> 난이도 : 실버3

해결 방법 : 나무의 길이들의 중간값을 잘라본 후 필요한 나무의 길이보다 길다면 자르는 부분을 중간보다 높이고, 필요한 나무의 길이보다 작다면 자르는 부분을 중간보다 내리면서 나무를 자를 위치를 찾는다.

코드일부

while(left <= right) { // 이분탐색
			sumOfLength = 0;
			
			int mid = (left + right) / 2;
			
			for(int i = 0; i < tree.length; i++) {
				
				long cutting;
				
				if(tree[i] > mid) {
					cutting = tree[i] - mid;
				}
				else {
					cutting = 0;
				}
				
				sumOfLength += cutting;
			}
			
			if(sumOfLength >= length) { // 자른 길이들의 합이 필요한 나무의 길이보다 같거나 클 경우
				left = mid + 1;
				answer = (answer < mid)? mid : answer;
			}
			else if(sumOfLength < length) { // 자른 길이들의 합이 필요한 나무의 길이보다 작을 경우
				right = mid - 1;
			}
		}

알고리즘 <이진탐색> 문제 : 백준 1920번 ("수 찾기") -> 난이도 : 실버4

해결 방법 : 우선 이분탐색을 하기 위해서는 A 집합에 있는 수들을 오름차순으로 정렬을 한다. 그리고 내가 갖고 있는 숫자를 하나씩 이분탐색을 이용해서 A집합에 있다면 1을 없다면 0을 출력한다.

코드일부

for(int i = 0; i < sizeOfNumber; i++) { // 이분탐색
			
			int mid;
			int left = 0;
			int right = A.length - 1;
			
			while(left <= right) {
				
				mid = (left + right) / 2;
				
				if(number[i] == A[mid]) {
					System.out.println(1);
					break;
				}
				else if(number[i] > A[mid]) {
					left = mid + 1;
				}
				else if(number[i] < A[mid]) {
					right = mid - 1;
				}
				
				if(right < left) {
					System.out.println(0);
				}
				
			}
			
		}