ULISIA's Developer Life

출처 : 내리막 길 문제해석 입력받은 맵을 (0,0)좌표에서 DFS탐색을 시작한다. 4방탐색을 통해 다음에 이동할 좌표의 인덱스가 경계를 벗어나지 않으면서 현재좌표값보다 높이가 더 낮을때만 dfs 함수를 재귀 호출한다. 최종적으로 (n-1,m-1)좌표에 도달했을때마다 ans값을 1씩 더해준다. 모든 dfs 탐색이 끝난 이후 최종적으로 나온 ans값을 출력한다. 처음엔 여기까지 해서 풀어본 결과 시간초과가 나왔다. (0,0)에서 시작해 dfs로 가능한 곳을 모두 탐색하였기에 너무 많은 경우의 수가 있기때문에 시간초과라는 결과가 나왔다. 따라서 시간초과를 줄이기 위한 핵심은 DFS에 DP 방식을 결합하는 것이다. isVisited 리스트에 -1, 0, n으로 구분하여 각각 미방문,방문한경우,경로완성수로 구분..

출처:14002번 가장 긴 증가하는 부분 수열 4 문제해석 수열을 받으면 그중 길이가 제일 긴 증가하는 수열을 구하는 문제이다. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘이라는 알고리즘 문제에서 자주 볼 수 있는 것을 사용하여 길이를 구할 수 있다. 이 문제에서는 길이뿐만 아니라 해당 수열까지도 결과값으로 출력해야 한다. 해답코드 #가장 긴 증가하는 부분 수열 4 import sys input = sys.stdin.readline n = int(input()) array = list(map(int, input().split())) dp = [1] * n #최장 부분 증가 수열 길이를 구하는 for문 for current in range(n): for ..