https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 나의 풀이 2칸씩 이어서 갈 수 있고, 3칸은 안됨 1칸만 띄어서 갈 수 있고 2칸은 안됨 마지막 계단을 무조건 밟아야 함 최대로 나오는 점수를 return 하면 되는 문제이다. dp에는 각 step에서 선택할 수 있는 가장 큰 수가 저장된다. import sys input = sys.stdin.readline n = int(input()) s=[int(input()) for _ in range(n)] pri..
https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 아래와 오른쪽으로만 이동 가능 물 웅덩이는 지나가지 못함 빨 -> 파 -> 초 -> 검 방향으로 갈 수 있는 경우의 수를 체크함 여기서 puddles이 x, y 정렬이 아니라 y, x 정렬이라 반대로 넣어줘야 함 이거 때문에 시간이 오래 걸림 def solution(m, n, puddles): roadmap = [[0]*(m+1) for j in range(n+1)] roadmap[1]..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 나의 풀이 n개의 정수로만 이루어진 임의의 수열이 있을 때 연속된 몇 개의 수를 선택해서 구할 수 있는 가장 큰 합을 구하려고 한다. [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] t-1 + t의 값이 t보다 크다면 해당 연속된 수열의 합이 가장 큰 것이다.라고 생각하고 문제를 풀었다. import sys n = int(sys.stdin.readline()) nums = list(m..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나의 풀이 다음과 같이 나선 모양의 삼각형이 있다고 할 때, 가장 긴 변의 길이를 K라고 한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변(k)의 길이이며 N이 주어졌을 때 p(N)을 구하는 프로그램을 작성하자. 다음과 같이 인덱스가 있다고 하면 p(n)은 p(n-1) + p(n-5)라고 볼 수 있으며 코드로 나타내면 아래와 같다. import sys cnt = int(sys.stdin.read..
https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 나의 풀이 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드 1 코드 2 실행 횟수를 출력하자...
https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 1. 처음엔 조합 solution으로 접근함 2를 최대로 쓰는 값을 구하고 (ex n = 7 , (2, 2, 2, 1)) 2를 1 두개로 변환하여 이에 대한 조합을 구함 from itertools import permutations def solution(n): bin_n = bin(n)[2:] cnt_2 = 0 cnt_1 = 0 ans = 0 if bin_n[-1] == '1': cn..
동적 계획법 (DP) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결하는 알고리즘, 문제 해결 패러다임 상향식 접근법, 최하위 해답을 구하고 이를 이용하여 상위 문제를 풀어감 Memorization 기법 사용 프로그램 실행 시 이전 계산 값(작은 문제)을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술임 큰 문제를 작은 문제로 쪼개서 답을 저장하고 재활용 하기에 '기억하며 풀기' 라고도 불림 ex) 피보나치 수열 재귀함수와 다른 점은 \((F_{2}\) 가 여러번 사용되는데 동적 계획법은 저장하여 다시 계산하지 않고 재귀함수는 하나하나 다 계산하여 시간이 오래 걸린다 \( O(n^{2}) \to O(f(n)) \) 분할 정복 큰 ..
