분류 전체보기74 동적 프로그래밍 (Dynamic Programming, DP) 이란? 나동빈님 유튜브 내용을 참고 하였다. 개요 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 구현 방식 Top down Bottom up 특정 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 예제. 피보나치 수열 피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능 점화식으로 표현할 수 있다. 점화식을 재.. 2023. 3. 14. [백준] 2644: 촌수계산 python 구현 / DFS 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력을 그림으로 설명하면 다음과 같다. 풀이 입력 받기 입력에서 요구한 두 사람의 촌수가 꼭 부모, 자식 관계로 나오지 않기 때문에 양방향으로 노드를 추가 하여야 한다 DFS 구현 본 과제에서는 깊.. 2023. 3. 13. [백준] 2583: 영역 구하기 python 구현 / BFS 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 풀이 좌표 문제는 항상 인덱싱이 헷갈린다. 이번.. 2023. 3. 13. [백준] 11725: 트리의 부모 찾기 python 구현 / DFS 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오 사실 처음에는 문제가 잘 이해가 가지 않아 tree 구조를 손으로 그려보니 이해가 편했다. 2번 노드부터 순서대로 부모노드를 출력하는 것 풀이 DFS로 구현하였다. vst에 1로 방문처리를 하는게 아니라 부모노드(current node)를 표시하며 방문 처리를 진행했다. 이번 문제에서도 재귀의 깊이를 확장해주었어야 했다. 또한 같은 코드로 pypy3으로 제출하였을 때 메모리 에러가 나는 것을 보면,, pyhon3보다 메모리 관리는 부족한가보다 CODE import sys sys.setrecursionlimit(10**7) n = int(input()) adj_list = [[] fo.. 2023. 3. 13. 이전 1 ··· 7 8 9 10 11 12 13 ··· 19 다음
