542. 01 Matrix - 파이썬 풀이 문제접근 아이디어 구현코드 문제접근 아이디어 해당 문제는 백준에 7569번 토마토라는 문제가 존재하는데 이 문제와 매우 흡사하다. 거의 똑같다. (클릭 시 해당 문제로 이동) 가장 이 문제는 1에서 가장 가까운 0까지의 거리를 적는 문제이다. 그럼 0에서 1까지의 거리를 써주면 된다. 근데 최소거리를 써줘야 하는 문제이기 때문에 값이 0인 인덱스를 전부 Queue에 넣고 빼면서 bfs를 해주면 가장 가까운 0이 제일 먼저 해당 1에 도달을 할 것이다. 그래서 distance값이 초기 설정과 달라지면 최소 거리를 찾은 것이다. bfs를 하는 방법은 인접 인덱스가 인덱스 범위 안에 있거나 방문한 적이 없다면 즉, distance가 초기 값과 같다면 Qu..

이 게시물은 게시자의 이해를 위하여 작성됨. " LIS ( Longest Increasing Subsequence ) 최장 증가 부분수열 알고리즘 " 최장 증가 부분수열 알고리즘은 N개의 배열의 일부 원소를 골라내서 만든 부분 수열의 각 원소가 이전 원소보다 크다는 조건을 만족하는 가장 긴 부분 수열을 의미. [ DP를 이용하는 방법 ] data = [10, 0, 20, 30] for i in range(n): DP[i] = 1 for j in range(i): if data[j] < data[i]: DP[i] = max(DP[i], DP[j] + 1) 1. i = 0일 때, DP[0] = 1 / j는 반복하지 않음. 1 2. i = 1일 때, DP[1] = 1 / for j in range(1)이기에 ..

이 게시글은 게시자의 이해를 위해 작성됨. " Longest Common Subsequence / Substring " 이는 한국어로 최장 공통 부분수열 / 문자열 이라고 함. ( 주로 최장 공통 부분수열을 말함. ) 먼저 최장 공통 문자열에 대해 알아보자. { 최장 공통 문자열 / Longest Common Substring } 최장 공통 문자열은 위처럼 연결되어있는 문자열이 같은 경우를 말함. 무조건 이어져 있어야함. 최장 공통 부분수열은 떨어져있는 경우도 생각해야하는데 이건 그렇지 않으니까 더 쉬움. 최장 공통 문자열에서 생각해야 하는 것은 두 문자열의 문자가 같은지와 문자가 연속되는지를 생각해야함. [ 두 문자의 비교 순서 ] 1. 두 문자열의 문자를 하나씩 비교. 2. 두 문자가 다르면 LCS[..