코테
-
최장 공통 부분수열 (LCS)코테/Dynamic Programming 2022. 6. 22. 19:57
LCS( Longest Common Subsequence) LCS란 가장 긴 공통의 부분집합을 말한다. 예를 들어 x = "ECADADABRBCRDARA" Y = "ABRACADABRA"라는 변수가 있다면 x와 y의 LCS는 다음과 같다. 부분 수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 어떤 문자열 X와 Y가 있다고 할 때 Xn = X1X2 . . . Xn(길이를 n으로 갖는 문자열 Xn) Ym = Y1Y2 ... Ym(길이를 m으로 갖는 문자열 Ym) 이라고 하면 우리가 구하고자 하는 것은 X와 Y의 LCS이므로 LCS(Xn,Ym) := (X[0..n]와 Y[0..m]를 사용하여 만들 수 있는 LCS의 길이)의 점화식을 세우면 된다. LCS(n,m)의 경우를 ..
-
상속과 다형성 with pyhton코테/그 외 2022. 4. 18. 11:39
상속 - 하나의 클래스가 다른 클래스의 속성과 메서드를 얻는 과정을 말하며 새롭게 형성된 클래스는 자녀 클래스, 자녀 클래스가 파생된 클래스 를 부모 클래스라고 부른다. 다형성 - 부모 class에서 상속받은 같은 이름의 method를 overriding하여 기능을 확장하거나 변경하는 것을 의미 - overriding: super클래스를 상속받은 서브클래스에서 super클래스의 메소드를 같은 이름, 같은 반환값, 같은 인자로 메소드 내의 로직을 새롭게 정의하는 것 class Point: def __init__(self): self.x = int(input('x=?')) self.y = int(input('y=?')) def disp(self): pass class Circle(Point): def __i..
-
Trie code by Phython코테 2022. 4. 5. 14:44
class Trie: head = {} def add(self, word}: cur = self.head for char in word: if char not in cur: cur[char] = {} cur = cur[char] cur['*'] = True def search(self, word): cur = self.head for char in word: if char not in cur: return False cur = cur[char] if '*' in cur: return True else: return False
-
동적 계획법(Dynamic Programming)코테/Dynamic Programming 2022. 3. 24. 16:58
Dynamic Programming(동적 계획법) 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성됨 Dynamic Programming의 조건 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 피보나치수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 ..
-
징검다리 건너기 (binarySearch)코테/Search 2022. 3. 17. 18:44
2019 카카오 개발자 겨울 인턴쉽 "징검다리 건너기"를 정말 힘들게 풀었다. 처음에 탐색해야 할 범위가 200,000개가 넘어가는데 감이 안 잡혀서 일단 생각나는 대로 작성했다. 처음 작성한 코드: import sys; sys.setrecursionlimit(100000) result = 0 def solution(stones, k): stop = 0 while stop != k: stop=0 for start in range(0,k): if not stones[start]: stop+=1 continue cross(start,stones,k) return result def cross(now,stones,k): global result stones[now] -= 1 for plus in range(1..