230209 모의코테(그리디) 및 스터디 내용 정리

deslog commented 1 year ago

(브랜치) greedy/8/mock-coding-test
(커밋 스타일) [Solve] 이지수 lc title 문제풀이(#8)
(파일 위치) greedy/이지수(각자위치)/lc_title

🔥 풀이할 Leetcode 문제

leedcode 그리디 문제 모음

[x] lc 611 valid triangle number
[x] lc 134 gas station

⚫️ 스터디 내용 정리

(브라운의견) 리트코드에서 난이도 easy, medium, hard가 어느정도인지 사전에 알아오는게 필요할듯!!
(레이몬드) 고민했던 부분 정리해서 올려주기~ 공유하기!
(잭) 병든나이트 다시 풀어보기,,,

▪️ 참고사항

다음주 레이몬드(여행), 윌(인턴) 으로 인해 스터디 불참, 과제는 참여!
다음주는 잭과 브라운 둘이서 오프라인으로 진행하던지 하겠습니다 ~.~ 🫠

deslog commented 1 year ago

어 커밋메시지 제가 규칙정해놓고 제가 어겼네용,,, 다음부터 지킬게요 ㅋㅋㅋㅋ 후하 하핫

SH0123 commented 1 year ago

@SeonJeon @deslog @sunshiningsoo 다들 이번에 최소 신장 트리 (MST)의 크루스칼 혹은 프림에 대해서 공부해봤잖아요! 최단거리 구하면서요! 자신만의 언어로 해당 알고리즘에 대해서 정리하고, 코드도 작성해보고 그 글을 어딘가 (개인 노션 혹은 블로그)에 다같이 작성해보는건 어떤가요? 혼자 하려고 늘 생각은 하는데 잘 안돼서 ... 2주라는 여유로운 시간(2월 25일까지)을 갖고 공부하고 정리하고 모르겠는 부분 공유하면 좋을 것 같아요 ~ 이슈나 discussion 만들어서 도움되는 링크도 서로 공유하면서요 ~

SH0123 commented 1 year ago

제가 오늘 문제를 풀면서 어떻게 접근해나갔는지, 왜 답에는 도달하지 못했는지에 대한 기록을 해놓겠습니다

LeetCode 611 valid triangle number
- 먼저 삼각형이 형성될 수 있는 기본 조건을 생각해보자 -> a + b > c (가장 긴 길이)
- 조건에서 배열의 길이가 10^3 이하네? 1초에 10^8만큼을 계산할 수 있으니 N^2까지는 사용할 수 있겠다!
- 길이 세개를 갖고 판단해야하는데 그냥 구현하면 N^3이 될테니 그러면 안되겠다
- 길이가 제일 긴 것을 for문으로 잡아두고, 나머지 두개의 값은 투포인터를 사용해볼까?
- 투포인터를 어떤 기준으로 이동시켜야하는지 감이 안잡히네 포기...

-> 투포인터의 start와 end 지점을 잡아놓기는 했지만, 과부화로 인해.. 어떤 조건에서 어떤 변수를 +, - 해야하는지 생각하지 못했습니다.. 투포인터 조건에 대한 생각을 좀 더 열심히 해봐야겠어요 시간복잡도 N^2으로 나올만한 것을 N으로 줄일 수 있는 방법이 또 뭐가 있는지도 차근차근 공부하면서 정리해봐야겠어요

LeetCode 134 gas station
- 배열의 길이가 10^5 이하네? 시간 복잡도 N만큼만 사용할 수 있겠다
- 하나의 정류장에서 다음 정류장으로 이동할 수 있기 위해서는 어떤 조건을 만족해야할까? 가스 정류장에서 얻어오는 gas보다 cost가 크면 안되겠구나
- 그렇다면 둘 사이의 차이를 미리 계산해서 배열에 넣어두자
- 4번 정류장에서부터 정류장 하나씩 이동하면서 계산해보자. 배열에 있는 값을 그냥 더해보면 되는구나? 그렇다면 배열의 값을 다 더한것이 0보다 크면 일단은 문제의 답이 있겠다
- 4번부터 시작해서 어떤 정류장까지 갔을 때 cost - gas가 0보다 작아지는지 확인하기 위해서는 4번 기준으로 하나씩 더해봐야하는데... 기준점을 계속 바꿔볼 필요도 있고, 기준점을 시작으로 배열 전체를 탐색할 필요도 있어서 이중for문을 벗어나지 못하겠다... 어떻게하지 ... 포기

-> 값이 unique 하다는 조건에 대해 깊이 생각해보지 않았다. 일단 gas - cost의 배열들중 양수값들이 정답 후보가 된다는것은 생각해봤지만 그 이상을 생각해보지 못한게 문제였다. 그리디답게 굳이 모든 배열을 하나씩 탐색할 필요가 없는 부분이 있을 수 있겠다는 생각을 잘 해보고 파악해보자 근데 제가 포기했던 부분인 for문을 포인터를 이용해서 줄일 수 있기는 하더라구요! 관련링크

@deslog 브라운의 칭찬과 격려와 응원 감사합니당 ~ 앞으로도 열심히 하면서 브라운은 빠르게 스터디에서 나갈 수 있도록,,, ㅋㅋㅋ 저는 계속 열심히 해서 취준 기간을 줄일 수 있도록 해봅시다 ㅎㅎ

deslog commented 1 year ago

제가 오늘 문제를 풀면서 어떻게 접근해나갔는지, 왜 답에는 도달하지 못했는지에 대한 기록을 해놓겠습니다 @SH0123

문제를 생각할 때 조건을 먼저 보고, 시간적인 측면에서 먼저 고려하는게 인상깊어요. 전 이렇게 안되어서,, 효율성 테스트에서 허덕이는 경우가 굉장히 많았거든요! 그리고 생각까지는 잘 뻗쳐 나갔는데 대부분 구현하는 부분에서 인덱스를 이리저리 가지고 노는 과정에서 조금씩 막히셨던것 같네요! 저도,, 이 과정이 어려워서 쓸데없이 O(N)으로 풀 수 있는건데,, 이중 for문을 남발하면서 O(N^2) 등등 덜떨어지는!! 알고리즘을 구현하곤 합니다...

논리적 사고 흐름을 보니, 대부분 솔루션에 거의 다접근하신 것 같은데 조금만 더하면 그리디 씹어먹기 쌉가능일것같은데요?!! 오늘 풀어봣던것 공유해주셔서 감사합니다아아아 ~~ !~! ~ 저랑 비슷한 고민들을 한 것도 보여서 너무 공감됩니다!

HotCodeBreakers / CodingTest