# DP
(Swift) Programmers 멀리 뛰기
코딩테스트 연습 - 멀리 뛰기 🚫 factorial을 사용한 풀이 (arithmatic overflow) 처음에는 아래처럼 모든 경우의 수를 더해서 문제를 풀어보고자 했습니다. 1과 2를 순서에 맞추어 나열하는 문제와 동일하므로 (1칸 이동의 횟수 + 2칸 이동의
[백준/java]11053. 가장 긴 증가하는 부분 수열
문제 링크 - https://www.acmicpc.net/problem/11053싸피 알고리즘 강의중 LIS 관련 내용을 복습하면서 풀어보았다.시간복잡도: 약 O(N^2) (정확히 따지자면 1+2+3+...+N = (N-1)\*N/2의 시간복잡도를 가진다.)
[BOJ-#2579] 계단 오르기
문제 본문은 아래 링크에서 확인하실 수 있습니다!\[\[BOJ-해당 포스팅은 백준 온라인 저지 이용 규칙을 준수합니다.계단 오르기 문제는 이차원 리스트를 만들어 해결할 수 있는 문제입니다.이차원 리스트 dp는 각 계단마다 연속되지 않은 계단을 밟은 경우와 연속된 계단을
BOJ - 팰린드롬 만들기
1695 팰린드롬 만들기 : https://www.acmicpc.net/problem/1695접근 방법도 생각을 못했습니다.DP로 풀수있다는 것에 신기했습니다.주어진 수열에서 수를 끼워넣을 수 있는데, 끼워넣는 개수가 최소가 되어야합니다.재귀를 통해 어떤 수를
BOJ 1003: 피보나치 함수
\->문제입니당 <-문제는 우리가 흔히 아는 피보나치인데 거기에 약간의 응용을 곁들인,,,문제에서 재귀를 이용해서 짠 피보나치 코드를 준다.재귀로 피보나치를 풀면 함수 f(n)은 f(n-1) f(n-2)를 호출한다.예를 들면 f(4) = f(3) + f(2) ->
[BOJ 1937] 욕심쟁이 판다
https://www.acmicpc.net/problem/1937 n x n 크기의 대나무 숲에서 판다는 상, 하, 좌, 우로 이동하며 대나무를 먹는다. 이때, 이동한 칸은 그 전 지역보다 대나무가 많이 있어야 한다. 판다가 이동할 수 있는 칸의 수의 최댓값을
BOJ - 퇴사
14501 퇴사 : https://www.acmicpc.net/problem/14501해당 문제는 브루트포스로 풀 수 있고, DP로도 풀 수 있는 문제입니다.기억은 안나지만 전에 브루트포스로 풀은 경험이 있길래 DP로 풀어보겠습니다. (점화식을 못구해서 다른
[Pytorch] 분산학습(V2) DP, DDP 개념 정리
💡 DataParallel(DP)은 Pytorch 에서 제공하는 가장 기본적인 방법이지만, GPU 메모리 불균형이 발생하는 문제점이 있음. Custom DataParallel은 GPU 메모리 불균형 문제를 어느 정도 해소해주지만, GPU util이 낮다는 문제가 여
[Pytorch] 분산학습(V1) 비교 실험 - DDP, DP
CUDA 11.1Pytorch : 1.8.1 CU11.1GPU : A10OS : Linux 18.04Model : AlexNet, ResNet20Data : CIFAR10Training Method : DP(DataParallel), DDP(DataDistributed
백준 1520번 내리막 길
목적지까지의 모든 경로를 탐색해야한다? DFS지도의 크기가 클 경우, 완전탐색은 시간초과를 야기하므로 DP를 적용한다.visited 이차원 배열을 선언하여,vistied\[x]\[y] 에 map\[x]\[y] 까지의 경로 갯수를 저장한다. 또한, -1로 초기화하고 0
[Algorithm] LIS, Longest Increasing Subsequence
수열 arr의 모든 부분수열중 원소가 모두 증가하는 부분수열의 최대길이를 구하려는 문제가 있을때,단순히 전부 그리디방법으로 탐색시, N N회의 연산이 필요하나,DP를 이용하여 N N (1/2)로 절반으로 줄이거나BS(Binary Search)를 이용하여 N log
백준 2011 암호코드 (C++)
2011번: 암호코드dp를 이용한 문제이다. 점화식을 잘 세우면 빠르게 풀 수 있다. 문제에 주어진 예시가 힌트였다. 1111111111을 차례대로 생각해보자.1 : 1개11 : 2개111 : 3개1111 : 5개11111 : 8개 즉 dp\[n] = dp\[n-2]
[백준] RGB거리 2 (17404)
https://www.acmicpc.net/problem/17404RGB 거리의 확장 형이다.달라진게 있다면 마지막 집의 색과 1번 집의 색은 같으면 안되는게 추가 되었다.많은 고민을 하다가 1번째 집의 색이 R일때 G일때 B일때 경우의 수를 따지기로 했다.
[백준 C++] 11055 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 5