머신러닝 숄구

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요. 제한 조건 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 abresult 5 24 "TUE" def solution(a, b): day = ["THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"] mo..

1. 2차원 배열을 만들어서 예를들어 2->3으로 간다면 arr[2][3]=1 을 해줘서 선후 관계를 표현해준다 2. 1차원 배열을 만들어서 진입 차수 (들어오는 차수)의 개수를 입력한다. 예를 들어 2->3 으로 간다면 arr[3]+=1 을 해주고, 4->3 으로 간다면 arr[3]+=1 을 해줘서 arr[3]=2 가 된다 3. 진입 차수가 0인 노드를 큐에 쌓아주고, pop 하면서 그 노드가 가리키는 노드의 진입차수를 -1 해주고 4. 노드의 진입차수를 -1 해줬는데 0의 값이 되었으면 더이상 그 노드를 가리키는 노드가 없으므로 큐에 쌓아준다 5. 큐 popleft 한 순서대로 print를 해준다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

앞에서 진행했었던 가방문제와 동일하다고 생각할 수 있으나, 한 유형당 문제 한 개만 풀 수 있다는 점이 다르다. 가방문제에서는 보석 각 타입을 무한정으로 이용할 수 있었다 상황을 이해하기 위해 우선 2차원 배열로 이해해보자 문제를 중복해서 풀지않기 위해서 2차원 배열로 풀어냈는데, 이는 1차원 배열로도 설명이 가능하다 위의 1차원 배열 코드 구현은 공간복잡도 시간복잡도 모두 고려했기 때문에 아주 최적이다 1 2 3 4 5 6 7 8 9 10 11 12 13 if __name__=='__main__': n, m = map(int, input().split()) dyn = [0]*(m+1) for i in range(1, n+1): scr, min = map(int, input().split()) for j..

앞의 가방 문제와 마찬가지로 냅색 알고리즘을 사용하여 푼다 다른 점은 minimum 값을 구한다는 것이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 if __name__=='__main__': n = int(input()) coins = list(map(int, input().split())) money = int(input()) dyn = [1000]*(money+1) # 동전이 1

처음 문제를 읽었을 때 DFS로 풀면 좋겠다고 생각해서 코드를 짯으나 다른 테스트 케이스에서 time limit에 걸려버렸다. 생각해보니 가방의 저장무게가 만약에 1000kg라고 하고 특정 보석이 1kg이라고 하면 1000번까지 돌면서 경우를 봐야하는 것인데 시간이 초과 될만했다. 밑에는 DFS로 푼 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def DFS(start, sum, res): global res_ if res > res_: res_=res for i in range(start,n): if sum+jewelry[i][0]

작은 부분부터 보면서 규칙을 파악해 본다 계산식이 2가지 부분으로 나뉘는데 1번째는 맨 위 라인과 맨 왼쪽 라인에 대해 Bottom up 동적계획법으로 값을 구한다는 것 + 2번째는 나머지 부분에 대해 왼쪽과 위쪽 중에 다이나믹 배열 상에서 더 작은 값을 선택해서 Bottom up 동적계획법으로 풀어나간다는 것 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n = int(input()) board = [list(map(int, input().split())) for _ in range(n)] for i in range(1, n): board[0][i] += board[0][i-1] board[i][0] += board[i-1][0] for i in range(1, n): for j in..

앞의 최대 부분 증가수열을 응용 한 문제이다 처음에는 좀 헤메다가 height 와 width 를 모두 신경 쓸 필요없이 height 기준으로 일단 sort 해주고 width를 맞춰서 LIS를 구하면 되겠구나 하고 생각이 미쳤다 나는 height 기준 오름차순으로 정렬했고, 인프런 인강 풀이는 sort(reverse=True)로 내림차순으로 정렬해서 풀이를 진행했다. width 값 기준 오름 차순으로 정렬하여 한 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] arr.sort() leng = [0]*n leng[0] = arr[0][1]..

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n = int(input()) ls = list(map(int, input().split())) dyn = [0]*n dyn[0] = 1 for i in range(1, n): length = 1 for j in range(0, i): if ls[j] max: max = length[j] length[i] = max + 1 if length[i] > res: res = length[i] print(res) Colored by Color Scripter cs

이 문제는 앞의 네트워크 선 자르기 문제와 동일해 보이나 다른 점은 마지막에 땅까지 도착하는 지점이 하나 추가된다는 것이다 1 2 3 4 5 6 7 8 9 10 if __name__=='__main__': n = int(input()) arr = [0] * (n+2) arr[1] = 1 arr[2] = 2 for i in range(3, n+2): arr[i] = arr[i-1] + arr[i-2] print(arr[n+1]) cs 이러한 유형의 문제는 중간 징검다리는 건널 수 없는 조건이 생긴다던지 다른 방법으로 응용되서 나올 수 있다

일단 피자집 M개가 선택되어야 하는 상황이니 조합을 생각했어야 한다! 예를 들어, 6개 중 4개만 뽑는다 하면 DFS를 사용하여 4가지만 뽑는 경우의 수를 구할 수 있다 그리고 뽑아진 M개의 피자집을 가지고 집들을 모두 for문을 이용하여 돌면서 하나의 집당 어떤 피자집과 가장 최소거리를 갖는지 찾은 후, 그 거리들을 모두 더하면 최소 피자배달거리가 나온다 나온 최소 피자배달거리도 조합에 따라 모두 다를 것이다. 그 중에 가장 최소값을 찾으면 되는 문제인 것이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 def DFS(level, start): ..