이진 탐색

[프로그래머스 Lv.4] N으로 표현 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43236풀이아래와 같이 먼저 단순하게 생각할 수 있는 방법으로 풀이해 보았다. 하지만 역시나 시간 초과로 인해 실패하였고, 이는 아래 풀이처럼 완전 탐색을 사용했을 때 탐색해야 하는 데이터가 너무 많기 때문이다.징검다리를 이루는 돌의 수가 최대 5만개이고, 제외할 수 있는 돌의 수도 5만 개 이하기 때문에 최악의 경우 5만 개 중 2만 5천 개의 돌을 제외하는 조합을 모두 계산해야 한다. 이는 정말 말도 안 되는 수이다. (단순히 생각해 봐도 50000!/(50000-25000)! 이니까 50000부터 25000까지 곱한 값이다. 대충 3만을 25000번 곱했다고 봐도 (3*10^4)^2..

[프로그래머스 Lv.2] 순위 검색 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72412  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2 문제라는 레벨 분류가 무색하게 문제 풀이를 위한 방법을 고민하는 게 너무나 어려웠다. 구현 난이도로만 따지면 레벨 2가 맞지만 문제 해결을 위한 방법을 생각해 내는 것 자체가 어려워 체감 난이도가 훅 올라가지 않았나 싶다. 처음에는 간단히 생각해서 전체 데이터를 순회하면서 조건에 일치하는 사람들의 수를 카운트하는 방법을 고민했으나, 데이터의 수를 보고 다른 방법을 생각해야 한..

(C++) 백준 1654번 - 랜선 자르기

문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 매개 변수 탐색을 사용해 풀이하였다. 매개 변수 탐색은 다음의 두 조건을 만족할 경우에 사용할 수 있다. 최적화 문제를 결정 문제로 변경할 수 있는지? 위의 결정 문제로 얻어진 함수가 감소 혹은 증가함수인지? 여기서는 N개를 만들 수 있는 최대의 랜선을 구하는 최적화 문제를 랜선의 길이가 X일 때 랜선의 개수가 N개 이상인가 아닌지 구하는 결정 문제..

(Python) 백준 1920번 - 수 찾기

문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 처음에 이진탐색 구현 시에 인덱스를 사용하지 않고, python의 리스트 슬라이싱을 활용한 풀이를 사용했는데 시간 초과가 발생하였다. 리스트 슬라이싱은 지정한 범위의 모든 리스트의 원소를 복사하여 새로운 리스트를 만드는 과정을 거친다고 한다. 그렇기 때문에 시간 초과가 발생한 것이다. 따라서 아래 풀이처럼 슬라이싱한 리스트를 넘겨..