내가 올리고 싶은대로 올리는 개발 블로그

[백준]11053- 가장 긴 증가하는 부분 수열 문제 풀이(파이썬,Python)

문제11053번: 가장 긴 증가하는 부분 수열 들어가며DP 문제의 대표격이다.하지만, 이 문제는 이분 탐색으로도 풀 수 있다.이 글은 이분 탐색으로 어떻게 푸는지에 대한 이야기이다. 코드from typing import MutableSequencedef lis_binary_search(arr : MutableSequence): lis = [] # LIS 배열 초기화 for num in arr: pos = binary_search(lis, num) if pos == len(lis): lis.append(num) # num이 가장 크다면 추가 else: lis[pos] = num # num으로 기존 값을 교체 ..

[백준]2470 - 두 용액 문제 풀이(파이썬,Python)

문제2470번: 두 용액들어가며이분 탐색으로 접근할려고 했는데, 아무리 생각이 안나서 투포인터로 풀었다.코드n = int(input())arr = list(map(int,input().split()))arr.sort()pl = 0pr = n-1result_nums = []best_sum = 10000000000# 끝점 두 개가 음수if arr[pl] 0 and arr[pr] > 0 : print(f"{arr[pl]} {arr[pl+1]}")# 끝점 두 개가 서로 혼합else : while pl 0: pr -= 1 # 합이 정확히 0이라면 최적이므로 종료 else: break print(f"{result[0]} {resul..

[백준]2110 - 공유기 설치 문제 풀이(파이썬,Python)

문제2110번: 공유기 설치 들어가며정말 머리가 터질 뻔한 느낌을 오랜만에 받은 문제이다.들어가기 전에 이 문제가 이분 탐색이라는 것을 알고 있어서 최대한 이분 탐색을 사용해서 풀려고 했다.근데 아무리 봐도 어디가 이분 탐색인지 안보였다.답답해 미칠 뻔 했다.아직까진 갈 길이 참 멀지 않나 싶다.. 화이팅 코드l = list(map(int, input().split()))n = l[0]c = l[1]arr = []for _ in range(n): arr.append(int(input()))arr.sort()result = 0left = 1right = arr[-1] - arr[0]while left = middle: cnt +=1 last_installed ..

벌써 들어온지 2주일이 되어간다..0 주차 땐, 미니 프로젝트를 만드는 것이 주된 내용이었다.1주차부턴 매주 바뀌는 팀들과 함께 알고리즘 및 CS 학습을 진행한다.그리고 CS와 백준 문제 시험으로 1주일을 마무리한다. 앞으로 이렇게 좋은 팀이 있을까?자리에 딱 앉아서 이야기를 하는데, 나이가 서로 다 같았다.여기서 99즈를 만들 줄은 정말 몰랐지만, 신기했었다.그리고 관심사도 비슷비슷하고 열정은 강의실 전체에선 최고라고 말해도 될 정도였다.언제나 새벽 1~2시 정도까지 강의실에 남아서 자습을 같이 할 정도였다.주 100시간 공부는 무슨 110시간 넘게 도달했었다.정말 체력적으로 힘들었지만, 강의실에 우리 팀만 남아있는 모습을 보며 더 열정을 불태웠었다. 밤 샌 덕분에 오랜만에 눈도 보고 눈사람도 만들고 ..