본문 바로가기

프로그래밍

[백준 11054 가장 긴 바이토닉 부분수열] 파이썬 풀이 가장 긴 바이토닉 부분 수열 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,0.. 더보기
[백준 9251 LCS] 파이썬 풀이 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이전략 1. 이차원 배열에 DP 값을 저장합니다. 2. DP[i][j]는 첫 번째 수열의 i 번째까지와 두 번째 수열의 j 번째까지 공통된 부분 수열의 최대 길이 입니다. 3. 만일 A[i]와 B[j]가 같다면 DP[i-1][j-1]에서 하나를 추가한 경우 입니다... 더보기
[백준 실버 1912 동적프로그래밍] 연속합문제 파이썬 연속합 문제는 주어진 순열에서 연속적으로 선택한 값 중에서 최대를 구하는 문제입니다. 예) 10 -4 3 1 5 6 -35 12 21 -1 다음 수열에서 최대는 12+21 = 33 입니다. 리스트의 최대 길이는 10만이므로 for 문으로 구현하게 되면 시간 초과가 나옵니다. 따라서 동적 할당을 통해서 문제를 풀어야 합니다. 방법을 복잡하게 생각하기보다 단순하게 생각하는게 도움이 됩니다. 수열 A가 주어질 때, 새로운 항 a를 A의 오른쪽에 붙인다면 세 가지 선택지가 주어집니다. 1. 기존 A의 최대값을 선택한다. 2. a 값을 새로운 최대값으로 설정한다. 3. 기존 A의 최대값에 a를 더한다. 이 세가지 경우에 대하여 동적으로 값을 저장하면서 수열을 확장하는 방식으로 구현하시면 됩니다. # Input N.. 더보기
Python Class에 대한 이해 클래스는 데이터를 소유하고 특정 기능을 수행하는 애들을 이름 짓고 편하게 사용하기 위해서 필수적인 요소입니다. 클래스와 객체는 다음과 같은 방식으로 만들 수 있습니다 1 2 3 4 5 6 7 8 class Super(): def __init__(self): self.a = 1 def func1(self): return 1 S = Super() cs __init__은 객체를 만들 때, 객체를 초기화해주는 함수입니다. S 라는 Super() 클래스의 객체가 생성될 때, S.a 라는 멤버 변수를 가집니다. S.func1()은 S 객체가 실행할 수 있는 함수입니다. 다른 언어와 다른 점은 self라는 말을 사용한다는 것 입니다. 파이썬에는 객체를 가리키기 위한 Indentifier가 필요합니다. 또한 a라는 멤.. 더보기
파이썬 Print 하는 방법 파이썬에서 프린트하는 방법에 대해서 살펴보겠습니다 1. 기본적으로 좌우를 맞춰서 Print하는 방식입니다. for j in range(1,10): for i in range(1, 10): print("%2d"%(i*j), end=" ") print() 더보기
Python Q&A 1 기초 파이썬의 데이터 타입 int a = 1 float a = 1.0 String a = '1' 파이썬의 자료 구조 list A= [1,2,3] tuple A = (1,2,3) dictionary A = {"a":1, "b":2} 더보기
GRASP Design (객체 지향 원칙) General Responsibility Assignment Software Patterns(GRASP) 객체지향 디자인 원칙 어떤 Object가 어떤 Responsibility? Identify the requirements Create a domain model Create design model(Add attributes and methods to the software classes) GRASP: Assign responsibilities to collaboratingn objects Responsibility = "A contract or obligation of a class" Responsibiltly를 구현하기 위하여 클래스에 있는 여러 Method가 조합을 이룬다. Knowing resp.. 더보기
Github Command Command – Github Effect CMD Initialize git init Clone git clone ~~.git Status git status Add git add FILE Add All git add . Commit git commit -m "Message" Push git push -u origin branch Remove rm -rf Folder Move to branch git checkout branch Merge to master git merge master Commit Log git log Remove Added git remove --cached File Login 1 git config --global user.name ID Login 2 git config --glob.. 더보기

티스토리툴바