[정글 SW사관학교] WEEK2. 풀이 고민 소요 시간에 대한 이분탐색

🤔회고

 

팀활동 방식에 대한 고찰

 

매주 새로운 주제 그리고 사람들과 협업을 하다보니 prev 조에서의 방식이 current 조에서 해답이 될 수 없었다. 1일차에는 같이 공부하고 풀기 > 2일차에는 개인 플레이 > 그리고 3일차 드디어 절충안을 찾을 수 있었다. WEEK2 1조가 찾은 팀활동은 다음과 같다. 

1. 개념 공부 후 공유
2. 주제별로 1문제씩 (새로운 문제로) 함께 문제 분석 시작 및 로직 세워보기 (이때, 문제를 풀기 위한 아이디어가 나오면 해당 아이디어가 채택되고, 반례는 없는지, 예외 처리는 어떻게 할지 등을 논의합니다)
3. 허점 없이 로직이 세워지고 코드를 구현해보는게 가장 베스트겠지만, 코드를 구현해보면서 디버깅을 통해 예외 처리하는 경우도 있어서 30분 정도 시간 제한 후 구현을 시작한다.
4. 코드 리뷰 및 문제 마무리

구현 방법에서 헤매는 팀원은 감을 잡을 수 있고, 문제를 속도감 있게 혹은 진득하게 풀고 싶은 팀원마다의 성향을 존중할 수 있게 되었다. 그리고 무엇보다 혼자 오랫동안 막힐 때는 꼭! 질문을 통해 뚫어주는게 중요하다는 점! (우리에게는 매주 새로운 과제가 물밀 듯 쏟아지기 때문에.. 어느 정도의 속도전은 필요하다 ㅎㅎ)

 

현재 WEEK2 1조의 최적의 방식을 찾은 것 같아 재밌었다. (후반부에 후기를 다시 적어보는데, 자주 모이지 못해 아쉬워하는 팀원도 있으셨다. 하지만 내 코도 석자라 죄송한 마음만 간직했다)

 

백준 #1916 그리고 #1707 문제 분석

 

풀이 고민 소요 시간에 대한 이분탐색

 

Q. 다음을 만족하는 최적의 '소요 시간'을 구하시요

- 문제 유형: 이분 탐색

- target; 알고리즘 풀이 고민 소요 시간

- condition; 풀어야하는 최소 문제 수

 

제한된 시간 내에 방대한 문제들을 풀어야하다보니, 저번주와 달리 이번주에는 타이머로 시간 체크하며 풀고 있다. 문제 분석에만 20분 정도 소요되면 블로그에서 아이디어만 얻은 후 구현해보고, 구현에도 20분 정도 소요되면 답을 보고 이해하는 방식을 채택해보았다. 이렇게 최적의 시간을 찾아가는 방식이 마치 이분탐색과 같아서 포스팅 제목을 위와 같이 작명해보았다. 아직 내 학습 방법은 서치 중이고, 최적의 해를 찾게되면 효율이 높아지지 않을까 기대해본다.

 

windows Free Timer 사용 예시

 

 

나는 아직 골드 유망주하고 싶은데,

 

알고리즘 주간 10일째인데, 실버2에서 골드5까지 승급했다.

(24.08.19 13:38 스샷 기준) 풀이 10일차 스샷 .

 

나는 아직 Silver도 버거운데 정답을 봐서라도 어떻게든 골드 ~ 플래티넘 문제들에 대한 진도를 나가서인 듯 하다. 진실된 Gold 등급은 좀 더 시간이 필요하다고 느낀다. 그래도 과거 못 풀던 그래프 탐색은 이번주의 재밌는 과제로 편식하 듯 먼저 섭취하고 있다. 이게 기본 틀에서 어떻게 변주하는지 발견하는 묘미가 있기 때문이다. 난이도 상 문제가 여럿 남아있다. 하지만 기본기를 다지고 싶어서 문제 유형에서 실버 문제들을 풀어보고 있다. 헌데 '시간초과', '틀렸습니다' 향연에 안그래도 꺾인 공부 의지가 탈탈 털렸었다. 그런 날은 집에 일찍 들어가서 에너지 충전을 하고 아침 일찍 나오곤했다. 컨디션 이슈로 이전의 공부 텐션이 나오지 않는게 속상하지만, 5개월 동안 그리고 이후에도 공부를 해야하니깐 아침 산책 거르지말고 문제 못 푼다고 속상해하지말고 천천히 나아가보자. (후일담이지만, 충분히 쉰 덕분인지 기초부터 다지고자 수준에 맞는 Silver 문제를 풀며 문제별 한줄평을 남기는 중인데 재밌고 텐션 회복한 것 같아 다행이다)

 

[백준/python] stack 유형 모음집 및 접근 컨셉

 

 

저번주보다 한 발자국 성장했다면,

이번주 시험에는 3/4 솔 했다. 어제 문자열 폭발 문제를 풀어본 행운과 더불어 어려운 문제 또한 이분탐색 + bfs 접근방식까지는 이해했기 때문이다. 무엇보다 잠깐 공부하고 그칠게 아니기 때문에 공부 방식을 찾은 것만으로도 잘했다고 생각한다. 사실 코드 리뷰할 때 왜 부족하게 이해하고 말하냐는 지적을 받긴 했지만, 나는 조금 슬프고 굴하지 않을 것이다. 내 부족한 부분들을 채우면 나는 강력해질 것이기 때문이다. 나는 이곳에 틈을 매우고 단단한 벽돌을 만들기 위해 들어왔다. 

 

