[Python] 프로그래머스 lv2 - 멀리 뛰기 코딩테스트 연습 - 멀리 뛰기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 문제에서 주어진 것 뛸 수 있는 거리는 1 or 2칸 문제에서는 n칸이 주어짐 이때 1과 순서가 달라지는 것도 수 체크에 들어감 이때 본인이 n의 거리를 뛸 경우 경우의 수 % 1234567를 구하기 문제 풀이 먼저 적은 수의 경우 뛸 수 있는 경우의 수를 계산해 보았다. 뛰는 거리 1 2 3 4 5 6 경우의 수 1 2 3 5 8 13 해당 표는 1,2로 뛸 수..

[Python] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분 수열 문제 출처 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 접근방법 가장 긴 증가하는 부분수열 이번에는 메모이제이션 기법을 이용해서 기존 수열과의 길이 비교에 사용된다. 메모이제이션을 사용하는 동적계획법의 이번 문제의 시간복잡도는 for문의 반복 첫번째 반복문에서 n번 그 다음 반복문은 i..

[Python] 백준 알고리즘 1010번 - 다리 놓기 문제 출처: 1010번: 다리 놓기 (acmicpc.net) 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 접근 방법 접근은 조합으로 접근을 하였다. 1 ) 파이썬 자체 내장 팩토리얼 메서드 이용 2 ) 팩토리얼을 동적계획법으로 구하고 그 나온 수를 이용해서 조합의 구조로 답출력 동적계획법을 넣기 위해 2번의 방식을 선택했다. 문제에서 주어진 숫자의 범위는 0

백준 알고리즘 11726 - 2 x n 타일링 문제 출처 : 11726번: 2 ×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 다이나믹 프로그래밍, 즉 동적 계획법을 바탕으로 접근을 해야 하는 문제이다. n이 늘어나는 경우에 맞춰 점화식을 세우고 그에 맞춰서 코드를 진행하였다. 점화식에 대해 접근을 해보자. 해당 점화식의 경우 피보나치 수열과 유사한 점화식이 등장한다. 점화식의 경우 본인의 인덱스를 i라고 하자. 그럼 i - 2 와 i - 1의 경우의 수를 합산하면 해당 인덱스의 경우의 수..