목록coding (169)

이모저모

이진탐색 연습 - 랜선자르기(백준 1654)

문제: https://www.acmicpc.net/problem/1654 import sys k, n = map(int, sys.stdin.readline().split()) lines = [] for _ in range(k): line = int(sys.stdin.readline().rstrip()) lines.append(line) # 이분탐색을 시작할 초기 범위 설정 lt = 1 rt = max(lines) # 주어진 길이로 자를 경우 가능한 조각 수 반환하는 함수 def how_many(length): total = 0 for line in lines: pieces = line//length total += pieces return total answer = 0 # 이분탐색 while lt= n:..
coding/알고리즘,자료구조 2022. 2. 5. 14:44
이진탐색 연습 - 예산(백준 2512)

문제 : https://www.acmicpc.net/problem/2512 import sys # 입력값 받기 N = int(sys.stdin.readline().rstrip()) reqs = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.readline().rstrip()) # 이분탐색을 시작할 초기 범위 설정 lt = 0 rt = max(reqs) answer = 0 # 상한선에 따른 예산 총액 반환하는 함수 def how_much(limit): total = 0 for req in reqs: if req > limit: total += limit else: total += req return total # 이분탐색 while lt
coding/알고리즘,자료구조 2022. 2. 5. 14:18
이진탐색 연습 - 고정점 찾기(이코테)

이코테 28번 문제 고정점이란 수열의 원소 중 그 값이 인덱스와 동일한 원소를 의미. 주어진 수열에서 고정점이 있다면 고정점을 출력하라. + 궁금한 점 남병관 튜터님의 강의를 보니 hi (나는 right)라고 명명한 것을 지정하는 방식이 조금 달랐다. hi = N, 그리고 hi를 낮출 때는 hi = mid 로 잡았다. 사실 풀이의 흐름은 거의 비슷한 것 같은데, 그렇게 하면 더 효율적인 걸까? import sys # 입력값 받기 N = int(sys.stdin.readline().rstrip()) a = list(map(int, sys.stdin.readline().split())) # 고정점이 될 수 있는 범위 초기 설정 left = 0 right = N-1 # 궁금한 점 : 남병관 튜터님 코드에선 h..
coding/알고리즘,자료구조 2022. 2. 5. 11:41
이진탐색 연습 - 오름차순된 배열에서 특정 원소 개수 #bisect

이코테 27번 문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하라. 파이썬 내장 모듈인 bisect를 활용하면 깔끔하게 풀 수 있다. bisect.. 다른 상황에서도 멋있게 쓸 수 있지 않을까 싶은 친구..! 공부해놓아야겠다. import sys import bisect n, x = map(int, sys.stdin.readline().split()) nums = list(map(int, sys.stdin.readline().split())) # bisect_left 가 반환해주는 index 는 자기 왼쪽에는 다 target 보다 작다는 것을 의미 # bisect_right 는 나를 포함한 내 뒤에 있는 아이들은 다 target 보다 크다..
coding/알고리즘,자료구조 2022. 2. 5. 11:33
이진탐색 연습 - 나무자르기(백준)

문제 : https://www.acmicpc.net/problem/2805 # 입력값 받기 N, M = map(int, sys.stdin.readline().split()) trees = list(map(int, sys.stdin.readline().split())) # 이분탐색을 시작할 초기 범위 설정 lt = 0 rt = max(trees) answer = 0 # 절단기 높이를 설정했을 때 얻어낼 수 있는 나무의 총 길이 구하는 함수 def how_long(length): total = 0 # 나무 높이를 돌면서, 절단기 높이보다 높다면, 잘렸을 때 길이를 총 길이에 더해간다. for tree in trees: if tree > length: total += (tree-length) else: con..
coding/알고리즘,자료구조 2022. 2. 5. 11:28
이진탐색 연습 - 징검다리(프로그래머스)

이진탐색을 연습하는 중이라서, 바로 직전에 프린터 문제를 풀었더니 프린터 풀이 방식과 동일한 방식으로 풀게 되었다. 살짝 변화를 준 부분은, mid의 변화에 따라 [가장 인접한 바위의 최대거리] 값이 주어질 때, 그 상황에서 바위는 몇 개까지 둘 수 있는지를 세보는 함수(isOK로 명명)가 boolean 을 return 하도록 해본 점이다. (직전에 풀었던 공유기에서는 거의 유사한 함수였지만 카운트한 int값을 반환해주었다.) 남겨두어야 하는 바위의 개수보다 적은 경우에는 False, 남겨두어야 하는 바위 이상인 경우에는 True를 주어서 본함수(?)에서 불리안 값을 참고해서 mid를 늘려도 될지, 아니면 mid를 더 줄여야 할지 판단하도록 했다. 1. 손정리 2. 코드 def solution(dista..
coding/알고리즘,자료구조 2022. 2. 4. 19:03
Prev 1 ··· 4 5 6 7 8 9 10 ··· 29 Next