최장증가 부분수열 - LIS(Longest Increasing Subsequendce) 주어진 수열에서 일부 원소를 골라내어 만든 부분 수열 중, 오름차순으로 정렬된 가장 긴 부분수열을 의미한다. 이때 핵심은 부분수열이 반드시 연속될 필요는 없다는 것이다. 즉 몇 개의 원소를 건너뛰어도 해당 연속으로 정렬만 되면 된다는 것이다. 예를 들어 {2, 3, 8, 6, 4, 5, 9, 1}의 경우 가장 긴 증가 부분수열은 {2, 3, 4, 5, 9}이 됨 특징부분수열의 각 원소는 원래 수열에서 순서를 지켜야 함, 연속적일 필요는 없음오름차순이므로 앞의 원소보다 뒤의 원소가 크거나 같아야 함한 수열에는 여러 개의 최장 증가 부분 수열이 존재할 수 있음 구하는 방법동적계획법 - DP각 인덱스에서 끝나느 LIS의 길..

[Python] 프로그래머스 lv2 - 숫자 변환하기 코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 숫자를 기준으로 x가 y가 되기까지의 최소 연산 횟수를 구하는 문제이다. 하나의 방법으로는 제한사항, 시간초과, 런타임 에러등의 두 가지의 방법을 생각했었다. 재귀 - 런타임 에러 발생 문제에서 요구하는 계산을 재귀로 호출, 재귀에서 호출하며 들어오는 cnt를 list에 저장 저장된 list의 최솟값을 answer로 반환 만약에 x==y가 성립되지 ..

[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의 경우의 수를 합산하면 해당 인덱스의 경우의 수..