남겨진 자들의 외로운 사투... 박선환,
박유은, 신채린, 오지수, 장현준, 홍주표
매주 목요일 오후 8시에 미팅을 합니다.
오프라인 또는 온라인 미팅을 합니다.
- 책 <파이썬 알고리즘 인터뷰>을 한 챕터씩 풀고
- 프로그래머스의 카카오 블라인드 테스트 한 문제씩 도전해봅니다.
- 해당 문제 폴더에 소스 코드를 저장하고 Github Repository에 푸시합니다!
누구든 스터디에 참여하고 싶으신 분은 멤버들에게 연락해주세요:wink:
한글로문제이름띄어쓰기없이_내이름.확장자명
오답노트 등 문제 풀면서 느낀 점을 적어서 공유해주세요:kissing_heart:
git commit명령어로 vi 창에서 편집합니다.(예시)
왜 이 문제가 이분탐색인가? 걸린 시간: 1시간 30분 우선 구하고자 하는 값이 모든 사람이 심사를 받을 수 있는 시간의 최솟값이다. 심사에 걸리는 시간, 남은 사람(n)의 최대 범위가 1,000,000,000까지 된다. 시간이 주어지면 각 심사관마다 심사할 수 있는 사람의 수를 구할 수 있다. 해당 시간에 심사할 수 있는 사람의 합(passed)이 주어진 n값(심사 받아야하는 사람의 수)보다 크면 답이 될 수 있다. 시간을 0분(주어진 시간의 단위는 분이다)부터 1분씩 늘려나가면 언젠가 심사가능 한 사람의 수가 n값보다 커진다. 따라서 답은 0과 무한히 큰 수 사이에 있을 것이다. 하지만 위와 같은 방법은 만약 답이 1,000,000,000분이라면 1,000,000,000번 계산해야하므로 효율적이지 못하다. 효율적인 방법 중 하나가 이분탐색이다. 최소 시간(0)과 최대 시간의 중간값을 구해 조건을 만족하면 더 작은 값(시간의 최솟값을 구하라고 하였으므로)을 찾고 조건을 만족하지 못한다면 더 큰 값을 찾는다. 이 문제에서 최대 시간은 주어진 인원을 심사관이 똑같이 나눠 심사했을 때라고 가정하고 풀었다. 최대 시간 = (남은 인원 수 // 심사관 수) * (각 심사관마다 소요 시간) 조건을 만족한다면 최솟값을 중간값으로 치환해 다시 중간값을 구하고 조건을 만족하지 못한다면 최댓값을 중간값으로 치환해 다시 중간값을 구한다. 최솟값이 최댓값보다 커질 때까지 반복한다. 0 ----------------------------- 25 ----------------------------------------------- 51 25 ------------------------ 38 ------------------- 51 25 ------------ 31 -------- 38 25 ---- 28 ---- 31 28 -29- 31 28
박상길 저, 책만
책에 나온 LeetCode 문제들을 열심히 풀어봅니다.
- 네트워크 딜레이 타임
- K 경유지 내 가장 저렴한 항공권
- 이진 트리의 최대 깊이
- 이진 트리의 직경
- 가장 긴 동일 값의 경로
- 이진 트리 반전
- 두 이진 트리 병합
- 이진 트리 직렬화 & 역직렬화
- 균형 이진 트리
- 최소 높이 트리
- 정렬된 배열의 이진 탐색 트리 변환
- 이진 탐색 트리(BST)를 더 큰 수 합계 트리로
- 이진 탐색 트리(BST) 합의 범위
- 이진 탐색 트리(BST) 노드 간 최소 거리
- 전위, 중위 순회 결과로 이진 트리 구축
- 배열의 K번째 큰 요소
- 트라이 구현
- 팰린드롬 페어
- 리스트 정렬
- 구간 병합
- 삽입 정렬 리스트
- 가장 큰 수
- 유효한 애너그램
- 색 정렬
- 원점에 K번째로 가까운 점
- 이진 검색
- 회전 정렬된 배열 검색
- 두 배열의 교집합
- 두 수의 합 II
- 2D 행렬 검색 II
- 싱글 넘버
- 해밍 거리
- 두 정수의 합
- UTF-8 검증
- 1비트의 개수
- 최대 슬라이딩 윈도우
- 부분 문자열이 포함된 최소 윈도우
- 가장 긴 반복 문자 대체
- 주식을 사고팔기 가장 좋은 시점 II
- 키에 따른 대기열 재구성
- 태스크 스케줄러
- 주유소
- 쿠키 부여
- 과반수 엘리먼트
- 괄호를 삽입하는 여러 가지 방법
- 피보나치 수
- 최대 서브 배열
- 계단 오르기
- 집 도둑
- 해시맵 디자인
- 보석과 돌
- 중복 문자 없는 가장 긴 부분 문자열
- 상위 K 빈도 요소
- 두 수의 합
- 빗물 트래핑
- 세 수의 합
- 배열 파티션 I
- 자신을 제외한 배열의 곱
- 주식을 사고팔기 가장 좋은 시점
- 팰린드롬 연결 리스트
- 두 정렬 리스트의 병합
- 역순 연결 리스트
- 두 수의 덧셈
- 페어의 노드 스왑
- 홀짝 연결 리스트
- 역순 연결 리스트 II
- 유효한 괄호
- 중복 문자 제거
- 일일 온도
- 큐를 이용한 스택 구현
- 스택을 이용한 큐 구현
- 원형 큐 디자인
- 원형 데크 디자인
- k개 정렬 리스트 병합
- 유효한 팰린드롬
- 문자열 뒤집기
- 로그 파일 재정렬
- 가장 흔한 단어
- 그룹 애너그램
- 가장 긴 팰린드롬 부분 문자열
매주 한 문제씩 격파해 나가자(링크)
- 비밀지도
- 다트 게임
- 캐시
- 셔틀버스
- 뉴스 클러스터링
- 프렌즈4블록
- 추석 트래픽
- n진수 게임
- 압축
- 파일명 정렬
- 방금그곡
- 자동완성
- 추후 수정