Dynamic Programming 검색 결과

4 개의 검색 결과가 있습니다.

Problem Solving/📗BOJ

[Programmers] N으로 표현 (Python)

📖 문제 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 💻 코드 def solution(N, number): # 집합을 원소로 하는 배열 생성 / 중복되는 값이 발생하므로 집합 사용 / 'N', 'NN', 'NNN' ... 값을 포함해서 초기화 dp = [{}] + [{int(str(N) * i)} for i in range(1, 9)] # i + j

2021. 10. 21. 22:17

Problem Solving/📗BOJ

[BOJ] 14501번: 퇴사 (Python)

📖 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 💻 코드 BFS 풀이 import sys from collections import deque def solution(): N = int(sys.stdin.readline().strip()) plan = [(-1, -1)] + [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)] q = deque() q.append((1, 0)) # 아무 상담도 못할 경우 대비 res = 0 # BFS while q: day, money = q.popleft() r..

2021. 10. 21. 22:16

Problem Solving/📕Programmers

[Programmers] 멀리 뛰기 (Python)

📖 문제 https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 💻 코드 def solution(n): dp = [0, 1, 2] + [0] * (n - 2) for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] % 1234567 🙌 한마디 가장 기초적인 dp 문제였다. 1칸 혹은 2칸씩 멀..

2021. 10. 20. 00:46

Computer Science/📝Algorithm

[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다. 다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming)은 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. 중복되는 연산을 줄이자 최적의 해를 구하기에 시간 또는 메모리 공간이 매우 많이 필요한 문제들은 컴퓨터로도 해결하기 어려운 문제다. 컴퓨터의 연산 속도와 메모리 공간은 한정적이기 때문이다. 따라서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다. 대표적인 방법이 바로 다이나믹 프로그래밍(Dynamic Programming)기법으로 동적 계획법이라고도 불린다. ..

2021. 10. 12. 16:10