개발자식

📃 문제: https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✏️ 나의 풀이 - 순차적으로 탐색해서 조건에 맞는지 확인한다면, 다음과 같은 반례가 있음 [50, 50, 30, 20, 70, 80], limit = 100 -> 50+50, 30+20, 70, 80 으로 4개의 구명보트가 필요하지만, 20+80, 30+70, 50+50으로 태우면 3개의 구명보트만 필요하다. - 그래서 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 쌍을 이뤄 ..

피보나치 함수 코드 n = int(input()) # fibonacci(0) = 0, fibonacci(1) = 1, # fibonacci(2) = fibonacci(1) + fibonacci(0) # fibonacci(3) = fibonacci(2) + fibonacci(1) arr = [] if n == 0: print(1, 0) else: for i in range(n): k = int(input()) arr.append(k) temp = arr.copy() temp.sort() if n == 1 and k == 0: print(1, 0) else: dp = [[0,0]] * (temp[-1]+1) dp[0] = [1,0] dp[1] = [0,1] for i in range(2, len(dp)): ..

최대공약수(Greatest Common Divisor) - 두 수 혹은 그 이상의 여러 수들의 공통인 약수 중 최대인 수 최소공배수(Least Common Multiple) - 두 수 혹은 그 이상의 여러 수들의 공통인 배수 중 최소인 수 코드 구현 a = 10 b = 12 #최대 공약수 구하기 for i in range(min(a,b), 0, -1): if a % i == 0 and b % i == 0: print(i) #2 break #최소 공배수 구하기 for i in range(max(a,b), (a*b) + 1): if i % a == 0 and i % b == 0: print(i) #60 break 유클리드 호제법 - 최대공약수를 쉽게 구할 수 있는 방법으로 최대공약수를 알면 최소공배수는 간단..

이진 탐색(Binary Search) - 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하여 원소 하나씩 확인해야 하는 순차 탐색보다 빠르다. - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. (데이터가 무작위일 때는 사용할 수 없음) 이진 탐색(Binary Search) 과정 - 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점을 사용해서 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾아간다. 1. 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. (중간점이 실수일 때는 소시점 이하를 버린다) 2. 찾으려는 데이터와 중간점 데이터를 비교하여 중간점의 데이터가 더 크다면 끝점을 중간점의 위치 이전으로 옮긴다. 중간점의 데이터가 더 작다면 시작점을 중간점..

누적 합(Prefix Sum, Cumulative Sum) - 말 그대로 나열된 수의 누적된 합을 말한다. - 수열 An에 대해서, 구간 [1,1]의 합, 구간 [1, 2]의 합, 구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다. An 1 2 3 4 5 Prefix Sum 1 3 6 10 15 누적 합의 사용 - 목적에 따라 다양한 문제에 활용이 가능하다. - 대표적으로 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다. 단순 반복을 이용한 구간 합 구하기 - 모든 입력마다 구간 합을 일일히 구해주는 경우 구간의 길이가 M이라고 하면 매 구간합을 구할 때마다 O(M)이라는 시간이 걸리게 된다. N개의 구간에 대해 구간의 길이가 M인 구간합을 구하는 경우 O(NM..