---

📅필수 목표

[필수 과제]

✅ 컴퓨터 시스템 교재; WEEK02: 1.5. 캐시가 중요하다 ~ 1.7. 운영체제는 하드웨어를 관리한다

 

[240816 금]

✅ WEEK1 개발일지 포스팅

✅ 스택&큐 개념 공부 w. 포스팅

✅ 스택&큐 문제 풀이; 문제 그룹당 1시간씩 타임어택; 꽤 쫄깃하고 재밌음

✅ 앞서 skip한 문제들 풀기 (#2504, #3190, #11866)

✅ stack Exception 정리하기 (이미 포스팅 완료되어서 수정으로) + Notion 꿀팁도 정리하기

 

[240817 토]

✅ [개념 공부] 그래프 탐색 기본, DFS, BFS

✅ DFS 순회 종류별 구현 방법 리서치

✅ [문제 풀기] 그래프 탐색 기본 (타이머와 함께 문제당 10분 내외 시도)

✅ 15시/ 개념 공유 및 문제 풀이 #1991 #5639

✅ [문제 풀기] DFS (일요일거 미리 당겨 풀기)

 

[240818 일]

✅  7시 ~ 17시/ 외출 (가을, 겨울 옷 채비)

✅ 19시/ [팀활동] BFS #1916 같이 풀어보기

✅ [문제 풀기] BFS #2665 부터 (토마토 while 안돎. 여기부터 살펴보기)

 

[240819 월]

✅ 9시/ 팀활동 DFS #1707 같이 풀기

✅ 위상정렬 개념 정리 > #2252 개인 풀이

✅ 우선순위큐 개념 정리 > #1655 개인 풀이

✅ 16시/ 팀활동 위상정렬 개념 공유 및 #2637 같이 풀기

✅ [문제풀기] (상 제외) BFS, 위상정렬, 우선순위큐 마무리

 

[240820 화]

✅ 9시/ 팀활동 우선순위큐 개념 공유 및 #1655 같이 풀기

🔼 상문제 풀기 (스택 2문제만 품) > 낮은 난이도로 다른 문제 푸는 중

 

[240821 수]

✅ 컴퓨터 시스템 교재; WEEK02: 1.5. 캐시가 중요하다 ~ 1.7. 운영체제는 하드웨어를 관리한다

✅ [블로그] 문제 유형별로 난이도 낮은거 풀고 한줄평 남기기 (유형별 패턴 뽑는게 목적) - 스택, dfs, bfs

✅ 잔여 문제 난이도 정답 풀이 보기 - dfs, bfs

 

[240822 목]

✅ #1916, #18405 다익스트라 알고리즘 풀이 보기
✅ 10시/ 시험 및 #16120 발표 (앞에서 발표할 때, 풀로 코드 작성하도록 코멘트해주심)

✅ WEEK2 포스팅 완료 및 다면평가

 

🔥추가 정리 필요

[코드 리뷰] 추가 정리 필요함

- #15573 이분탐색이 가능한 이유 = 적정해를 찾는 과정 monotic; min(Di) ~ max(Di)

-- O( M*N*log(max(Di)) )

 

- 스택 vs 큐 vs 우선순위 큐

-- 스택 상황; 이전 값 조회, 브라우저 히스토리, 함수 call, PushDown 오토마타

-- 큐 상황; 줄, 들어온 순서대로 서빙

-- 우선순위 상황; 높은 사람 먼저 서빙, 곧 정렬이 가능함. heap 정렬

 

- 그래프

-- vertex, edge 

-- 어떤 자료구조로 표현되는지? 인접리스트, 인접 행렬

-- 종류? 무방향(곧 양방향), 단방향

-- simple graph vs multi graph (끊기는 컴포넌트 수와는 다름)

-- multi graph = 인접 리스트 유리 (인접 행렬도 가능하지만 tuple 데이터가 들어가게됨)

 

- 그래프 vs 트리 (simple graph, #E = #V-1 (귀납법) )

-- 정의 방법 : child로 갈지 parent로 올라갈지에 따라 structure는 다양하게 정의할 수 있음

 

- 스패닝 트리: 다시 공부해야함

 

 

[추가 목표]

- 위 빨간색 글씨 개념 다시 찾아보기

- 위상정렬 난이도 낮은걸로 기출 풀기 (상 pass 이해 안됨)

- [스택 유명한 문제] #6198 옥상 정원 꾸미기

- DP vs 재귀 차이점 [참고자료](https://m.blog.naver.com/vail131/221943619686)

- 코드트리 서비스 가입

- 트리 insert, delete 등 메소드 구현 실습 필요함

- 스택으로 DFS 많이 어려운데?? 특히 전위순회는 어찌 어찌 구현했는데, 중위/후위는 어렵네..

def preorder(root):
    stack = deque(root)

    while stack:
        root = stack.pop()
        child_nodes = tree[root]
        print(root, end="")
        if child_nodes:
            for idx in range(len(child_nodes) - 1, -1, -1):
                child = child_nodes[idx]
                stack.append(child)

 

 

[개념 공부 다 하고 시간 남으면]

- TED 추천영상 보기; https://www.youtube.com/watch?v=arj7oStGLkU

- WEEK1 & 시험 본거 안보고 다시 작성해보기

- 임시저장 포스팅 (3 주제; JWT > 백준 설정 > itertools 직접 구현)

 

 

📝메모