코테 스터디 54일차 TIL + 오늘의 학습 키워드 window sliding

- 오늘의 학습 키워드 window sliding

- 공부한 내용 본인의 언어로 정리하기

그리디 방식: 현재 상태에서 볼수 있는 선택사항 중에서 최선의 선택을 하는 알고리즘

단, 항상 최적의 해를 보장하지는 못한다.

 

그리디 알고리즘의 수행과정
해 선택: 현 상태에서 가장 최선의 선택을 한다.
적절성 검사: minprice 를 찾는데에 있어서 전체 문제의 제약조건에 벗어나지 않는지를 조사
해 검사: 현재 선택한 해의 집합이 전체 문제를 해결할수 있는지를  검사

maxProfit=0;
minPrice=prices[0];

for i=1 to prices.length-1;
   if prices[i] < minPrice:
      minPrice= prices[i]; //가장 작은 가격이 나오면 바꿔치기한다. 그리디 알고리즘원리
      
   else :
      profit = prices[i]- minPrice;
      maxProfit= max(maxProfit , profit)
      
   return maxProfit

---

sliding window

2개의 포인터로 범위를 지정하고 그 범위를 계속 유지한 상태로 그 범위를 한쪽으로 옮겨 가면서 문제해결

투포인터로 생각하고 양쪽 움직이는걸 생각했는데 그건 아니었음

 

- 오늘의 회고

  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

ArrayList 와 stack의 차이점 

ArrayList는 동적배열 stack처럼 쌓이는 구조가 아니다. 굳이 자료구조에 넣지 않고 풀리는 간단한 문제도 있다.

 

sliding window인거 판별하는 법

연속된 배열에서 최적값을 찾아야함

왼쪽 포인터와 오른쪽 포인터가 한방향으로 움직인다.

조건에 따라서 window 크기를 조절하면서 탐색한다.
  - 어떻게 해결했는지
  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지