선릉역 1번 출구

최장 증가 부분 수열이란? 원소가 n개인 배열의 일부 원소를 골라내 만든 부분 수열 중에서(상대적인 순서는 유지) 길이가 최대인 수열을 의미한다. ex) {4, 2, 3, 1, 6, 5}이라면? {2, 3, 6}이 된다. 가장 기본적인 해결 방안은 dynamic programming을 사용하는 것이다. dp[i] : i까지 인덱스 중 가장 긴 수열의 길이 dp = [1] * n for i in range(n): for j in range(i): if ls[j] 2, 1 번째 -> 3, 2 번째 -> 3, 3 번째 -> 4, 4번째 -> 4가 된다.

동적 계획법이라고 불리는 다이나믹 프로그래밍에 대해서 알아보자. 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로, 부분 문제 반복과 최적 부분 구조를 가지고 있는 문제를 일반적인 방법에 비해 적은 시간안에 풀 때 사용한다. 기본 structure는 앞서 말한 것처럼 문제를 여러 하위 문제로 나눠 풀고, 그것을 결합해 최종적인 답을 도출해내는 것이다. 이 방법을 사용하면 계산횟수를 획기적으로 줄일 수 있어 하위 문제의 수가 많을 때 유용하다. 이 과정에서 메모이제이션(memoization)이라는 기술이 사용된다. +메모이제이션: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 빠르게 하..

python에서 queue 사용하는 방법 *queue는 FIFO의 구조를 가지고 있다. (선입 선출) 1. list 사용하기 list에서 push연산은 append를 사용해 구현할 수 있고, pop연산은 pop(0)을 사용해 구현할 수 있다. 그러나 pop연산의 시간복잡도는 O(N)이어서 큐에 적합한 자료구조라고는 볼 수 없다. 2. collections module의 deque 사용하기 deque는 double-ended queue로 양방향 큐이다. 앞, 뒤 양쪽 방향에서 데이터를 추가하거나 제거가 가능한 큐이다. from collections import deque deq = deque() # 데이터 push deq.append() //데크의 오른쪽 끝에 데이터 push deq.appendleft()..

사전적 정의의 재귀란 어떤 것을 정의할 때 자기 자신을 참조하는 것을 말하고 컴퓨터에서는 재귀 호출(recursion call)의 형태로 많이 사용된다. 장점: 코드의 간결함 단점: 무한 재귀호출의 위험성 재귀적 정의의 구성 1. 기본 단계: 몇몇 초기 원소들을 기술한다. 2. 귀납적 단계: 이미 존재하는 원소들로부터 새로운 원소들을 구성하는 규칙을 제시 가장 많이 사용하는 코드인 factorial code이다. def factorial(num): if num