아이테킨의 끄적끄적

bfs탐색 알고리즘을 통해서 풀 수 있는 문제다. 이 문제에서 신경써야 하는 부분은 보통은 상하좌우만 탐색을 하는 문제가 많았는데 이번 문제는 대각선까지 탐색을 해야 한다. # 4963번: 섬의 개수 # 상하좌우대각선까지 dx = [0,0,-1,1,1,1,-1,-1] dy = [1,-1,0,0,1,-1,1,-1] from collections import deque def bfs(w,h): cnt = 0 for x in range(h): for y in range(w): if graph[x][y] == 1: cnt += 1 q = deque() q.append([x,y]) while q: a,b = q.popleft() for i in range(8): nx = a + dx[i] ny = b + dy[i..

2가지 알고리즘을 이용하여 풀 수 있다. 1. BFS 2. bruteforce 첫번째로 BFS알고리즘은 주어진 그래프에서 탐색을 하기 위한것이므로 BFS문제를 많이 풀어본 사람이라면 쉽게 풀 수 있을것이다. 두번째로 이 문제에서 bruteforce는 벽을 세울 때 사용한다. 문제에서 입력값의 범위가 크지 않으므로 모든 범위를 계산해서 제일 큰 값을 고르면 된다. 참고로 제출할 때 python3이 아닌 pypy3로 제출해야 통과된다. python은 시간초과가 뜬다. 왜 이렇게 다른지는 나중에 ㅠㅠ 아이디어를 코드로 구현하는 것과 여러가지 환경설정에 대해서 알아야 할 부분도 많다 ㅠㅠ 가야할 길이 많지만 차근차근 꾸준히 걸어가자! # 14502번: 연구소 from collections import deque..

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