[Python] 백준 알고리즘 1654번 : 랜선 자르기
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 👩💻문제 이해 만들 수 있는 랜선의 길이 (target) 이 [1,2,3, ..., 주어진 랜선의 최대값] 배열을 이분탐색을 이용해 (주어진 랜선 길이 // 배열의 중간값)의 합이 K와 같아질 때 까지 반복하면 된다. 정렬된 배열에서 각각의 (주어진 랜선 길이 // start와 end의 중간값(mid)) 의 합(= cnt)이 k와 같아질 때까지 이분탐색 알고리즘을 반..
[Algorithm] 이분 탐색 / 이진 탐색 (Binary Search) 알고리즘
🌵이분 탐색(Binary Search) 이란? - 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 원하는 값(target)을 탐색하는 방법 - 이 때 리스트(배열)는 항상 정렬되어 있어야 한다 시간 복잡도 : O(log n) 🌵문제 해결 방법 이분 탐색 알고리즘은 변수 3개 (start, mid, end)를 사용해 값을 탐색 간단하게 말하면 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분 탐색의 과정 변수 이름에서도 알 수 있듯, start의 초기 값은 리스트(배열) 시작 위치 (0) mid 는 start와 end의 중간 지점 ((start + end) // 2) end 는 리스트(배열) 마지막 위치 (len(list) - 1) 1. 리스트(..
[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 👩💻문제 이해 list를 이용해 각각의 원소들을 비교하면 쉽게 풀릴 문제지만, 시간초과가 난다. 따라서 처음 주어지는 배열을 오름차순으로 정렬해 이분 탐색 알고리즘을 이용해 풀었다. 👩💻List만 사용 : 시간초과💀 import sys n = int(input()) nli = sys.stdin.readline().split() m = int(in..
[Python] 백준 알고리즘 1436번 : 영화감독 숌
https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 👩💻문제 이해 처음 문제를 풀 때 '666'에 0부터 1씩 커지면서 수를 합치면 풀릴꺼라 생각하고, # prevnum = 666 # cnt = 1 # i = 1부터 더해지고, # while cnt = int(input()) # int('666' + 'i') > int('i' + '666') and int('i' + '666') > prevnum => nextnum = int('i' + '666..
[Python] 백준 알고리즘 7568번 : 덩치
https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 👩💻문제 이해 1. 모든 사람들간의 비교를 하는데 몸무게는 몸무게 끼리, 키는 키끼리 비교 2. 둘 다 큰 사람이 더 큰 덩치를 가지는 것이다. 👩💻dictionary형태와 반복문 사용 : 성공🌈 dic = {} li = [] for i in range(int(input())): kg, cm = input().split() li.append([int(kg), int(cm)]) di..
[Python] 백준 알고리즘 2231번 : 분해합
https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 👩💻문제 이해 N의 생성자는 N보다는 작지만 N+(각 자리 수의 합) 이므로 0부터 하나씩 확인 하는 것보다 N부터 1씩 줄어들며 확인하는 것이 나을 것이라 생각했다. 👩💻reversed(N)을 범위로 하는 반복문 사용 : 성공🌈 n = int(input()) res = [] for i in reversed(range(n)): sum = 0 sum += i for ..