아이테킨의 끄적끄적

기본적인 탐색문제인 듯 하다. 이 문제는 DFS로 풀 수 있는데 푸는 방법을 굳이 나눠보자면 인접행렬과 인접리스트 방식으로 풀 수 있다. 이 차이는 그래프를 표현하는 방식의 차이일뿐 본질적인 차이는 없다. 표현 방식에 따라서 코딩을 해주면 된다. 나는 인접행렬 형식으로 풀어보았다. 인접리스트 방식으로 푼 풀이가 궁금하신 분들은 https://hjp845.tistory.com/33 여기 블로그에 코드가 있으니 참고하면 된다. 그러나 알고리즘이 아닌 다른 부분에서 좀 해맸다. 1. sys.setrecursionlimit(10000) 재귀를 사용할 땐 항상 재귀의 깊이를 넉넉하게 설정해주는 것을 잊지 말아야 한다. 이걸 안해주면 런타임에러(recursuionerror)가 뜬다. 2. sys.stdin.read..

한시간 가량 고민하다가 결국 구글에 검색하고야 말았다...ㅠㅠ 이 문제를 푸는 아이디어는 누적합까지는 모든 무게의 경우를 만들 수 있다는 것이다. 예를 들어 1,2,3의 추가 있다고 한다면 누적합 6(1+2+3) 까지의 무게를 무조건 만들 수 있다는 것이다. 그리고 이 누적합+1 의 값보다 큰 추가 다음으로 나온다면 (예를들어 8이 나온다면) 누적합 +1(7) 이 주어진 추들로 측정할 수 없는 양의 정수 무게중 최소값이다. 누적합까지의 모든 경우의 수가 만들어 질 수 있다는 아이디어, 이건 평소 숫자에 대해서 얼마나 친한지?, 센스인것 같다. 내 머리가 조금 딱딱한 듯 하다... 더 유연하게 생각할 수 있기를! 이런 방법도 있음을 기억해두자. # 2437번: 저울 n = int(input()) scale..

피보나치 수열을 구하는 대표적은 다이나믹 프로그래밍 문제이다. 그러나 이번 문제는 단순히 문제를 해결하는 것 뿐만 아니라 더 빨리 효율적으로 풀 수 있는 알고리즘을 물어보고 있다. 문제의 답은 반복문 또는 메모이제이션을 이용해서 풀면 된다. (메모이제이션을 이용한 코드는 아래 있다.) # 반복문으로 푼 피보나치 n = int(input()) dp = [0]*100 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 이번 기회에 피보나치 수열을 구하는데 사용되는 3가지 방법에 대해서 정리해보았다. 반복문, 재귀, 메모이제이션 총 세가지 방법으로 피보나치 수열을 풀 수 있지만 각각 시간복잡도, 메모리를 사용하는 정도가 다르다. 1...

다이나믹 프로그래밍 문제는 점화식을 풀어서 해결해야 하는 경우가 많다는 것을 기억하자. 이 문제도 점화식을 사용해보면 해결할 수 있다. i번째 포도주를 시음한다고 하면 생각할 수 있는 경우의 수는 1. i-2번째 포도주를 마신 경우 2. i-3번째 i-1번째 포도주를 마신 경우 또한 i번째 포도주를 마시지 았았을 경우 생각할 수 있는 경우의 수는 3. i-1번째 포도주를 마신 경우이다. 이 세가지 경우의 수 에서 가장 큰 값을 출력해내면 된다. 이를 점화식으로 표현해보면 dp[i] = max(dp[i-2]+w[i], dp[i-3]+w[i-1]+w[i], dp[i-1]) # 2156번: 포도주 시식 # dp문제는 점화식을 만들어봐야 한다. # 다시 풀어보기!! 아 실력이 안느냐 왜 ㅠㅠ n = int(in..

그리디문제로 나는 행렬이 들어가기만 하면 어렵다 ㅠㅠ # 1080번: 행렬 # 다시풀기 n,m = map(int,input().split()) graph1 = [] graph2 = [] cnt = 0 def convertgraph(i,j): for x in range(i,i+3): for y in range(j,j+3): graph1[x][y] = 1- graph1[x][y] for i in range(n): graph1.append(list(map(int,input()))) for i in range(n): graph2.append(list(map(int,input()))) for i in range(n-2): for j in range(m-2): if graph1[i][j] != graph2[i][j..

그리디 문제로 발생할 수 있는 경우의 수를 차근차근 따져보면서 풀어보면 된다. 우선 이 문제는 사야하는 줄보다 더 많이 사도 된다는 것이 포인트이다. 그래서 6개 세트로 넉넉하게 살 경우 1개를 낱개로 맞춰서 사는 경우보다 저렴할 경우 넉넉하게 사도 된다. 또 놓치지 말아야 할 부분은 6개 세트가 낱개로 6개를 살때보다 항상 싸다는 말은 없다. 따라서 이 부분도 신경을 써주어야 한다. 이를 코드로 표현하면 아래와 같다. # 1049번 기타줄 n,m = map(int,input().split()) line_set = [] line_ = [] for i in range(m): a,b = map(int,input().split()) line_set.append(a) line_.append(b) e = min(..

코드스테이츠 AI 부트캠프 3기 section2 프로젝트 내용을 정리한 것입니다. 1. 개요 전세계 맥주데이터를 분석하여 소비자들이 어떤 맥주를 선호하는지 머신러닝 기법을 통해서 분석하고 결론을 도출하는 프로젝트 입니다. 2. 프로젝트의 목표 알코올 함유량에 따라서 소비자들의 맥주 선호도가 달라지는지 확인해보려고 한다. 가설은 다음과 같이 설정해보았다. 가설 : 알코올의 함유량에 따라 맥주에 대한 소비자들의 평가가 다를것이다. 3. 데이터 총 5500개 정도의 데이터와 21개의 피처를 가지고 있는 맥주데이터 입니다. (데이터 출처 : https://www.kaggle.com/stephenpolozoff/top-beer-information?select=beer_data_set.csv) 앞에서부터 10개의..

쉬운 문제인듯 하다 정답률도 높다.(70퍼 이상) 최소값을 만들땐 6을 5로 바꿔주고 최대값을 만들땐 5를 6으로 바꿔주면 된다. # 2864번: 5와 6의 차이 a,b = map(int,input().split()) min_a = '' for i in str(a): if i == '6': min_a += '5' else: min_a += i min_b = '' for i in str(b): if i == '6': min_b += '5' else: min_b += i max_a = '' for i in str(a): if i == '5': max_a += '6' else: max_a += i max_b = '' for i in str(b): if i == '5': max_b += '6' else: max..

# 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..