아이테킨의 끄적끄적

# 1912번: 연속합 n = int(input()) a = list(map(int, input().split())) sum = [a[0]] for i in range(len(a) - 1): sum.append(max(sum[i] + a[i + 1], a[i + 1])) print(max(sum))

이분탐색(binary search)를 이용해서 풀었다. 이분탐색은 탐색 기법중 하나로 말 그대로 탐색범위를 두 부분으로 나눠서 원하는 값을 찾는 방식이다. 탐색 범위를 절반씩 줄여가면서 찾는 탐색방법이다. 따라서 시간복잡도가 하나하나 일일이 탐색하는 순차탐색보다 더 좋다. 시간복잡도 : O(logN) 이분탐색을 할 때는 먼저 정렬이 된 상태이어야 한다. dynamic programming, recursion의 개념이 녹아있다. 이분탐색 함수를 따로 정의해주고 찾아야할 리스트는 파이썬 함수로 정렬해주었다. # 10815번: 숫자 카드 n = int(input()) n_list = list(map(int,input().split())) m = int(input()) m_list = list(map(int,i..

A에서 B를 만드는것이 아니라 반대로 B에서 A를 만드는 방향으로 생각해서 풀었다. B를 10으로 나눈 값이 1 이거나 B가 2로 나누어떨어질때마다 카운트를 계속 해주고 B가 A보다 작거나 위의 조건을 만족시키지 못하는 수(한자리 홀수)가 나오면 카운트를 -1로 정의해주면 된다. 처음 풀 때 한자리 홀수를 생각하지 않고 단순히 b B a,b = map(int,input().split()) cnt = 1 while True: if b == a: break elif (b%2 != 0 and b % 10 != 1) or (b

DP문제로 이 문제는 뒤에서부터 생각해야 풀 수 있다. 뒤에서 풀어보려고 계속 노력하다가 결국엔 다른 사람의 블로그를 참고해서 풀었다. 참고 블로그 https://pacific-ocean.tistory.com/199 # 14501번: 퇴사 n = int(input()) t_list = [] p_list = [] for _ in range(n): t,p = map(int,input().split()) t_list.append(t) p_list.append(p) dp = [0]*(n+1) for i in range(n-1,-1,-1): if t_list[i] + i > n: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1],p_list[i] + dp[i + t_list[i]]) pr..

DP문제다 DP문제의 가장 큰 특징은 중복되는 서브문제(overlapping subproblem)와 최적 부분 구조(optimal substructure)로 이런 유형의 문제에 접근하기 위해서는 하나의 문제를 작은 그러나 같은 방법으로 풀 수 있는 문제로 쪼개야한다. 이번 문제에서는 원하는 카드의 개수를 만드는 최대값을 구해야한다. 카드 1개 샀을때 최대값 카드 2개 샀을때 최대값 카드 3개 샀을때 최대값 카드 4개 샀을때 최대값 이런식으로 생각을 해보면 카드 1개 -> P[1] (=1개 카드 값) 카드 2개 -> max(P[1]+P[1] , P[2]) 카드 3개 -> max(P[1]+P[1]+P[1] , P[1]+P[2] , P[3]) ... 이런식으로 모두 따져봐야 하는 문제다. #11052번: 카드..

앞서 풀었던 타일 문제에 정사각형 타일이 하나 추가된 문제이다. 정사각형 모양의 타일이 하나 추가되었기 때문에 n-2번째 타일에서 가로 직사각형 두개 붙이는 경우와 정사각형 붙이는 경우, 총 두가지 방법으로 늘어났다. m(n) = m(n-1) + (2 × m(n-2)) # 11726번: 2xn 타일링 n = int(input()) m = [0]*1001 m[1] = 1 m[2] = 2 for i in range(3,n+1): m[i] = m[i-1] + m[i-2] print(m[n]%10007)

LIS(Longest Increasing Subsequence)라는 유명한 DP 문제라고 한다. 처음봤다. 아이디어는 배열에 있는 숫자들을 각각 비교하면서 큰 숫자가 나올때마다 1을 더해주는 방법이다. 배열의 순서에 상관없이 증가하는 가장 긴 부분수열의 길이를 찾을 수 있다. (배열의 최대값이 답이다) # 11053번: 가장 긴 증가하는 부분 수열 # LIS(Longest Increasing Subsequence)라는 유명한 DP문제 N = int(input()) A = list(map(int,input().split())) dp = [1] * N for i in range(N): for j in range(i): if A[j] < A [i]: dp[i] = max(d[i],dp[j]+1) print(m..

예전에 공부할때 봤었던 이코테라는 책에 이 문제와 비슷한 유형이 있어서 쉽게 풀 수 있었다. 타일을 채우는 방법의 수를 구하는 문제인데 m(n) = m(n-1) + m(n-2)로 결국 피보나치 수열과 같다. 피보나치 수열은 DP의 대표적인 문제로 재귀와 반복문 둘다 풀이가 가능하고 둘다 알아놓으면 좋을 듯 하다. 이번에는 바텀업 방식으로 풀어보았다. 마지막에 10007로 나눈 나머지를 출력하는 것을 까먹으면 안된다 ㅠㅠ 이걸 놓쳐서 10분동안 "어.. 왜 안되지...??" 를 반복했다.ㅠㅠ # 11726번: 2xn 타일링 n = int(input()) m = [0]*1001 m[0] = 0 m[1] = 1 m[2] = 2 for i in range(3,n+1): m[i] = m[i-1] + m[i-2] ..

일반적인 DP문제다. 오랜만에 문제를 풀어서 그런지(코딩 자체가 굉장히 오랜만이다...ㅠㅠ) 문제를 해결하는데 생각보다 오랜 시간이 들었던거 같다. 다이나믹 프로그래밍 문제는 기본적으로 문제를 작게 잘 쪼개는것이 가장 중요하다고 생각한다. 재귀를 이용해서 풀던(탑다운), 반복문을 이용해서 풀던(바텀업) 자기가 생각하기 편한 방식대로 풀면 된다. [DP조건] 중복되는 서브문제(overlapping subproblems) - 문제해결관점 : 큰 문제를 작은 문제로 쪼갤 수 있고, 큰문제와 작은문제를 같은 방법으로 풀 수 있다. => 메모이제이션 최적 부분 구조(optimal substructure) - 문제의 구조관점 : 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다. 이 문제는 주어진 수의 3번째..

코드스테이츠 AI 부트캠프 3기 section1 프로젝트 내용을 정리한 것입니다. 1. 프로젝트 개요 1980년도부터 2020년까지 출시된 게임의 지역별, 연도별 판매량 데이터를 통해 게임시장의 트랜드변화와 앞으로 게임시장은 어떻게 될 것인지, 최종적으로 새롭게 출시할 게임을 설계하고 추천하는 프로젝트 입니다. 2. 프로젝트의 목표 새롭게 출시할 게임 설계하기. 게임장르 플랫폼 지역 게임회사 출시시기 3. 데이터 EDA 및 전처리 총 16000개 정도의 데이터와 9개의 피쳐(feature)를 가지고있는 게임데이터입니다. 게임이름(Name), 사용된 플렛폼(Platform), 출시년도(Year), 장르(Genre)와 회사정보(Publisher)가 있으며 각각 북미,유럽,일본,그외 지역의 판매량(Sales)..