얄루의 개발일기🥑

Linked List(Head만 존재할 때) 자바로 구현한 linked list public class LinkedList { Node head; public LinkedList() { this.head = null; } public void append(int value){ Node newNode = new Node(value); if (head == null){ this.head = newNode; } else { Node currentNode = this.head; while (currentNode.next != null){ currentNode = currentNode.next; } currentNode.next= newNode; } } public int get(int index){ Node c..

n = int(input()) arr = list(map(int,input().split())) arr.insert(0,0) dp = [0] * (n+1) dp[1] = 1 res = 0 for i in range(2, n+1): MAX = 0 #해당 기준점이 되는 부분의 바로 앞부터 전체 다 돌아가며 확인을 위한 범위 for j in range(i-1, 0, -1): if arr[i] > arr[j] and dp[j]>MAX: MAX = dp[j] dp[i] = MAX+1 if dp[i] > res: res = dp[i] print(res) n = int(input()) arr = list(map(int,input().split())) arr.insert(0,0) dp = [0] * (n+1) dp[1..

def DFS(n): #메모이제이션 if dp[n] > 0: return dp[n] if n == 1 or n == 2: return n else: dp[n]= DFS(n-1)+DFS(n-2) return dp[n] if __name__ =="__main__": n = int(input()) dp = [0] * (n+1) print(DFS(n)) Top-Down 방식은 재귀와 메모이제이션 방식을 사용해서 진행한다. 재귀는 말그대로 본인을 호출하는 것을 의미하고 메모이제이션은 해당 재귀가 한 번이라도 호출되었다면 어딘가에 메모해두고 이를 다시 사용하지 않는 방식을 의미한다. 위의 코드에서 if dp[n] > 0: 이 한 번 호출되었던 경우를 의미한다.

n = int(input()) dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]) 가장 작은 해를 구해 그 해를 이용해서 점차 다른 큰 해를 구하는 점화식을 Bottom-up 방식이라 한다. DP의 경우 기준점이되는 부분을 잘 찾아서 이를 이용하면 문제를 쉽게 해결할 수 있다. Bottom-Up 방식이 동적계획법이고 Top-Down 방식은 넓은 의미의 동적 계획법이다.

문제 n개의 수들을 k개 만큼 뽑아 더한 수들의 합이 m의 배수인 경우를 다 구하라 문제풀이 def DFS(L,s,total): global cnt if L == k: if total%m == 0: cnt += 1 else: for i in range(s, n): DFS(L+1, i+1, total + a[i] ) if __name__ =="__main__": n, k = map(int,input().split()) a = list(map(int,input().split())) m = int(input()) cnt = 0 DFS(0,0,0) k개 만큼씩 수들의 조합을 뽑아낸 뒤 해당 k의 조합의 합이 m의 배수라면 cnt를 1개 증가시켜준다. L = 노드 레벨 s는 그 앞전에 확인했던 부분을 빼주기 위함..

문제 주어진 그래프의 섬의 갯수를 구해라 섬은 상하좌우 대각선이 연결되어 있으면 하나의 섬으로 본다. 코드 from collections import deque def BFS(x,y): q = deque() q.append((x,y)) island[x][y] = 0 while q: x, y = q.popleft() for i in range(8): nx = x+dx[i] ny = y + dy[i] if 0

문제 주어진 그래프에서 0,0부터 6,6 에 가는 방법을 모두 구해라 문제 풀이 def DFS(x,y): global cnt if x == 6 and y == 6: cnt +=1 else: for i in range(4): nx = x+ dx[i] ny = y+ dy[i] if 0

문제 해당 그래프 0은 갈 수 있는 길 1은 벽이라 했을 때 2차원 리스트의 마지막 지점에 도착하는 최소 거리는 몇일까? 해당 그래프의 최단 거리는 12이다. 문제 풀이 from collections import deque dx = [0,0,-1,1] dy = [1,-1,0,0] board = [list(map(int,input().split())) for _ in range(7)] dist = [[0] * 7 for _ in range(7)] q = deque() q.append((0,0)) board[0][0] = 1 while q: now = q.popleft() for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0

문제 마름모 모양으로 되어 있는 부분의 사과만 수확한 경우 총 몇 개의 사과를 딸 수 있는지 구해라 칸들 안에 들어있는 해당 숫자는 수확량이다. 문제 풀이 from collections import deque n = int(input()) a = [list(map(int,input().split())) for _ in range(n)] sum_apple = a[n//2][n//2] ch = [[0]*n for _ in range(n)] ch[n//2][n//2] = 1 dx = [0,0,-1,1] dy = [1,-1,0,0] q = deque() q.append((n//2, n//2)) L = 0 while True: size = len(q) if L == n//2: break else: for i in..

문제 s는 현재 나의 위치 e는 송아지의 위치로 +1, -1, +5 만큼만 이동할 수 있다고 할 때 우리는 최소 몇번의 움직임으로 송아지를 찾을 수 있을지 출력하세요 문제 풀이 -next 함수 사용 from collections import deque s, e = map(int,input().split()) MAX = 10000 ch = [0] * (MAX+1) dis = [0] * (MAX +1) a = [-1,1,5] ch[s] = 1 #시작 노드는 체크를 해준 표시를 해야 된다! dis[s] = 0 #시작 노드의 거리값은 0이다. q = deque() q.append(s) while q: now = q.popleft() if now == e: break for next in(now-1, now+1,..