아이테킨의 끄적끄적

LIS(Longest Increasing Subsequence)라는 유명한 DP 문제라고 한다. 처음봤다. 아이디어는 배열에 있는 숫자들을 각각 비교하면서 큰 숫자가 나올때마다 1을 더해주는 방법이다. 배열의 순서에 상관없이 증가하는 가장 긴 부분수열의 길이를 찾을 수 있다. (배열의 최대값이 답이다) # 11053번: 가장 긴 증가하는 부분 수열 # LIS(Longest Increasing Subsequence)라는 유명한 DP문제 N = int(input()) A = list(map(int,input().split())) dp = [1] * N for i in range(N): for j in range(i): if A[j] < A [i]: dp[i] = max(d[i],dp[j]+1) print(m..

최단거리를 묻는 문제에서는 우선 BFS탐색법을 생각해봐야 한다. 단순히 최단거리를 묻는 문제가 아니라 여러가지 조건들을 만족시켜야 하는 상황이어서 코드가 약간 길어지긴 했지만 다행히 통과가 되었다. BFS문제는 큐 자료구조를 이용해서 큐가 빌때까지 하나씩 노드를 뽑아서 탐색하는 방법이다 1. 큐 자료구조를 만들고 2. 큐에서 한개씩 뽑아서 탐색 3. 큐가 빌때까지(while queue:) 코드 # 7576 토마토 m,n = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input().split()))) arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우 from collections..

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이 마지막으로 DP 정복하는것을 향해서!!! 다이나믹 프로그래밍(Dynamic programming, DP)란? 다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다. 나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷..

가장 기본적이고 DFS/BFS 개념문제라고 생각한다. DFS는 깊이우선탐색이라고 하여 그래프 자료구조를 그려놓고 수직의 방향으로 먼저 탐색하는 방법을 말한다. 재귀 혹은 스택 자료구조를 이용하여서 구현할 수 있다. BFS는 넓이우선탐색이라고 하여 그래프에서 수평방향으로 먼저 탐색하는 방법이라고 이해하면 될것 같다. 큐 자료구조를 이용하여 구현한다. # 1260번 # 입력값을 받는 부분 # 인접행렬로 그래프를 표현하였다. n,m,v = map(int,input().split()) graph = [[0]*(n+1) for _ in range(n+1)] for i in range(n+1): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 # DFS구..

수많은 정렬 알고리즘 중 대표적인 5가지 정렬 알고리즘에 대해서 정리해보려고 한다. 버블 정렬(bubble sorting) 선택 정렬(Selection sorting) 삽입 정렬(insertion sorting) 병합 정렬(Merge sorting) 퀵 정렬(Quick sorting) 셸 정렬(shell sorting) 힙 정렬(heap sorting) 우선 시간복잡도 기준으로 나눠보자 O(N²) 버블 정렬 선택 정렬 삽입 정렬 O(N log₂ N) 병합 정렬 퀵 정렬 셸 정렬 힙 정렬 아래에 있는 정렬들이 일단 시간복잡도가 더 빠르니 성능이 좋은 정렬 알고리즘이라 생각해도 될 것 같다. 그러나 언제나 그렇듯 모든 상황에서 아래의 알고리즘이 더 좋다고 단정지을 수는 없다. 1. 버블 정렬(Bubble s..