[week02/03.25]TIL

오늘 한줄 요약

부족한 깊이감, 어떻게 채울까?

오늘 공부한 것

• CSAPP(해시 충돌과 체인법, 지역성의 원리, 프로세스 vs 스레드)
• 분할 정복
• deque 자료구조

새로 배우게 된 것

CSAPP

해시 충돌

두개 이상의 아이템이 동일한 저장 공간에 지정되는 현상
해시 함수의 특성상 동릴한 해시값을 가질 수 있기 때문에 발생함

• 체인법
  각 버킷에 연결리스트를 사용하여 Key:value를 저장하는 방법
• 오픈 주소법
  비어있는 버킷을 만날 때까지 해시함수를 실행하는 방법

위 두가지로 해결할 수 있다.

지역성의 원리

프로그램이 메모리 접근시 특정 부분을 집중적으로 사용하는 경향.

• 시간적 지역성
  한번 접근된 데이터는 가까운 미래에 다시 접근
• 공간적 지역성
  메모리의 특정 주소에 접근 후 그 주변 주소 데이터에 접근될 가능성이 높은 것

캐시 메모리는 이 지역성 원리를 활용, 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시 저장

분할 정복

말그대로 분할하고 작은 범위로 나누어서 문제를 해결하고 이를 다시 조합하여 큰 문제를 해결하는 것,
다만 문제를 풀면서 어떤 것을 분할할까 라는 고민을 했는데
주로 인덱스를 분할하고,만약 인덱스가 고정되어있지 않다면,
거리나 다른 부분들을 고려하는 방향으로
분할 정복 문제를 풀어야겠다는 것을 팀 스터디를 통해 배움

이분 탐색

이분 탐색도 어찌됐든 찾고자 하는 것을 탐색할때 범위를 절반씩 줄이며 log N 의 시간으로 더 빠르게 찾기 위함이다.

https://www.acmicpc.net/problem/8983

위 문제도 결국 사대를 찾는 과정을 이분탐색으로 진행한다는 핵심 키 아이디어를 떠올리지 못해서
접근조차 하지 못했다.

공부하면서 어려운 점

그냥 크게크게 보면서 원리를 이해하는 것은 잘 되는데,
입력값이 바뀌거나, 특정 세부 기능을 구현하는 것에 있어서 여전히 한계를 느낀다.

이런 깊이감을 얻기 위해 들어온 만큼, 내일은 더 깊이에 집중하여 공부해보자.