사실 1주차는 너무 쉬웠다. 이렇게만 나오면 너무 수월할것 같다고 생각했는데... 이번 주차는 문제의 난이도가 정말 1주차랑 천지차이였다.
1주차 공부 키워드
이분 탐색
이분 탐색은 자신이 찾는 값이 정렬된 리스트 안에 있는지 O(log N) 만에 찾아낼 수 있는 굉장히 혁신적인 기술이다.
학부 때 자료구조 수업에서 교수님이 정렬 알고리즘이 발달한 이유는 사실 이 이분 탐색을 사용하기 위함이라는 말씀도 하셨다.
이분 탐색의 개념은 먼저 배열을 둘로 나눠서 중간값을 찾고, 이 중간값이 찾고 있는 값보다 크다면, 이 둘로 나뉜 배열 중 큰 부분만 찾고, 작다면 배열의 작은 부분에서만 탐색을 이어나가는 방식이다.
이 방식은 자신이 찾고 있는 값이 배열에 없더라도 만약 찾고 있는 값이 배열에 있었다면 들어있어야 할 인덱스도 찾을 수 있다.
위 문제들이 이분탐색의 키워드의 문제로 나왔는데... 나무 자르기부터 쉽지가 않다.
단순히 값이 있는지 없는지 찾는 것이 아니라 조건을 만족하면서 최댓값을 찾는 문제인데, 이는 공유기 설치, 두 용액, 사냥꾼 등도 같은 방식이었다.
처음에는 문제 풀이 방식이 제대로 잡혀있지 않아서 골머리를 앓았지만, 조금 풀다 보니까 패턴이 보였다.
분할 정복
분할 정복... 말 그대로 문제들을 작은 부분으로 나누어 문제를 해결한 뒤 합치는 방식인데... 이게 말만 들으면 참 쉬워보이지만 어떻게 잘 나누느냐가 중요한것 같다. 나눠 봤자 적절하게 나누지 않으면 결국 시간초과 나는 문제가 한트럭이다.
그래도 지난주에 배운 재귀에서 크게 벗어나지 못하니 열심히 풀어봤다.
여기서 히스토그램과 두 점 문제는 플래티넘이다.. 특히 두 점 문제는 진짜 도저히 혼자는 못 풀겠어서 GPT에게 힌트를 받고 겨우 풀었다. 분할 정복 뿐만 아니라 수학적인 개념 또한 필요한 것 같다.
스택
스택이야 선입후출의 개념을 가진 가장 기본적인 자료구조이이다.
이번 백준 스택 문제들도 사실 패턴이 보인다. 별로 어렵지는 않았지만 문제 하나가 어째 풀리지가 않는다
다른 문제들이야 수월하게 풀었는데... 원 영역은 진짜 절대 풀리지가 않았다... 디버깅만 이틀을 꼬박 해봤는데 반례도 찾을수가 없었고... 혹시 있다면 https://www.acmicpc.net/board/view/157967 여기에 부탁한다 ㅠㅠ
결국 반례가 달리긴 했지만... 디버깅이 너무 빡세다. 정체를 밝힐 수 없는 고수로부터 힌트를 얻어 트리 구조로 결국 풀었다!! 트리를 재귀적으로 탐색해서 풀었는데 재귀 문제는 결국 스택으로 풀 수 있는 문제니까 나중에 스택으로 변경하기로 했다.
어떻게 풀었는지는 다음 블로그를 참고하자. 동기가 작성한 포스트인데 내 코드랑 거의 유사하다.
학부때 배운 스택의 가장 큰 효용성은 후위 표기 계산식이 아닌가 한다.
이 후위 표기 계산식으로 컴퓨터는 괄호나 곱셈과 덧셈을 순서대로 할 수 있다. (내부적으로 정말 그렇게 구현되어있는지는 잘 모르겠다)
큐
큐는 선입선출을 기본으로 하는 자료구조이다.
이번 주차의 큐 관련 문제들을 정말 이지하다.
카드 2와 요세푸스 문제는 큐 맨 앞의 원소를 뒤로 추가하면서 풀면 된다.
뱀은 사실 큐를 쓰긴 했지만... 구현 문제 쪽이라고 하는게 더 좋겠다.
사실 큐는 문제를 푸는 것 보다는 이 자료구조가 내부적으로 어떻게 구현되었는가를 공부하는 편이 더 유익하다. 큐는 그냥 배열을 사용해서 front, rear 포인터를 가지고 선입선출을 구현해낼수도 있지만, 이러면 큐에 데이터가 들어오고 나가면서 앞의 빈 공간이 점점 늘어나게 되고, 이는 낭비가 된다.
이를 해결하기 위해 링 버퍼를 사용하는데, front와 rear 포인터의 인덱스를 나머지 연산을 통해 배열의 사이즈 이상으로 커지지 않도록 하는 것이다.
하지만 배열의 사이즈를 넘어서 데이터가 추가되면 어떻게 할까? C 같은 경우는 직접 현재 배열의 사이즈 이상으로 동적 할당을 한 뒤 원래 배열의 원소들을 새 배열로 복사하는 코드를 작성해야 한다.
요새 사용되는 언어들의 리스트들은 이 연산을 자동으로 해준다.
우리가 링 버퍼로 직접 큐를 구현할 때 사이즈를 늘리고 새 배열로 원소들을 복사해주고, front와 rear 포인터의 인덱스를 나눠주는 사이즈만 바꿔주면 될 것 같지만... 그렇게 간단하지가 않다.
만약 링 버퍼에서 rear가 front 보다 앞의 인덱스를 가리키는 상황에서 사이즈를 늘려서 배열을 복사해버리면??
순서가 팍 꼬여버린다.
따라서 front에서 rear를 순회하면서 순서대로 배열을 복사해줘야 한다.
이런 문제도 고려해보는 상황이 자료구조를 배우는 이유인것 같다.
우선순위 큐
우선순위 큐는 미리 설정해둔 순위로 원소들을 입력받는 즉시 정렬해주는 자료구조이다.
보통 이진 힙으로 구현되어있고 이는 곧 배열로 구현할수 있다는 의미이다.
물론 우선순위 큐를 그냥 순회해버리면 순서대로 나오지는 않는다.
이진 힙을 배열로 구현했을 때 왼쪽 자식 노드는 (부모 인덱스) * 2, 오른쪽 자식 노드는 (부모 인덱스)*2 + 1 인데, 형제끼리의 순서는 보장되지 않기 때문이다
파이썬에서는 heapq 라이브러리로 구현되어있고, 최소 힙이 기본으로 사용된다.
자바를 사용할 땐 우선순위 큐 자체에 Comparator를 주거나 compareTo를 구현해주면 순서가 알아서 보장되어서 참 편했는데, 파이썬은 그렇게는 안되고 배열에 key를 주고 배열 자체를 heapq로 줘야 하더라
파이썬의 heapq는 기본적으로 최소 힙이다. 따라서 원소를 넣을 때 음수값으로 넣고, pop 할 때도 음수값으로 빼는 식으로 최대 힙을 구현 가능하다.
median heap은 최소 힙과 최대 힙을 유지하면서 둘의 root 값을 비교해 교환해주면 최대 힙의 root 값이나 두 힙의 중간값이 전체 힙의 중간값이 된다.
카드 정렬하기는 처음에 묶음을 만들고 그냥 힙에 추가시켜가면서 다시 묶음을 만들어주면 끝나는 문제이다. 마치 허프만 트리를 보는 듯 하다.
Linked List
연결리스트는 배열과 달리 메모리에서 연속적으로 붙어있다는 것이 보장되지 않고, 이에 따라 값을 조회할 때 연결리스트 전체를 순회해야하므로 배열에 비해 조회할때의 속도가 느리다.
하지만 중간에 값을 추가하거나 삭제할 때는 그냥 포인터만 바꿔주면 되므로 O(1)의 시간이 걸린다. 이에 비해 배열은 중간에 값을 추가하거나 삭제할 경우 뒤의 인덱스를 밀거나 당겨줘야 하므로 O(N)의 시간이 걸릴수 있다.
Hash Table
내가 찾는 값을 항상 O(1)에 근접하게 찾을 수 있는 정말 획기적인 방식이다.
모듈러 연산을 이용하는데, 값을 특정 해시 함수로 나누어서 나온 나머지 값(해시값)을 인덱스로 하여 저장한다. 이러면 그 값을 다시 찾을 때 이전에 사용한 해시 함수로 얻은 해시값으로 가면 그 값이 있을 것이다.
하지만 저장해야되는 값들 중에 같은 해시값을 가질 수도 있다. 이럴 땐 2가지 방법을 이용해 해결한다
Separate Chaining
값을 저장할 공간을 버킷이라 하는데, 만약 내가 저장될 버킷에 이미 값이 있다면 그 버킷에 연결 리스트로 새 공간을 만들고 연결해서 연속적으로 값을 추가한다. 이 상황에서 값을 조회하면 해당 버킷의 끝을 찾거나, 원하는 값을 찾을 때까지 해당 버킷을 순회하면 된다.
Linear Probing
값을 저장할 공간에 다른 값이 있으면? 비어있는 공간을 찾을 때 까지 인덱스를 증가시켜서 저장하는 방식이다.
조회할 때도 빈 공간을 만나거나 원하는 값을 찾을 때 까지 인덱스를 증가시키면서 찾으면 된다.
다만 이 방식은 중간에 값이 삭제되어버리면 문제가 생긴다
내가 찾아야 할 값A는 원래 0 번 인덱스에 있어야 하지만, 밀려나서 5번 인덱스에 있을 때, 3번 인덱스의 값이 A가 저장된 이후에 삭제되었다면? 이 때 조회를 위해 인덱스를 순회하면 3번 인덱스가 삭제되어서 A가 저장되어있지 않다고 인식할 것이다.
이를 방지하기 위해 삭제할 때 묘비를 세운다. 이 인덱스에는 값이 원래 없던 것이 아니라 무언가 있다가 삭제되었으므로 조회할 때 여기를 넘어가서 순회하라는 의미이다.
이외에도 클러스터가 생기는 문제가 있다. 클러스터는 값이 뭉쳐서 나타나는 현상인데, 예를 들어 해시 함수 T는 값을 10으로 나눈 나머지를 인덱스로 사용한다고 하자. 0은 인덱스 0에 저장되고. 10 또한 인덱스 0에 저장되야 하지만 이미 저장되어 있으므로 인덱스 1에 저장된다. 이 후 값들이 1,2,3이 저장되면 이들은 각각 인덱스 2,3,4에 저장될 것이다. 이후에 만약
11,21,31,41 이 들어오면? 인덱스 1에 저장되어야 하지만 11은 4번 밀려나고, 21은 5번 밀려나고, 31은 6번 밀려나고... 이런 식으로 점점 자신의 자리를 찾는 연산이 많아진다.
이 연산은 클러스터가 커지면 커질수록 점점 더 커지는 암세포같은 문제다.
이를 해결하기 위해 두 개의 해시 함수를 사용하는 Double Hashing, 충돌 시 다음 인덱스를 찾는 값을 1이 아니라 제곱으로 넓히는 Quadratic Probing 등이 있다.
가상 메모리
코어타임에 나는 가상 메모리를 중점적으로 공부하고 설명했다.
https://verdant-bathtub-bae.notion.site/1bd7bb7778c980c9b272ddca6167bb93?pvs=4
가상 메모리 | Notion
메인 메모리와 가상 메모리
verdant-bathtub-bae.notion.site
이 부분은 노션에 정리해놨다.
퀴즈와 시험
퀴즈는 뭐... 어렵지 않았다. 무슨 문제가 나올지 다 알려줬었고 한번씩 연습만 해보면 다 풀수 있는 문제였다.
물론 나중에 들어올 기수를 위해 비밀
시험은 실버 두문제, 골드 한문제가 나왔는데, 이번 주차 백준 문제들이 비정상적으로 어려웠던 것이 맞다 ㅡㅡ
골드 문제가 그렇게 어려운 편은 아니었으니 평소에 실버 1 ~ 골드 5 문제들을 풀 수 있었으면 다 통과할수 있을 것이다.