징검다리 1. 문제유형 이분탐색 2. 자료구조 distance (int): 목적지 거리 rocks (list): 바위 위치를 저장한 리스트 left, right (int): 바위별 거리의 최소값, 최대값 mid (int): 정답으로 지정한 바위별거리. left, right의 중간값 current (int): 현재 바위 위치 diff (int): 현재 바위 위치를 기준으로 다음 바위까지의 거리 cnt (int): 제거한 바위 수 3. 해결과정 최대 범위가 10억이므로 이분탐색을 위해 rocks를 정렬 후 시작한다. 이분탐색을 지정하기 위해 최소, 최대거리를 지정한 후 mid를 계산한다. mid가 정답이이라고 가정한 뒤, 제거한 바위 수가 n과 같은지 판단한다. 바위를 하나씩 꺼내가며 diff를 계산하고, ..

12015 가장 긴 증가하는 부분 수열2 1. 문제유형 Binary Search, DP 2. 자료구조 lis (list): 최장 부분 순열을 저장하는 리스트 a (int): n개의 입력값을 저장하는 리스트 3. 해결과정 입력받은 값을 a에서 하나씩 꺼낸다. lis가 비어 있으면 꺼낸 값을 추가한다. 비어있지 않고, lis[-1] < num이면 꺼낸 값을 추가한다. 꺼낸 값이 lis의 마지막 값보다 작으면 이분탐색으로 들어갈 index를 찾고 덮어씌운다. 반복이 끝나면 lis의 길이를 출력한다. import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) a = list(map(int, input().split()..

1. 입국심사 1.1. 문제유형 이분탐색 1.2. 자료구조 times (list): 심판관별 심사시간 left, right (int): 최소 시간, 최대 시간 mid (int): 정답으로 지정한 left, right의 중간값 cnt (int): mid 시간안에 완료한 승객 수 1.3. 해결과정 구하고자 하는 것은 최소 시간이다. 이분탐색을 사용하여 정답 시간을 설정 후 지정한 시간안에 완료되는 지를 구한다. left, right 지정 후 left

2470 두 용액 1. 문제유형 Binary Search Two Pointer 2. 자료구조 l (int): 첫 번째 원소 인덱스 r (int): 마지막 원소 인덱스 flag (boolean): 탐색 여부를 결정하는 변수 3. 해결과정 시작하기 전, 정렬을 수행한다. 만약 첫 번째 값과 마지막 값이 모두 양수라면, 가장 작은 두 값을 출력한다. 만약 첫 번째 값과 마지막 값이 모두 음수라면, 가장 큰 두 값을 출력한다. 만약 첫 번째 값과 마지막 값의 부호가 다르다면, 탐색을 수행한다. 탐색과정은 flag and l < r동안 반복한다. sum의 절대값이 answer 값보다 작다면 answer에 sum을 저장하고, a,b = l,r를 저장한다. sum이 0보다 작다면 용해값을 키우기 위해 왼쪽값을 증가시..

2805 나무 자르기 1. 문제유형 Binary Search 2. 자료구조 left (int): 가장 작은 트리의 높이 right (int): 가장 높은 트리의 높이 mid (int): 트리의 중간 높이 3. 해결과정 ⭐ 실수한 점) 트리의 높이가 최대여야 나무를 가장 적게 가져간다. 따라서, 자른 나무 길이가 M보다 작을 경우 right의 크기를 감소시킨다. 반대로 자른 나무 길이가 M보다 클 경우, left 크기를 증가시켜 나무를 절약한다. ⭐ list(tree-mid for tree in trees if tree-mid>0)으로 계산한 뒤, sum 계산 시 시간 초과가 발생했다. 따라서 바로 sum(tree-mid for tree in trees if tree-mid>0)으로 계산해주니 바로 통과했..

4. 1300 K번째 수 4.1. 문제유형 Binary Search 4.2. 자료구조 left (int): 각 행의 최소값 인덱스 == 1 right (int): 각 행의 최대값 인덱스 == n mid (int): (left+right)//2 == 중간값으로 탐색해 나갈 값 4.3. 해결과정 핵심 아이디어는 행별로 mid값보다 작은 값의 개수를 세는 것이다. 각 행의 값은 i의 배수이며 작은 값들의 개수는 최대 n, 최소 mid // i이다. left

프로그래머스 데이터 엔지니어링 강의 1주차를 수강하며 느낀점을 정리해보려고 합니다. 1️⃣ 주차 강의 내용 지난 1주차 강의 내용을 간략히 정리해보자면 다음과 같다. 새로운 분야를 학습하는 태도 남과 비교하지 않되, 나도 학습하면 저렇게 발전해나갈 수 있다라는 마인드를 갖자 무엇을 모르는 지 정의하고, 조사하여 정리한다. 작은 성공을 반복해서 자신감을 높이자. Agile 방법론에 익숙해질 것 빠르게 요구조건 파악 후 반영할 것 짧은 사이클을 빠르고 반복적으로 구현하는 것 중요 데이터 팀과 데이터 엔지니어의 가치 바람직한 데이터 팀 구조는 무엇일까? Centralized, Uncentrialized, Hybrid 일의 성공과 실패를 어떻게 측정할 것이냐? ⭐ 본인의 성공을 입증할 수 있는 지표 설정 ⭐ A..

1072 게임 1. 문제유형 Binary Search 2. 자료구조 중요한 점은 y/x * 100과 같이 실수형으로 계산 후 int로 바꿔줄 시 정확하지 않을 수 있다. 따라서 실수형 계산이 아닌, y * 100//x처럼 정수형 계산으로 바꿔 승률을 계산해야 한다. z (int): 초기 승리한 게임 수 y/전체 게임 수 x * 100 target (int): 승리한 경기수를 이분탐색하며 계산한 승률 left (int): 더해나갈 승리한 횟수의 최소값 right (int): 더해나갈 승리한 횟수의 최대값 mid (int): (left+right)//2 == 중간값으로 실제 더할 승리한 횟수 3. 해결과정 승리한 게임 수를 찾는 게 핵심이며, 범위는 0부터 x(10 ** 9)까지이다. 따라서 1부터 적용할 ..

2110 공유기 설치 1. 문제유형 Binary Search 2. 자료구조 cnt (int): 공유기 개수 left (int): 최소 거리 == 1 right (int): 최대 거리 == (마지막 집 좌표 - 첫 번째 집 좌표) mid (int): 공유기 간 거리 == (left + right) // 2 wifi (int): 공유기가 설치된 집 좌표 3. 해결과정 집 좌표 최대 크기가 10억이므로, 순차탐색이 아닌 이분탐색을 떠올려볼 것 공유기 간 최대거리를 찾는 것이 목적이므로 이분탐색 활용할 것 left

1. 2343 기타 레슨 1.1. 문제유형 Binary Search1.2. 자료구조 cnt (int) : 블루레이 개수 file (int) : 레슨을 저장한 파일 크기 mid (int) : 블루레이 크기 left (int) : 가장 작은 블루레이 크기 right (int) : 가장 큰 블루레이 크기1.3. 해결과정 가장 작은 블루레이 크기는 max(lesson), 최대 크기는 sum(lesson)이다. 주어진 m개의 블루레이에 강의를 저장하되, 블루레이 크기는 작을수록 좋다. 따라서 블루레이의 크기를 찾는 이분탐색 문제로 해결할 수 있다. left는 max(lesson), right는 sum(lesson)로 설정한다. left m: left = mid+1 else: answer = mid right = ..