[WEEK02] DAY15 & 피보나치수열, 파라메트릭서치, DP(동적프로그래밍)

https://velog.io/@yerimii11/WEEK02-DAY15 2021년 11월 16일에 작성된 게시글 아카이브입니다.  (사유: 블로그이전)

[WEEK02] DAY15 & 피보나치수열, 파라메트릭서치, DP(동적프로그래밍)

---

 

MONDAY!!

• 8번까지 복습 V
• 파이썬 교재 3, 4과 읽기
• 컴퓨터시스템 교재 읽기
• 이해 한 문제는 끝까지 코드 짜보고 퇴근하기~!

1. 인프런도 보기 (코드구현)
2. 힙큐, 우선순위 큐

-밑에 내용 노션에도 정리하기

---

* 피보나치 수열

제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다. 이 둘 사이에는 시작점이 다르다는 정도를 빼면 사실상 동일하다.

그 중에서 16 번째 항까지만 나열해 보자면 (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
이렇게 간다.

수학의 수열 파트에서 잠시 배우는 수준이지만 컴퓨터 계열로 진학할 경우 정말 질리도록 보게 된다. 프로그래밍 언어에서 재귀함수를 배우면서 과제로 반드시 한 번은 하게 된다. 재귀함수로 간단히 구현되지만, 메모이제이션(Memoization) 없이 구현할 경우 실행시간이 안드로메다로 증가하게 된다. 반대로 메모이제이션을 할 경우에는 필요한 메모리가 O(n) 에 비례해지는 단점이 있다. 단순히 직전과 그 전의 값만 저장하는 방식으로 반복문이나 꼬리재귀 최적화가 된 재귀를 할 경우 시간복잡도 O(n)에 공간복잡도 O(1)도 가능하다. 다만, 정말 큰 임의의 n에 대한 피보나치 수를 구해야한다면, 행렬을 이용하여 시간복잡도 O(log n)에 공간복잡도 O(1)로 구현할 수도 있다. 좀더 높은 레벨의 프로그래밍에서는 피보나치 힙(Fibonacci Heap) 같이 자료구조나 알고리즘 최적화에 피보나치 수열의 성질을 우려먹는 경우를 많이 보게 될 것이다.

---

출처 나무위키
11053 가장 긴 증가하는 부분 수열 관련 문제를 풀다가 DP를 접하게 되면서 같이 언급되었어서 다시 정리 ㅎㅎ

---

* 파라메트릭 서치

https://sarah950716.tistory.com/16
파라메트릭 서치는 문제를 풀어나가는 과정이 바이너리 서치(이분 탐색)와 매우 흡사합니다. 파라메트릭 서치는 의외의 문제들에 적용돼서 최적화 문제들을 조금 더 쉽게 풀 수 있게 해줍니다. 파라메트릭 서치의 핵심은 결정 문제입니다. 해당값이 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야(즉, 결정 문제를 쉽게 풀 수 있어야) 최적화 문제를 파라메트릭 서치로 풀 수 있습니다. 또한, 정답이 될 수 있는 값들이 연속적이어야 파라메트릭 서치를 이용할 수 있습니다. 예를 들어, 어떤 조건을 만족하는 최솟값을 구하는 최적화 문제가 있다고 해봅시다. 정답이 될 수 있는 값들이 연속적이어야 한다는 말은, 정답이 x라고 했을 때, x이상의 값들은 모두 조건을 만족해야 한다는 것을 의미합니다.

출처: https://sarah950716.tistory.com/16 [주니어 개발자의 대나무숲]

최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(decision problem)로 바꾸어 푸는 것이다.
예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
https://velog.io/@lake/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search

파라메트릭 서치를 사용하기 위한 조건들
1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우
2) 가능한 해의 영역이 연속적이어야 한다.

2110 공유기 문제 풀이와 관련 됨!

---

* dp 다이나믹 프로그래밍(동적 프로그래밍)

https://galid1.tistory.com/507

---

* bisect

bisect_left(a, x)
정렬된 a에 x를 삽입할 위치를 리턴해준다. x가 a에 이미 있으면 기존 항목의 앞 (왼쪽)의 위치를 반환한다.

bisect_right(a, x)
bisect_left와 거의 같은 함수인데, 이번에는 x가 a에 이미 있으면 기존 항목 뒤 (오른쪽)의 위치를 반환한다.

출처: https://folivora.tistory.com/83 [나무늘보의 연구실]

https://velog.io/@woo0_hooo/python-Bisect-%ED%95%A8%EC%88%98%EB%9E%80

---

* 스택, 큐

스택은 리스트에서 최근에 들어간 후발대가 먼저 빠지기 때문에 바로 빼도 되지만 (후입선출)

큐는 리스트로 큐를 구현하게되면 pop으로 끝에서부터 빠질때 리스트를 첫번째부터 다 돌아서 보기때문에 pop 자체가 O(N)이라 시간복잡도가 비효율적이니 라이브러리를 사용하는게 좋다. (선입선출)

---

시간복잡도

1. 성공코드(O(N)): 각 원소가 스택에 들어가고 나오는 연산이 한 번씩만 수행된다.
2. slicing(O(N^2)): 각 원소마다 slicing을 수행하는데 대상 원소의 수가 1부터 N까지 계속 증가하고 slicing의 시간복잡도는 원소의 수와 비례하므로 O(N^2))이 된다.
3. index(O(N^2)): 각 원소마다 index함수가 해당 원소를 찾기 위해 리스트를 처음부터 끝까지 순회하기때문에 역시 O(N^2))가 된다.

---

저번에 시간복잡도에 대해서 정리했었지만 추가로 더 알게 된 사항!
바로 위에 큐 설명에 썼듯 pop index순회시에 고려해야할 시간복잡도 관련 문제때문에 추가해보았다.!

---

코드 복습

2470 두 용액

 

11053 가장 긴 증가하는 부분수열

 

8983 사냥꾼

 

18258 큐 2

마무리 중

9012 괄호

 

17608 막대기 (스택)

스택 문제인 걸 놓쳐서 처음 스택을 안쌓고 문제를 풀었음. 다시 풀어보기

2493 탑

맨밑 아래 방식으로 풀려니 pop을 사용 안해서 시간초과가 나올 가능성이 커져서
처음 생각을 메모한 맨위 방식으로 append, pop사용해서 코드 마무리 할 것.
끝에서 부터 비교하고, 작은 수 pop으로 날림.

11866 요세푸스 문제0 (큐)

앞에 2개 바로 지우고 뒤로 붙이는 방법으로 작성해보기
num = [] 에 for문 돌려서 1~7 리스트 만들지 말고
nums = deque(range(1, n+1)) -> 으로 작성해서 1~n까지 만들면서 바로 덱 처리 하기

---

2021.11.15 월

오늘의 이야기

우리 팀이 2명이다 보니 다른 팀에 비해 전체적인 문제를 훑는 속도가 느린 것 같아 30분~ 1시간 제한을 두고 후루루룩 넘겨보면서 풀고 있다.
그러다보니 나는 문제를 어떻게 풀지 구상까지 다 된 상태에서 코드작성은 미룬채 넘어가는 경우가 다반사¨
그래서 화요일까지 주어진 문제를 다 훑어본 뒤 시간을 더 내서 코드 완성 해보고 복습까지 최대한 해볼 계획이다!!

그리고 월요일부터 너무 피곤해서..
뻗음 X.X
도저히 안되겠어 굿나잇