아이테킨의 끄적끄적

기본적인 탐색문제인 듯 하다. 이 문제는 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(..

쉬운 문제인듯 하다 정답률도 높다.(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..

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