구프의 메모장

세그먼트 트리에 대해서 이전에 부분합을 구하는 것으로만 사용하는 것으로 작성한 적이 있다. 그러나 최근 BOJ에서 1168번 문제와 12899번 문제를 풀면서 다른 활용법을 알게 되었는데 이에 대한 내용이다. 세그먼트 트리의 특성은 간단하게 부모 노드가 모든 자식노드의 합이 된다는 것이다. 위에서 작성한 1168번 문제와 12899번 문제는 이 특성을 이용해 순서를 찾는데 이용하는 문제이다. 자, 다음과 같은 height 3에 모든 자식 노드가 1의 값을 가지는 세그먼트 트리가 있다. root node의 값을 통해 우리는 전체 자식노드 중 값을 가지는 노드가 총 4개임을 알 수 있다. 그리고 각 자식노드는 왼쪽부터 1, 2, 3, 4로, 오름차순으로 d=1의 등차수열에 매칭된다. tree[4] -> 1,..

이진 탐색은 PS에서 정말 자주 쓰이는 알고리즘이다. 근데 알고는 있는데, 뭔가 자꾸 왼쪽.. 오른쪽.. 최대.. 최소.. 하면서 헷갈리게 된다. 글을 쓰고 나면 좀 이 헷갈림이 사라질까.. 이진 탐색은 정렬된 데이터에서 특정한 값을 O(log N)시간에 찾기 위한 알고리즘이다. 데이터가 정렬되어져있기 때문에, 배열의 중간값과 찾으려는 값의 크기를 비교하면서 탐색하게 된다. 데이터가 오름차순으로 정렬됬다고 생각해보자. ( 1, 2, .... N ) 그렇다면 다음의 두 명제는 자명할 것이다. - 만약, 찾으려는 값이 중간값보다 크다면, 찾으려는 값은 중간값보다 오른쪽에 있을 것이다. - 만약, 찾으려는 값이 중간값보다 작다면, 찾으려는 값은 중간값보다 왼쪽에 있을 것이다. 이 명제를 활용해 값을 찾는 방식..

트리문제는 풀어도 풀어도 헷갈리고 어렵다... 상성이 잘 안맞는 것 같고.. 어떻게 풀고 보면 다른 사람들보다 코드 길이가 좀 많이 길고... 더 많이 풀면 해결 되겠지... 트리는 일종의 그래프이다. 근데 이제 사이클이 존재하지 않는. 예를 들어, 이것은 트리이다. 사이클이 없기 때문이다. 그러나 선을 하나 더 추가해서 이렇게 순환하게 만들어 버리면 트리가 아니다. 트리는 '루트, 부모, 자식' 이렇게 3가지의 개념만 알면 사실 기본은 끝이다. 추가로 단말노드(Terminal node or Leaf node)와 비-단말노드(Non-terminal node)라는 개념도 있는데, 이 개념들에 대해 이해하려면 간단하게 족보를 생각해보자. 가문의 족보라는것은 조상부터 대대로 내려온다. 뭐 1대손.. 2대손....

이건 알고리즘이라기 보다는 자료구조지만, 일단 기본이니까 짚고 넘어가보자. 오늘 있었던 2022 Sogang Programming Open Contest에서 쉬워보였던 스택/큐 문제를 못풀어서 그런것도 있고.. 일단 고 큐와 스택에 대해 가장 단순하게 설명하는 방법은 FIFO와 LIFO다. FIFO : First In First Out LIFO : Last In First Out 큐는 FIFO 형식으로 넣은 순서대로 출력하는 구조로 모두가 같은 속도로 달리는 터널이라고 생각하면 쉽다. 모두가 같은 속도로 달리고 있기 때문에, 먼저 들어간 차가 나중에 들어간 차보다 먼저 터널을 탈출할 것은 자명하다. 스택은 LIFO 형식으로 가장 늦게 넣은것이 먼저 출력된다. 스택은 하노이의 탑을 생각하면 편하다. 가장 ..

PS를 하면서 느낀점이 지금까지 코딩 해온 경험으로 어떻게든 억지로 문제를 풀고 있다는 느낌이 들어서 기초 알고리즘을배우면서 다시 기초를 다져보자는 생각이 들었다. 트리나 힙, 최소경로 이런 것도 대충 손으로 쓰라고 하면 쓰겠는데 코드로 짜라하면 뭔가 애매한 느낌이고, 좌표압축같은 문제도 제대로 못푸는걸 보니까 확실히 기초가 딸린다는 생각이 들더라.. 재귀란 '자기 자신을 참조하는 행위'이다. 재귀 함수의 예로 피보나치 수를 구하는 방법도 있고, ( cache를 만들어주지 않으면 시간복잡도 멸망 ) ※ 피보나치 수를 구하는 문제 : https://www.acmicpc.net/problem/2747 public long getFibonacci(int index) { if(index 5 * getFactor..