✨ 이번 주 핵심 키워드 ✨
: 분할정복, 이분탐색, 스택, 큐, 우선순위 큐
천방지축 어리둥절 빙글빙글 돌아가는 하루하루들을 견뎌내고 드디어 2주차 정글이 끝났다. 이번주 개발일지도 우리 조원들 이야기를 빼놓을 수 없지.
이번엔 3명이 한 팀이었다. 이번 문제 난이도가 확 올라서 팀원들이 곁에 있는게 많이 의지가 됐다.
뱀이 사방을 기어다니는데 대체 왜 안 잡고 놔두는지, 도현이는 집이 그렇게 많으면서 공유기 값은 왜 아끼고 있는건지 내 상식으로는 이해할 수 없는 문제들이 많아서 팀원들과 하루에도 몇 번씩 모여 함께 토론하고, 고민하고, 알게된 것은 서로 공유했다.
그렇게 문제 해결에 집중하며 하루하루를 보내는게 너무 만족스러웠다. 이번 팀원들과 유난히 소통이 잘돼서 더 그랬던 것 같다. 비록 '원 영역' 같이 끝까지 못 풀었던 문제들도 있었지만, 해결하기 위해 고민하고 여러방향으로 생각하는 과정들이 즐거웠다. 이 기쁨을 모두 우리 팀원들에게 돌립니다. 사랑해요.
++) 근데 아무리 그래도 원 영역은 좀 너무했다. 내가 살면서 이렇게 구질구질하게 매달린 적이 없었는데 끝까지 내게 마음을 열어주지 않았다...
두 번째 시험은 빵점이었다.
시험 전에 누군가가 자기는 빵점 맞을 준비를 끝냈다구 해서 깔깔 웃었는데 그게 내가 될 준 몰랐다.
하지만 난 이정도로는 기죽지 않는 여자. 이순신 장군님께도 아직 열 두척의 배가 남아있었듯 나에게도 아직 2주의 알고리즘 주간이 남아있다. 2주는 곧 14일이니까 아주 충분하지.
시험 코드를 깃허브에 올릴 때는 좀 민망해서 이번 주 내 리뷰어에게 빵점짜리의 리뷰어가 된 걸 축하한다고 편지를 썼다. 모든 조언은 내 피가 되고 살이 될 테니 알고 있는 것들을 적어주면 감사하겠다고.
그래놓고 정작 나는 점심먹고 기분 좋아서 리뷰하는 걸 잊어버렸다... 미안합니다...
재귀는 아직도 어렵고, 이분탐색은 중간값을 설정하기 힘들고, 스택하고 큐는 여전히 어떻게 사용해야 할지 감이 안오지만 저번주에 비하면 정말 장족의 발전을 했다. 이번 주도 힘내서 공부해보자~~!
1. 이분탐색, 분할정복
- 이분탐색 시 정렬 먼저 하고, 탐색 대상이 되는 값을 잘 설정하자.
- 이분탐색으로 풀기 어려운 문제는 투포인터로도 시도해보자.
- 분할정복(divided and conquer) 알고리즘
: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법.(정렬 알고리즘 중 퀵 정렬, 합병정렬, 이분탐색, 고속 푸리에 전환 등이 대표적임)
2. 스택
- 스택 : 가장 나중에 추가된 항목이 가장 먼저 제거되는 후입선출 구조
- 리스트 대신 스택 자료구조를 사용하면 리스트 길이를 늘리는 작업이 없어지므로 성능을 향상시킬 수 있음.
- for문 사용 시, 문자열을 입력받는 코드가 for문 밖에 있으면 시간복잡도가 증가함. 문자열을 읽어오는 동시에 스택을 관리하는 것이 좋음.
- for~else : for문이 break되지 않고 정상적으로 종료될 경우, else 블록을 실행하게 됨.
- 후위연산자(postfix expression)
- 우리가 평소에 사용하는건 중위연산자(infix)
- '4+7' 을 후위연산자로 표현하면 '4 7 +' 이런 형식이 됨.
- '2 4 7 * 2 /' 이런식들은 일단 앞의 2부터 차례대로 스택에 넣었다가, 연산자가 나오는 순간 가장 최근의 두 값을 꺼내어 계산하고, 다시 넣는다. 이 과정을 반복함.
3. 큐, 우선순위 큐
- 큐 : 선입선출 자료구조(from collections import deque)
- 우선순위 큐 : 우선순위(오름, 내림차순)대로 자료를 보관하는 큐
- 파이썬에서는 heapq라는 내장 라이브러리로 우선순위 큐 구현이 가능하다
- heapq의 heappush 메서드는 임의의 리스트에 자료를 우선순위를 부여하면서 저장
- heappop 메서드는 그 리스트에서 우선순위가 가장 높은 자료를 출력
- heapq 모듈을 사용하면 '최소 힙'을 쉽게 구할 수 있으며, 이를 이용하여 입력받은 값에 -부호를 붙여준다면 가장 큰 수가 가장 작은수가 되어, 최소값을 출력하면서 다시 양수로 바꿔주면 최대값을 구할 수 있다.(한 문제에서 최대힙과 최소힙을 두 개 만들어 사용 가능)
- heap도 정렬 기준이 매우 중요함!
