https://admin.teferi.net/ 2026-05-05T12:05:03+00:00 https://admin.teferi.net/ https://admin.teferi.net/_media/wiki/dokuwiki.svg text/html 2022-11-16T14:44:46+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/2-sat?rev=1668609886&do=diff 2-SAT * 2-satisfiability * Boolean satisfiability problem 중에서, 식이 2-CNF 형태로 주어지는 경우를 2-satisfiablity, 줄여서 2-SAT라고 부른다. * k-SAT들 중에서 2-SAT만 따로 빼서 특별하게 설명하는 이유는, 2-SAT 까지만 쉽게 풀리기 때문이다. text/html 2023-04-04T15:05:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/2%EC%83%89_%EC%83%89%EC%B9%A0?rev=1680620723&do=diff 2색 색칠 * 인접한 두 노드는 다른 색을 갖도록 하면서, 전체 노드들을 2가지 색으로 색칠하기. * 일반적인 vertex k-coloring 은 NP라서 PS에서는 다룰일이 별로 없다. 기본정리 * 2색 색칠이 가능하다 text/html 2025-03-03T14:55:05+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B0%80%EC%9E%A5_%EA%B8%B4_%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4?rev=1741013705&do=diff 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS) * 참고: <https://cp-algorithms.com/sequences/longest_increasing_subsequence.html> * 먼저 종종 헷갈리는 용어를 정리하면, 부분수열(Subsequence)은 '주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열' 이다. $ T[k]=min_{dp[j]=k}{A[j]} $$ max_{T[k]<A[i]}{k} + 1 $ text/html 2021-11-11T16:02:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B0%80%EC%9E%A5_%EA%B8%B4_%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC_%EB%B6%80%EB%B6%84%EB%AC%B8%EC%9E%90%EC%97%B4?rev=1636646530&do=diff 가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring) * Longest palindromic substring 을 참고. * 사실 이 문서에서의 메인 주제는 '가장 긴 팰린드롬 부분문자열' 이라는 태스크가 아니라, Manacher's algorithm에 관한 전반적인 내용이다. text/html 2023-02-13T08:15:39+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1%EC%9D%98_%EB%B9%A0%EB%A5%B8_%EA%B3%84%EC%82%B0?rev=1676276139&do=diff 거듭제곱의 빠른 계산 (Exponentiation by squaring) * 어떤 수의 n제곱을 분할 정복을 이용해서 O(logn)에 계산하는 방법. * 위키피디아에 따르면 Exponentiation by squaring 라는 이름 말고도 square-and-multiply 알고리즘이나 binary exponentiation 등으로도 불린다고 한다. text/html 2026-02-24T13:54:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B2%8C%EC%9E%84_%EC%9D%B4%EB%A1%A0?rev=1771941289&do=diff 게임 이론 (Game theory) * 작성중 용어 정리 설명하기 쉽게 하기 위해서, 용어를 통일해서 쓰도록 하겠다. (통일하려고 노력해볼 것이긴 한데 잘 될지는 모르겠다..) * 포지션: 현재 게임의 상태. 게임에서는 스테이트 대신에 포지션이 더 일반적인 것 같다.$(n_{k}, m_{k})$$ \phi$$ n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\ $$ m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\ $ text/html 2025-10-30T08:47:16+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B2%BD%EB%A1%9C_%EC%BF%BC%EB%A6%AC?rev=1761814036&do=diff 경로 쿼리 * 트리에서 u와 v를 잇는 경로상의 엣지들 (또는 노드들) 에 대한 뭔가를 물어보는 쿼리이다. * 가장 간단한 것은 경로의 길이를 묻는 문제이다. 경로상의 엣지들에 대해서 sum 쿼리를 요구하는 것과 똑같다. text/html 2023-08-01T07:44:11+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B3%84%EC%B0%A8%EC%88%98%EC%97%B4_%ED%8A%B8%EB%A6%AD?rev=1690875851&do=diff text/html 2023-08-04T15:09:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98?rev=1691161767&do=diff 고속 푸리에 변환 (Fast Fourier Transform, FFT) 개념 * 푸리에 변환은 신호처리등의 용도로 각종 공학분야에서 너무도 많이 쓰이는 것이지만, PS와 관련돼서는 합성곱의 빠른 계산 그리고 다항식의 빠른 곱셈에 사용된다. text/html 2023-03-20T04:06:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B3%B1%EC%85%88%EC%A0%81_%ED%95%A8%EC%88%98?rev=1679285169&do=diff 곱셈적 함수 (Multiplicative Function) * gcd(m,n)==1 일때, f(mn) = f(m)f(n) 이 성립하는 함수들 예 * φ(n): 오일러 피 함수. n보다 작고 n과 서로소인 자연수의 갯수 * 오일러 파이로 읽는 경우랑 오일러 피로 읽는 경우가 혼재한다.. text/html 2021-03-29T10:40:21+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B5%AC%EA%B0%84_%EB%B6%84%ED%95%A0_%EB%B0%A9%EC%8B%9D%EC%97%90_%EA%B4%80%ED%95%9C_dp?rev=1617014421&do=diff 구간 분할 방식에 관한 DP * 이런 문제를 따로 일컫는 명칭이 없는것 같아서, 이름을 적당히 붙여보려 했으나 쉽지 않다.. * 어떤 구간에 대한 값이 그 안에 포함된 더 짧은 구간에 대한 값들로 계산되는 형태이다. text/html 2023-08-01T07:43:57+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B5%AC%EA%B0%84_%EC%BF%BC%EB%A6%AC?rev=1690875837&do=diff 구간 쿼리 * 어떤 1차원 배열 l이 있을 때, a번째부터 b번째까지의 원소들의 대표값, f(l[i:i+n]) 을 효율적으로 계산하는 방법에 대한 내용. * 기본적인 요령은, 대표적인 몇몇 구간에 대해서 미리 값을 구해 놓은 뒤, 인풋으로 들어온 구간에 대한 처리는 미리 계산된 구간들의 값을 조합해서 계산하는 것이다. text/html 2023-04-04T15:30:56+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B7%B8%EB%9E%98%ED%94%84?rev=1680622256&do=diff 그래프 용어 정의 * Walk: 노드나 엣지의 중복을 허용하는 경로 * Open walk: 시작점과 끝점이 다른 walk * Closed walk: 시작점과 끝점이 같은 walk * Trail: 엣지의 중복이 없는 walk * Circuit(=tour): 엣지의 중복이 없고, 시작점과 끝점이 같은 walk (=closed trail) text/html 2026-03-19T09:23:28+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EA%B7%B8%EB%A6%AC%EB%94%94?rev=1773912208&do=diff 그리디 알고리즘 * 이게 참.. 그리디는 딱히 정형화를 해서 공부할 수 있는 부분이 아닌거 같은데.. 그래서 딱히 뭘 적어야 할지도 모르겠고 해서 항목 자체를 안만들고 있었다. * 그러나, 차라리 풀었던 그리디 문제들을 모아놓고, 비슷한 유형끼리 모아보는 식으로 접근해본다면 그래도 도움이 되지 않을까 하는 생각이 들었다. text/html 2026-01-11T03:32:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%84%A4%EC%9D%B4%EB%B0%8D_%EA%B0%80%EC%9D%B4%EB%93%9C?rev=1768102332&do=diff 네이밍 가이드 앞글자를 따서 약자로 쓰는 단어들 * coordinate => coord * distance => dist * direction => dir_ * dir은 builtin 함수라서 뒤에 _를 붙인다. direc도 고민했으나 탈락 * current => cur * previous text/html 2023-09-26T06:52:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%ED%94%8C%EB%A1%9C%EC%9A%B0?rev=1695711169&do=diff 네트워크 플로우 (Network Flow) ??? text/html 2024-02-29T02:26:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D?rev=1709173614&do=diff 동적 계획법 (Dynamic Programming) * 기본 개념은 wikipedia 참고 * 정확히는 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다. text/html 2024-02-23T01:31:04+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1708651864&do=diff 데이크스트라 알고리즘 (Dijkstra's algorithm) * 최신 트렌드(?)는 다익스트라가 아닌 데이크스트라 라고 읽는 것 같다만.. 참 적응이 안된다.. (호이겐스가 하위헌스로 바뀔때 느꼈던 당혹감?).. 원래는 그래서 좀더 입에 붙을때까지는 그냥 다익스트라로 쓰겠다고 했었는데. 그래도 이제는 의식적으로라도 표준 발음으로 바꿔 읽으려고 노력은 해야할 것 같다. text/html 2022-11-25T17:19:19+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%8B%A8%EC%9D%BC_%EC%B6%9C%EB%B0%9C%EC%A7%80_%EC%B5%9C%EB%8B%A8_%EA%B2%BD%EB%A1%9C?rev=1669396759&do=diff 단일 출발지 최단 경로 (Single Source Shortest Path) * 위키피디아 참고 * 그래프의 종류에 따라서 어떤 알고리즘을 써야하는지는 아래 순서대로 결정하면 된다 * 트리이면 => 최단 경로 이전에, 그냥 경로가 하나밖에 없다. BFS든 DFS든 아무거나 쓰면 된다 O(V+E) text/html 2026-05-05T07:07:03+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%8C%80%ED%9A%8C?rev=1777964823&do=diff 대회 공식 해설 모음 * 공식 해설은 <https://editorial.coduck.io/> 에서 찾아보자 * 원래 이 페이지는 BOJ에 올라온 대회의 공식 에디토리얼을 찾아볼때마다 링크들을 기록해두어서, 다음에 찾을 때에 수고를 줄이려는 목적으로 만들어졌다 text/html 2024-05-13T14:32:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%8D%B1?rev=1715610755&do=diff 덱 (Deque) * Double-Ended QUEue의 약자 * 덱이 맞는 발음이다. 디큐아님 Monotone deque * 참고: <https://stonejjun.tistory.com/126> * 덱 안의 원소들을 단조증가하는 순서대로 유지함으로써 문제를 푸는 테크닉. * 새 원소를 덱 뒤에 추가시킬때, 덱 맨 뒤의 원소가 추가할 원소보다 작은 값이 될때까지 마지막 원소를 삭제한 뒤에, 새 원소를 추가한다. 사실 여기까지는 $ dp[i] = f(min_{i-K<j<i}(dp[j])) $$ dp[i] = f(i, min_{i-K<j<i}(dp[j])) $… text/html 2025-05-08T14:43:40+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%8F%99%EC%A0%81_%EC%97%B0%EA%B2%B0%EC%84%B1?rev=1746715420&do=diff 동적 연결성 * 개념은 Dynamic Connectivity를 참고하자. * 몇가지 케이스로 분류할 수 있고, 문제의 난이도도 이에 따라 달라진다 * 쿼리 종류에 따라서 '엣지를 추가하는 쿼리만 들어올 때' / '엣지를 삭제하는 쿼리만 들어올 때' / '두 종류의 쿼리가 모두 들어올 때' 로 분류 text/html 2020-12-25T16:32:34+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%9D%BC%EB%B9%88-%EC%B9%B4%ED%94%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1608913954&do=diff 라빈-카프 알고리즘 (Rabin-Karp Algorithm) * <https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm> 참고 * 이 알고리즘 자체는 문자열 매칭 문제를 위한 알고리즘인데, 사실 문자열 매칭 문제 자체는 그냥 KMP를 쓰는 것이 낫다. * 다만, 여기의 해싱 기법은 다른 응용 문제에서도 종종 유용하게 활용된다. text/html 2023-02-09T08:27:55+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%AA%A8%EB%93%88%EB%9F%AC_%EC%97%B0%EC%82%B0?rev=1675931275&do=diff 모듈러 연산 (Modular arithmetic) * 덧셈, 뺄셈, 곱셈은 간단하다. 그냥 연산 한번 할때마다 모듈러를 취하면 된다 * (X + Y) % M = ( (X % M) + (Y % M) ) % M * (X - Y) % M = ( (X % M) - (Y % M) + M) % M (X>Y 일때)$ \text{inv}[i] = - \left\lfloor \frac{m}{i} \right\rfloor \cdot \text{inv}[m \bmod i] \bmod m $ text/html 2024-05-13T12:14:11+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%AB%BC%EB%B9%84%EC%9A%B0%EC%8A%A4_%ED%95%A8%EC%88%98?rev=1715602451&do=diff 뫼비우스 함수 (Mobius function) * <https://rkm0959.tistory.com/186> 1부터 n까지의 뫼비우스 함수값을 모두 구하기 * 에라토스테네스의 체를 이용해서 구현 가능 * 리니어 시브를 이용해서 구현 가능 * => 이쪽이 더 빠르다. 소수 목록을 구할때 에라토스테네스의 체가 더 빠른 이유는 파이썬에서 slice assignment 가 빠르기 때문인데. 뫼비우스 함수값을 구할때는 어차피 slice assignment가 불가능하기때문에, 그냥 리니어시브를 쓰는게 더 빠르다.… text/html 2025-04-03T14:05:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%AC%B8%EC%9E%90%EC%97%B4_%EB%A7%A4%EC%B9%AD?rev=1743689123&do=diff 문자열 매칭 * 주어진 문자열 S 안에 어떤 패턴문자열 P가 존재하는지, 몇개나 존재하는지, S의 몇번째 인덱스에 있는지 등등을 처리하는 매우 실용적인 문제 * 문자열 매칭을 위한 알고리즘들은 여러가지가 있다. len(S) = N, len(P) = M이라고 하자 text/html 2023-05-27T14:47:44+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%AC%B8%EC%9E%90%EC%97%B4?rev=1685198864&do=diff 문자열 * 문자열 관련해서 PS레벨에서 알아야 할 알고리즘들은 어느정도 정해져있는 편이고, 그다지 많지 않다. * 어려운 점은 어떤 문제에 어떤 알고리즘을 어떻게 적용해야 할지이다. * text/html 2025-04-08T07:52:13+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C?rev=1744098733&do=diff 배낭 문제 (Knapsack problem) * 작성중 * 기본적인 내용에 관한 글은 너무 많고, 고급 기법에 관해서는 아래 두 링크를 참고 * <https://infossm.github.io/blog/2023/03/18/Knapsack/> * <https://codeforces.com/blog/entry/98663> * '이 문제는 냅색으로 푸면 된다', '냅색DP를 쓰면 된다' 이런 표현들을 흔히 쓰긴 하는데, 원래 배낭(=냅색) 문제는 알고리즘 이름이 아니라 문제 이름이다. 표현을 정확히 하자면 '냅색 문제를 풀듯이 풀면 된다' 이런 식이 될텐데.. 그냥 문제 이름에서 알고리즘 이름이 붙은 '불도저 트릭' 이나, '금광 세그' 등을 생각하면 뭐 냅색DP라는 표현 자체가 그렇게 말이 안될것도 없지 않나 싶기도 하다… text/html 2023-08-01T07:23:29+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EB%B3%91%EB%A0%AC_%EC%9D%B4%EB%B6%84_%ED%83%90%EC%83%89?rev=1690874609&do=diff 병렬 이분 탐색 (Parallel Binary Search; PBS) * 일단 참고자료는 * <https://m.blog.naver.com/kks227/221410398513> * 이하는 PBS의 동작방법 자체보다는.. 다른 테크닉들과 어떤식으로 다른지 내가 공부하면서 느낀 방식대로 정리한것. * 우선 이름에 이분탐색이 들어가긴 하지만, 이분탐색의 변형..이라는 느낌보다는 오프라인 쿼리 테크닉의 일종으로 생각하자 text/html 2023-12-19T16:02:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%82%BC%EC%86%8C%EB%A9%A4?rev=1703001765&do=diff 삼성 S/W 멤버쉽 기술 블로그 * 굉장히 양질의 글들이 많은 사이트인데 문제는 사이트에서 검색이 안된다. 깊이가 있는 글들이 많아서 한번에 다 소화하지 못하고, 다시 찾아봐야 할 경우가 많은데, 검색이 안되다 보니까 한참 걸려서 찾게 되는 일이 많다. text/html 2022-12-08T12:12:51+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%84%A0%EB%B6%84_%EA%B5%90%EC%B0%A8?rev=1670501571&do=diff 선분 교차 * 선분의 교차 여부는 세 점의 방향성을 이용해서, 실수 연산 없이 구하는 것이 가능하다. 세 점의 위치 관계 * 세 점 p1, p2, p3의 위치 관계는 벡터의 외적을 이용해서 구할수 있다. text/html 2021-01-03T14:31:02+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%84%A0%ED%83%9D_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1609684262&do=diff 선택 알고리즘 * 기본적인 내용은 <https://en.wikipedia.org/wiki/Selection_algorithm> 을 참조 * 이론적으로는 * QuickSelect 를 쓰면 k번째 원소를 평균 O(n)에 구할 수 있다. * Median of median 을 쓰면 k번째 원소를 최악 O(n)에 구할 수 있다. * text/html 2023-08-28T08:40:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%84%A0%ED%98%95_%EC%A0%90%ED%99%94%EC%8B%9D?rev=1693212020&do=diff 선형 점화식 * 점화식의 종류는 무궁무진하지만 제일 기본으로 다루는 것은 선형점화식으로, a[n] = c[1]*a[n-1] + c[2]*a[n-2] + ... + c[k]*a[n-k] + f(n) 형태로 표현되는 점화식이다. 이때 c[i]는 모두 상수이고, f는 산술적 함수이다. $ a_n = \frac{1}{\sqrt5} \Bigg(\bigg( \frac{1+\sqrt5}{2} \bigg)^n -\bigg( \frac{1-\sqrt5}{2} \bigg)^n \Bigg) $$ \begin{bmatrix}dp[n] \\ dp[n-1] \end{bmatrix}=\begin{bmatrix}a & b \\1 & 0 \end{bmatrix}\begin{bmatrix}dp[n-1] \\ dp[n-2] \end{bmatrix} $$ \begin{bmatrix}dp[n] \\ dp[n-1] \end{bmatrix}=\begin{bmatrix}a & b \\1 & 0 \end{bmatrix}… text/html 2023-08-30T13:29:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8_%ED%8A%B8%EB%A6%AC?rev=1693402173&do=diff 세그먼트 트리 * 작성중 * 사실 세그먼트 트리에 관한 내용은 이미 구간 쿼리에 열심히 적어놓았다. 하지만, 그 문서가 너무 길어지다보니 좀 분리할 필요성이 느껴졌다. 세그먼트 트리의 활용부분에 대해서만 그 문서에 남겨놓고, 기본 세그먼트 트리의 원리나 구현 등은 이쪽 문서로 옮길 text/html 2022-10-12T06:07:46+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%84%BC%ED%8A%B8%EB%A1%9C%EC%9D%B4%EB%93%9C_%EB%B6%84%ED%95%A0?rev=1665554866&do=diff 센트로이드 분할 (Centroid Decomposition) * 참고: <https://justicehui.github.io/hard-algorithm/2020/08/25/centroid/> 센트로이드 * 센트로이드는 정점 하나를 지웠을때 쪼개지는 서브트리의 크기가 모두 전체 트리의 절반 이하가 되게하는 노드를 말한다. * text/html 2023-08-09T06:51:15+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%86%8C%EC%88%98_%EB%AA%A9%EB%A1%9D_%EA%B5%AC%ED%95%98%EA%B8%B0?rev=1691563875&do=diff 소수 목록 구하기 * 기본적으로 에라토스테네스의 체를 사용한다. * 시간복잡도상으로는 O(n)의 Linear sieve가 O(nloglogn)의 에라토스테네스의 체보다 더 빠르지만, 실제 구현은 에라토스테네스의 체가 더 빨리 돈다. text/html 2023-03-31T08:13:46+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%86%8C%EC%88%98_%ED%8C%90%EB%B3%84?rev=1680250426&do=diff 소수 판별 (Primality Test) 특정 수가 소수인지 판별 * 참고: <https://cp-algorithms.com/algebra/primality_tests.html> <https://aruz.tistory.com/entry/primality-test-1> * 여러가지 방법이 있긴 하지만, 작은수에는 Trial division, 큰 수에는 밀러-라빈 알고리즘을 사용하면 된다 * 페르마 소수판별법 등은 몰라도 된다 text/html 2025-04-20T13:39:34+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%86%8C%EC%88%98?rev=1745156374&do=diff 소수 (Prime number) 관련된 성질들 * 유클리드의 정리 (Euclid's theorem) * 소수의 갯수는 무한히 많다 * 소수정리 (Prime number theorem) * n이하의 소수의 개수는 대략 n/ln(n)개이다. 바꿔쓰면, n번째 소수의 값은 대략 n*ln(n)이다 text/html 2024-01-11T01:17:52+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%86%8C%EC%88%98%EC%9D%98_%EA%B0%9C%EC%88%98_%EA%B5%AC%ED%95%98%EA%B8%B0?rev=1704935872&do=diff 소수의 개수 구하기 * x이하의 소수의 개수를 π(x)라고 표현하고, 이것을 Prime-counting function이라고 부른다 * π(x)이 x/ln(x)로 근사된다는 것은 잘 알려진 내용이다. 바로 그 유명하고도 중요한 소수 정리이다. * 하지만 근사값이 아니라 특정 n에 대해서 정확한 π(n)의 값을 계산해야 할 필요가 있다. 여기에서는 정확한 값을 구하는 알고리즘들을 정리한다.$f$$ \sum_{i \leq x} f(i) $$ \sum_{p \leq x, p is prime} f(p) $$ S_f(v, 1) = f(2) + f(3) + \ldots + f(v) $$ S_f(v, p) = S_f(v, p-1) - f(p)\left[S_f(v/p, p-1) - S_f(p-1, p-1)\right] $… text/html 2026-03-29T07:08:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4?rev=1774768128&do=diff 소인수분해 (Prime Factorization) * Integer Factorization 이라고도 불린다 (이게 더 흔히 쓰이는 표현같기도..) n을 소인수분해하기 * 참고 - <https://cp-algorithms.com/algebra/factorization.html> <https://aruz.tistory.com/entry/factorization-1> * 소인수분해는 암호학이나 여러 분야에서 매우 중요하게 사용되는 알고리즘이고, 그러다보니 다양한 알고리즘이 있는데.. PS 범위에서는 trial division과 Pollard's rho 두가지만 알면 충분하다… text/html 2023-08-20T15:49:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%8A%A4%ED%83%80%EC%9D%BC_%EA%B0%80%EC%9D%B4%EB%93%9C?rev=1692546566&do=diff 코드 작성 가이드 기본 가이드 * 기본적으로는 Google Python Style Guide와 PEP 8 -- Style Guide for Python Code를 따른다 * 두 규칙이 충돌나는 부분이 있다면 Google Python Style Guide를 따른다. * 포매팅은 Black을 사용하고 pylint로 체크한다. * Python Formatter 참고 text/html 2024-01-27T09:40:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%8A%A4%ED%83%9D?rev=1706348454&do=diff 스택 (Stack) * 몇가지 대표적인 활용은, 괄호쌍 매칭, infix order를 변환하기, Monotone stack 등이다. Monotone Stack * Monotonic stack 이라고 불리기도 한다. * 스택 안에 원소들을 정렬된 순서로 유지하면서 문제를 해결하는 테크닉이다. 구체적인 설명은 text/html 2024-03-27T14:56:21+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%8A%A4%ED%94%84%EB%9D%BC%EA%B7%B8-%EA%B7%B8%EB%9F%B0%EB%94%94_%EC%A0%95%EB%A6%AC?rev=1711551381&do=diff 스프라그-그런디 정리 * 작성 예정 Octal game * Octal game 참고 * 세줄요약 먼저 하자 * Octal game은 Take-and-break 게임을 부르는 말로, 그런디수가 주기적으로 반복될 가능성이 높다. 주기를 찾으면 그런디 수를 O(n^2)이 아닌 O(n)에 계산할수 있다. text/html 2024-02-15T03:23:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98?rev=1707967415&do=diff 시뮬레이션 (Simulation) * 알고리즘이라기 보다는, 그냥 시키는 대로 구현해서 돌려보는 가장 원초적인 문제풀이 방법이다. * PS의 문제들을 정말 크게 나눠볼때 * '주어진 답 후보들 중에서, 조건을 만족하는 답을 찾아라' 라는 형태의 문제를 푸는 가장 원초적인 방법은 완전탐색이다. 모든 답후보들에 대해서 조건을 만족하는지 확인하는 것이다. text/html 2024-05-11T14:58:56+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1715439536&do=diff 알고리즘 정리 * 이것저것 공부한 내용 또는 혼자 알아낸 내용들을 나중에 쉽게 다시 찾아볼 수 있도록 간단히 정리해 두는 것이 가장 큰 목표. * 책이나 인터넷에서 쉽게 찾을 수 있는 내용을 굳이 다시 적을 필요는 없다. 그냥 링크만 걸어두자. text/html 2025-04-07T09:28:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%95%A0%EB%93%9C%ED%98%B9?rev=1744018090&do=diff 애드혹 * 애드혹은 알고리즘이나 풀이 기법의 이름이 아니라. 애드혹이라는 태그는, 어떤 정형화된 풀이기법을 적용할수 없는 문제에 붙여지는 태그이다. * 그냥 문제마다 그때그때 필요한 풀이방법을 떠올려서 푼다는 면에서는, 가장 원초적이고 근본적인 풀이 방법이기도 하다 text/html 2024-07-24T08:01:31+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%97%98%EB%A6%AC%EC%8A%A4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%BD%94%EB%93%9C_%EC%B1%8C%EB%A6%B0%EC%A7%80?rev=1721808091&do=diff 엘리스 알고리즘 코드 챌린지 * <https://code-challenge.elice.io/explore> * 2023년에 시즌1 대회가 있었던것 같은데 참여도 안했고 정보도 없다. * 2024년에 열린 시즌2 대회만 정리. 방식 및 상품 * 예선은 10일동안 매일 한문제씩 문제가 나오고, 그날 안에 정답을 제출하면 된다. text/html 2025-03-11T01:19:00+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80_%EC%88%98%ED%95%99_%EC%A0%95%EB%A6%AC?rev=1741655940&do=diff 여러가지 수학 정리 * 따로 카테고리를 만들정도로 중요하거나 웰노운도 아니면서 다른 정리들과 연관되어있지도 않은 정리들을 그냥 모아놓은 페이지.. (그뭔씹?) 거듭제곱수의 합 / 파울하버의 공식 (Faulhaber's Formula) $\sum _{k=1}^{n}k^{p}= 1^p + 2^p + 3^p + \cdots + n^p$$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} $$ {\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {2n^{3}+3n^{2}+n}{6}}} $$ {\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=\left[{\frac {n(n+1)}{2}}\right]^{2}={\frac {n^{4}+2n^{3}+n^{2}}{4}}} $$ {\displaystyle \su… text/html 2022-05-03T02:06:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8?rev=1651543614&do=diff 연결 리스트 (Linked List) * 자료구조 수업에서 배열과 함께 처음 배우는 가장 기본적인 자료구조이다. 설명은 생략. * 다음 노드의 포인터만 갖고 있느냐 이전 노도의 포인터도 갖고 있느냐에 따라서, 단일 링크드 리스트와 양방향 링크드 리스트로 구현할수 있다. 맨 앞 노드와 맨 뒤 노드를 연결해서 서큘러 링크드 리스트를 사용하는 경우도 있다. text/html 2023-11-27T14:31:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%97%B0%EA%B2%B0_%EC%9A%94%EC%86%8C?rev=1701095470&do=diff 연결 요소 (Connected Component) * 탐색으로 찾기? DSU로 찾기? * 테스트용 문제 * 11724: V<1000, E=O(V^2) * DSU(v4.1): 572ms * RemDsu : 636ms * ListDSU: 544ms * bfs(v0.21): 704ms * dfs(v0.22): 736ms text/html 2025-07-03T14:46:06+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%97%B0%EB%A6%BD_%EC%84%A0%ED%98%95_%ED%95%A9%EB%8F%99%EC%8B%9D?rev=1751553966&do=diff 연립 선형 합동식 * 다음의 형태로 주어지는 문제이다 * x % m_1 = a_1, x % m_2 = a_2, ..., x % m_n = a_n 중국인의 나머지 정리 (Chinese Remainder Theorem; CRT) * 중국인의 나머지 정리는 m_i가 모두 서로소일 경우에 이 문제의 해가 법 m_1*m_2*$ x \equiv \sum^{n}_{i=1} M_iN_ia_{i} \pmod M $$ M = m_1m_2m_3 ... m_n, M_i = M/m_i, N_i = M_i^{-1} \bmod{m_i} $ text/html 2023-12-26T08:50:30+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%98%81_%ED%83%80%EB%B8%94%EB%A1%9C?rev=1703580630&do=diff 영 타블로 (Young tableau) * 참고 * <https://codeforces.com/blog/entry/98167> * <https://infossm.github.io/blog/2021/09/19/young-tableaux/> * 한글로 된 고퀄리티의 글이긴 한데, 주요 내용이 다음 포스트에 이어진다고 적혀 있지만 다음 포스트가 작성되지 않았다..ㅜㅜ * <https://horizon.kias.re.kr/6446/> * PS 컨텍스트로 쓰여진 글은 아니지만, 전반적 이해에 많은 도움이 된다 text/html 2021-08-06T14:13:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C?rev=1628259228&do=diff 요세푸스 문제 * Josephus problem과 <https://cp-algorithms.com/others/josephus_problem.html>을 참고하자. * 제외되는 번호를 순서대로 나열한 요세푸스 순열을 구하는 문제와, 마지막으로 제외되는 번호를 구하는 문제가 있다. * 1~n번까지 번호가 있을때, 매 k번째 번호를 제외시킨다$ J_{n,2} = 1+2(n-2^{\lfloor{log_{2}n}\rfloor}) $$ J_{n,k} = (J_{n-1,k}+k){\bmod n},{\text{ with }}J_{1,k}=0 $$ {\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\\left\lfloor {\frac {k((g(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{where… text/html 2024-10-18T04:36:30+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90?rev=1729226190&do=diff 우선순위 큐 (Priority Queue) * 기본적인 내용은 Priority Queue 참고 * insert, find-min, extract-min을 빠르게 처리하는 자료 구조이다. 다양한 구현법이 존재하지만, 대표적인 것은 binary heap이다. 여러 언어의 기본 라이브러리에서 제공하는 것도 바이너리 힙이다. text/html 2021-10-08T17:13:56+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9C%84%EC%83%81_%EC%A0%95%EB%A0%AC?rev=1633713236&do=diff 위상 정렬 (Topological Sorting) * 기본 개념과 설명은 위키피디아에 잘 나와있다 - Topological Sorting * 위상정렬 결과를 구하는 알고리즘은 Kahn's algorithm과 DFS를 이용하는 방법이 있다. 인접리스트로 그래프가 주어질때, 수행시간은 둘 다 O(|V|+|E|)이다. text/html 2024-08-25T05:58:03+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9D%B4%EB%A1%A0?rev=1724565483&do=diff 이론 이론 로 옮길예정 자료구조 / 알고리즘 * 그래프 * 최단 경로 * 전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP) 문제 유형 * 구간 쿼리 문제 text/html 2022-04-22T14:16:03+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9D%B4%EB%B6%84_%EB%A7%A4%EC%B9%AD?rev=1650636963&do=diff 이분 매칭 (Bipartite Matching) * 이분 그래프에서 최대 매칭을 찾는 문제를 이분 매칭이라고 부른다. 이분매칭을 푸는 알고리즘 * 이분 매칭은 최대 유량 문제로 쉽게 변환해서 풀 수 있다. text/html 2024-11-30T15:20:47+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89?rev=1732980047&do=diff 이진 검색 (Binary search) * 이분 탐색이라고 배웠던 것 같은데, 한국어 위키에는 이진 검색으로 되어있다. * 뭐가 제일 대중적인 번역인지 구글에서 검색해서 나온 문서수를 비교하면 이진 text/html 2025-05-12T13:03:02+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC?rev=1747054982&do=diff 이진 탐색 트리 (Binary search tree) * [작성중] * 이진 탐색 트리에 대한 부분은 생략. 나중에 시간될때 채워넣기로 하자. * 우리가 진짜 관심이 필요한 것은 Self-balancing binary search tree 이다. bbst라고 부르겠다. text/html 2026-03-23T12:49:11+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98?rev=1774270151&do=diff 이항 계수 (Binomial Coefficient) * 정의와 설명은 ko:이항 계수 참고. * $ {\binom {n}{k}}$, ${{n}C_{k}}$, ${C(n,k)}$ 등으로 표기하고, 계산 공식은 0≤k≤n 일 때, $n!/\left(k!(n-k)!\right)$ 이다. * 잘 쓰이는 일이 없지만, k>n 일때에는 C(n,k)=0 이다. * k<0일 때는 설명이 다르다$ \sum _{k=0}^{n}{\binom {n}{k}}=2^{n} $$ \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1} $$ \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n}{k-j}}={\binom {m+n}{k}} $$ \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}} $$ \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}} $$\nu_{p}({\bin… text/html 2026-03-31T14:25:03+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%9D%B8%EB%AA%85%EC%82%AC%EC%A0%84?rev=1774967103&do=diff 인명 사전 * 원래는 인명이 들어간 알고리즘/정리/추측 등이 있을 때에 한글로 인명표기를 일정하게 쓰기 위해서 정리했다만.. 하는 김에 조금 더 추가정보를 적었다. 직업은 수학자/전산학자로만 구분했다. text/html 2024-03-13T13:52:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%A0%84%EC%B2%B4%EC%8C%8D_%EC%B5%9C%EB%8B%A8_%EA%B2%BD%EB%A1%9C?rev=1710337953&do=diff 전체쌍 최단 경로 (All-pairs shortest path) * 위키피디아 참고 * 진짜로 O(n^2)개의 모든 페어에 대해서 전부 구해야 하는 문제가 있고, 그 정도까지는 아니고 Q개의 쿼리에 대해서 구해야 하는 문제가 있을수 있다. text/html 2023-01-11T15:54:51+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%A0%91%EB%AF%B8%EC%82%AC_%EB%B0%B0%EC%97%B4?rev=1673452491&do=diff 접미사 배열 (Suffix Array) * 참고 * <https://en.wikipedia.org/wiki/Suffix_array> * <https://koosaga.com/125> * <https://cp-algorithms.com/string/suffix-array.html> * 주어진 한개의 문자열에서 어떤 정보를 뽑아내야 할 때 사용할수 있는 가장 강력한 알고리즘이다 * prefix에 관한 정보는 KMP 알고리즘이나 Z 알고리즘으로 대충 해결되는 경우가 많지만, 일반적인 부분문자열에 관한 것은 접미사 배열이 필요한 경우가 많다.… text/html 2025-03-07T13:15:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%A0%95%EA%B7%9C_%ED%91%9C%ED%98%84%EC%8B%9D?rev=1741353333&do=diff text/html 2025-02-16T12:39:02+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%A0%95%EC%88%98%EB%A1%A0?rev=1739709542&do=diff 정수론 * 특별히 여기에 쓸 내용은 없는데.. * 그냥 따로 하부페이지를 만들기 애매한 잡다한 것들을 적어보자.. 잡다한 지식 * 시간복잡도 계산을 위해, 어떤 수의 약수의 개수(= τ(n)) 가 필요할때에는 O(n^1/3) 으로 두면 대충 맞는다.$ D(n) = \sum_{1 \le k \le n}{\tau(k)} $ text/html 2025-02-16T06:01:01+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%A0%95%EC%88%98%EB%A1%A0%EC%A0%81_%ED%95%A8%EC%88%98?rev=1739685661&do=diff 정수론적 함수 f(N)을 계산 * 1부터 sqrt(N)까지 증가시키면서 찾는다. O(sqrt(N)) f(1)+f(2)+...+f(N)을 계산 * <https://ahgus89.github.io/algorithm/Harmonic-Lemma/> 를 참고. * 어떤 함수들에 대해서는 $\sum_{i=1}^{n} f(i) = \sum_{d=1}^{n} g(d)[{n \over d}] $ 로 표현 가능하다 * f(x) = τ(x) (x의 약수의 갯수) $ \sum_{i=1}^{n} \tau(i) = \displaystyle \sum_{d=1}^{n} [{n \over d}] $$ \sum_{i=1}^{n} \sigma(i) = \displaystyle \sum_{d=1}^{n} d[{n \over d}] $$\sum_{i=1}^n\lfloor\frac ni\rfloor=2\sum_{i=1}^k\lfloor\frac ni\rfloor-k^2$$k=\lfloor\sqrt … text/html 2023-06-14T04:53:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%A0%9C%EA%B3%B1%EC%88%98%EC%9D%98_%ED%95%A9?rev=1686718429&do=diff 제곱수의 합 * 자연수 n을 최소갯수의 제곱수의 합으로 표현하는 것에 관련된 이론들이다. * 크게 두가지 주제가 있다. * n을 제곱수의 합으로 표현할 때 필요한 제곱수의 최소 갯수를 찾기$ K \cdot \frac{n}{\sqrt{\ln n}} $ text/html 2022-07-07T07:08:57+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B2%B4%EC%8A%A4_%EA%B8%B0%EB%AC%BC_%EB%B0%B0%EC%B9%98?rev=1657177737&do=diff 체스 기물 배치 문제 (N-Queen, Rook, Bishop, ...) N-Queens * N*N 체스판에 N개의 퀸을 배치하는 유명한 문제. (Eight queens puzzle) * 배치할수 있는 방법의 갯수를 세는 문제는 백트래킹 연습문제로 흔히 등장한다. * $ n!+\sum_{k=1}^n {(-1)^k}(n-k)!\sum_{i=1}^k 2^{i} \binom{k-1}{i-1}\binom{n-k+1}{i} $ text/html 2024-02-23T01:18:39+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EB%8B%A8_%EA%B2%BD%EB%A1%9C?rev=1708651119&do=diff 최단 경로 (Shortest Path Problem) * 크게 두 종류의 문제 유형이 있다. * 단일 출발지 최단 경로 * 모든 쌍 최단 경로 * 사실 이보다도 흔히 나오는 것은 특정 쌍 최단 경로인데, 이것은 보통 단일 출발지 최단 경로 알고리즘으로 처리한다. text/html 2023-07-27T14:09:38+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EB%8C%80_%EB%B6%80%EB%B6%84%ED%95%A9?rev=1690466978&do=diff 최대 부분합 (Maximum subarray problem) * 주어진 배열의 부분배열중에서 합이 최대가 되는 것을 찾는 문제. Maximum_subarray_problem를 참고 * 가장 무식한 방법은 O(n^2)개의 모든 구간에 대해서 일일히 합을 전부 계산해보는것. O(n^3)이 된다 text/html 2023-12-20T06:00:37+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EB%8C%80_%EC%9C%A0%EB%9F%89?rev=1703052037&do=diff 최대 유량 (Maximum Flow) * 참고: * <https://koosaga.com/18> 전반적인 요약 알고리즘 * 다양한 알고리즘들이 존재하고, 실제로 사용되는 알고리즘들도 다양한 편이다. * 목록과 요약은 위키를 참고 * 잘 알려져 있는 알고리즘들에 대해서만 간단히 언급해보자$O(fE)$$O(VEU)$$O(VE^2)$$O(V^2E)$$O(VElogV)$$O(min(V^{2/3}E, E\sqrt{E}))$$O(E\sqrt{V})$$O(E\sqrt{V})$$O(VElogU)$$O(E^2logU)$$O(V^2\sqrt{E})$$ O(V^2E) $$ O(V^3) $$ O(VElog{{V^2}/E})$$ O(V^3) $$O(V^2\sqrt{E})$$O(|E|^{1+o(1)})$… text/html 2026-01-25T06:13:06+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98?rev=1769321586&do=diff 최대공약수 (GCD; Greatest Common Divisor) * 최대공약수가 뭔지는 생략해도 충분할듯. * 한국어 위키피디아에는 ko:최대 공약수로 등록되어있지만, 띄어쓰기 없이 붙여 쓰는게 맞다고 한다. 최대공약수 알고리즘 text/html 2022-06-23T02:56:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EC%86%8C_%EB%B9%84%EC%9A%A9_%EC%B5%9C%EB%8C%80_%EC%9C%A0%EB%9F%89?rev=1655952985&do=diff 최소 비용 최대 유량 (MCMF, Minimum Cost Maximum Flow) [작성중] 알고리즘 * Successive shortest path * (=capacity scaling ??) * 가장 널리 쓰이는 방법. 포드풀커슨 알고리즘과 비슷한 원리로, Shortest path를 찾고, 그 패스에 플로우를 할당하는 것을 반복한다 text/html 2024-11-09T13:54:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EC%86%8C_%EC%8B%A0%EC%9E%A5_%ED%8A%B8%EB%A6%AC?rev=1731160465&do=diff 최소 신장 트리 (Minimum Spanning Tree / MST) * 기본적인 내용은 위키피디아 참고 * 최대 신장 트리는, 웨이트에 모두 마이너스를 붙인 그래프에서 최소 신장 트리 찾는 방식으로 찾을수 있다. 알고리즘 * text/html 2023-11-29T15:12:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EC%86%8C%EC%BB%B7?rev=1701270745&do=diff 최소 컷 (Minimum Cut) * 이제 막 작성 시작한 단계 * <https://koosaga.com/192> * undirected 그래프에서 정의되는 것이다. 가중치 없는 그래프, 가중치 있는 그래프 모두 계산 가능 * s-t min cut은 Max flow min cut 정리를 이용해서 플로우로 풀 수 있다 text/html 2023-02-19T03:58:58+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B5%9C%EC%86%9F%EA%B0%92%EC%9D%84_%EC%B0%BE%EB%8A%94_%EC%A0%90%ED%99%94%EC%8B%9D%EC%9D%98_%EC%B5%9C%EC%A0%81%ED%99%94?rev=1676779138&do=diff 최솟값을 찾는 점화식의 빠른 계산 * 문서 제목을 정하는게 제일 어려웠다; 대충 뭔 뜻인지는 알것이다.. * 내 느낌상 DP를 통해서 구해야 하는 문제의 90% 이상은 조건을 만족하는 답의 갯수를 구하는 문제 text/html 2026-03-16T08:29:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98?rev=1773649775&do=diff 카탈랑 수 (Catalan number) * 카탈란 수라고 표기하는 책도 많은 것 같은데, 여기서는 위키피디아를 따라서 카탈랑수로 표기한다 * 사실 이 수열을 처음 만든 사람은 카탈랑이 아니다. 기록상 처음 사용한 사람은 몽골 수학자 명안도이고, 유럽 기준으로는 오일러가 삼각분할의 갯수를 설명할때 처음 사용했다.$ C_n = \frac{1}{n+1}{2n \choose n} $$ O(4^n / n^{\frac{3}{2}}) $\begin{align} &C_0 = 1 \\ &C_{n+1} = \sum_{i+j=n} C_iC_j \end{align}$ C_{n+1} = \frac{2(2n+1)}{n+2}C_n $$ C_n = \frac{2n!}{n!(n+1)!} $$ C_{n/2} $$ DP_{n+1} = \sum_{i+j+k=n} DP_iDP_jDP_k $$ C^{(3)}_n = \frac{1}{2n+1}{3n \choose n} $$ C^{(k)}_n = \frac{1}… text/html 2022-07-05T06:26:57+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%EC%BD%94%EB%94%A9_%ED%99%98%EA%B2%BD?rev=1657002417&do=diff 코딩 환경 * 로컬에 IDE를 설치하는것이 싫다보니 cloud에서만 작업중. 현재는 google cloud shell을 메인으로, gitpod를 세컨으로 사용중 * 사용했던 IDE * c9 : 잘 쓰다가 유료화되어서 포기 * goorm : 잘 쓰다가 오류가 자주 나서 포기 text/html 2024-02-26T02:32:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%88%AC_%ED%8F%AC%EC%9D%B8%ED%84%B0?rev=1708914765&do=diff 투 포인터 * 흔히 투 포인터라고 부르기는 하는데, 정확히 뭐를 투 포인터라고 부르는지 명확하게 정의된건 아닌것 같다. 대충, 두 개의 포인터를 유지하면서 조건에 따라서 적합한 한쪽을 이동시키는 것을 반복하는 방식으로 작동하는 알고리즘이면 전부 다 투 포인터로 부를 수 있는거 같긴 하다. 일반적으로는 한개의 일차원 배열 상에서, 양쪽 끝에서 출발하는 포인터 두개를 갖고 작업하거나, 한쪽에서 출발하는 두개의 포인터를 갖고 작업하는 경우에 쓰이는것 같지만, 두개의 정렬된 배열에 대해서 두개의 포인터를 유지하면서 머지하는 것을 구현하는 문제에도 투 포인터라는 태그가 붙어있는 것을 보기도 했다.… text/html 2021-05-22T17:13:00+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%8A%B8%EB%9D%BC%EC%9D%B4?rev=1621703580&do=diff 트라이 (Trie) 개념 * 생략. 검색하면 많이 나옴 유의점 * 파이썬에서는 트라이가 정해인 문제도 트라이를 안쓰는 것이 더 빠른 경우가 종종 있다. * 트라이를 활용하는 문제 유형은 다양하지만, 기본적으로는 단어들의 접두사들을 갖고서 어찌저찌 해보는 문제들이 대부분인데. 이런 문제들중 다수는 단어들을 정렬한 뒤, 인접한 단어들끼리 비교해보는 식으로도 풀리는 문제들이 많다.… text/html 2023-05-27T15:24:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%8A%B8%EB%A6%AC?rev=1685201083&do=diff 트리 (Tree) * [작성중] * 사이클이 없는 연결된 무향 그래프 * 연결되지 않으면 트리가 아니라 포레스트(forest). * 루트가 주어진 경우는 rooted tree라고 부른다 * rooted tree에서는 부모노드/자식노드가 정의되고, depth/height 개념이 적용된다 text/html 2025-10-31T06:46:14+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%8A%B8%EB%A6%AC%EC%9D%98_%EC%A7%80%EB%A6%84?rev=1761893174&do=diff 트리의 지름 * 참고 * <https://00ad-8e71-00ff-055d.tistory.com/115> * <https://codeforces.com/blog/entry/101271> * 먼저 관련된 텀들을 정리해보자 * 트리뿐 아니라 일반 그래프에서도 똑같이 정의되는 텀들이다. * 노드 v의 이심률(eccentricity of v): v와 다른 노드들 까지의 거리중 가장 긴 거리. (=v에서 가장 멀리 떨어진 노드까지의 거리) text/html 2026-03-31T15:14:28+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC?rev=1774970068&do=diff 팩토리얼 * n이 조금만 커져도 정수형 범위를 넘어간다. * 실용적인 경우에는 스털링 급수로 근사한 값을 쓰는 것으로 충분하다. * 하지만 PS에서는 정확한 값을 필요로 하기 때문에 p로 나눈 나머지를 구하게 하는 경우가 대부분이다.$ O(\sqrt{n}log^{2}n) $$ v_{p}(n!)=\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor $$ O(log_{p}{n}) $$ k = {p_1}^{e_1}\cdot{p_2}^{e_2} \cdot \ldots \cdot {p_m}^{e_m} $$ \min_i(\lfloor {\frac {v_{p_i}(n!)} {e_i}} \rfloor) $$ v_5(n!) $… text/html 2025-03-11T01:17:01+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%94%84%EB%A1%9C%EB%B2%A0%EB%8B%88%EC%9A%B0%EC%8A%A4%EC%9D%98_%EB%8F%99%EC%A0%84_%EB%AC%B8%EC%A0%9C?rev=1741655821&do=diff 프로베니우스의 동전 문제 (Frobenius coin problem) text/html 2024-04-09T14:55:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98?rev=1712674512&do=diff 피보나치 수 (Fibonacci numbers) * 피보나치 수를 구하는 여러가지 방법 과 <https://cp-algorithms.com/algebra/fibonacci-numbers.html>를 참고 * F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) 의 형태로 정의되는 수열. 초기 몇 항의 값은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 이다 * 여러가지 DP 문제들의 답이 피보나치 수가 되는 경우도 많고, 또한 수열 자체에도 여러가지 성질들이 많아서 그것들에 관한 문제도 많이 나온다. $$ F_{2k}=F_k(2F_{k+1}−F_k) \\ F_{2k+1} = F^2_{k+1} + F^2_{k} $$$ F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} $$ {\displaystyle \sum _{k=0}^{n}F_{k}=F_{n+2}-1} $$ {\displaystyle \sum _{k=0}^{n… text/html 2020-12-11T14:57:57+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%ED%9E%99?rev=1607698677&do=diff 피보나치 힙 * 위키피디아 * 피보나치 힙을 처음 접하는 것은 보통 Dijkstra's algorithm이나 Prim's algorithm을 배울 때이다. 시간복잡도를 놀랍게 단축해 줄 수 있다고 전해진다. * 일반적인 바이너리 힙과 달리, 삽입과 decrese-key 연산을 O(logn)이 아닌 O(1)에 처리할 수 있다고 한다 text/html 2022-11-26T15:55:14+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%99%95%EB%A5%A0%EB%A1%A0?rev=1669478114&do=diff 확률론 기댓값 * 중고등학교에서 배우는 기본적인 내용이면 충분하다. * 학교에서 배울때와는 달리, PS에서는 연속확률변수를 다룰 경우는 거의 없고 이산확률변수에 대해서만 사용할테니 이쪽만 보자.$ \operatorname {E} [X]=\sum _{i}p_{i}x_{i} $$ \operatorname {E} (X+Y)=\operatorname {E} (X)+\operatorname {E} (Y) $$ \operatorname {E} (cX)=c\operatorname {E} (X) $ text/html 2021-08-13T05:53:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/%ED%99%95%EC%9E%A5_%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1628834006&do=diff 확장 유클리드 알고리즘 유클리드 알고리즘 * 그냥 유클리드 알고리즘(=유클리드 호제법)은, 두 수의 최대공약수를 구하기 위해 사용되는 알고리즘이다. * 로직도 심플하고 코드도 간단하게 작성 가능하다 (재귀함수로 구현하면 한줄에도 가능). text/html 2024-07-19T04:51:03+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/advent_of_code?rev=1721364663&do=diff Advent Of Code * 사이트 링크: <https://adventofcode.com/> * 매년 12월 1일부터 25일까지 매일 한 문제씩 문제가 올라오는 사이트. Advent calendar을 모티브로 한다 * 2015년에 처음 시작되어서 지금까지 매년 이어져오고 있다. text/html 2024-03-15T14:32:46+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/apsp?rev=1710513166&do=diff 전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP) text/html 2025-05-06T07:04:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/bcc?rev=1746515083&do=diff 이중 연결 요소 (Bi-connected Component) * 작성중 * 유향그래프에서의 scc의 무향그래프 버전이라고 생각하면 얼추 비슷하다. 대충 사이클 같은것 이라고 생각하면 개념도 대충 비슷하고 활용 방법도 비슷하다. 유향그래프에서 그래프 특성에 관련된 것을 구할때 무지성으로 SCC로 분할해서 DAG를 만들어 놓고 생각해봤다면, 무향그래프에서는 BCC로 분할해서 tree를 만들어 보는것도 방법이다.… text/html 2026-04-25T16:16:39+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/blind_75?rev=1777133799&do=diff Blind 75 * NeetCode 의 문제셋 중 하나. 문제들의 출처는 LeetCode * “The Blind 75 is a popular list of algorithm practice problems.” Arrays & Hashing * Contains Duplicate * . * . * . * Top K Frequent Elements text/html 2020-11-11T14:35:00+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/boj?rev=1605105300&do=diff Baekjoon Online Judge (BOJ) text/html 2023-02-20T09:09:37+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/cht?rev=1676884177&do=diff 볼록 껍질을 이용한 최적화 * [정리 예정] * 제대로 정리를 해야 되지만, 급한대로 3줄요약부터 하자.. * f_i(x) = a_i * x + b_i 형태의 1차함수들이 N개 있을때, 어떤 x=k에 대해서 min_i{f_i(k)} 값을 계산하는 것을 O(N)보다 빠르게 할수 있다. 이것이 기본 아이디어이다. text/html 2023-11-15T03:08:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/convolution?rev=1700017700&do=diff 합성곱 (Convolution) * 위키피디아에 있는 합성곱에 대한 요약설명은 “하나의 함수와 또 다른 함수를 반전 이동한 값을 곱한 다음, 구간에 대해 적분하여 새로운 함수를 구하는 수학 연산자” 이다. * $ (f * g )(t) = \int_{-\infty}^\infty f(\tau) g(t - \tau)\, d\tau $$ (f * g)(m) = \sum_n {f(n) g(m - n)} $$(f * g)(m) = \sum_n{f(n) g(m-n)} = \sum_{i+j=m} {f(i) g(j)} $$(f * g)(m) = \sum_{i★j=m} {f(i) g(j)}$ text/html 2024-02-29T02:46:47+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/dag?rev=1709174807&do=diff 방향 비순환 그래프 (Directed Acyclic Graph; DAG) * Directed acyclic graph * 정리는 천천히 하자 * 대충 키워드들만 적어두면 * 수학적으로는 poset 에 대응된다 * O(V+E)에 위상정렬이 가능하다 * 위상정렬 순서대로 각종 DP문제를 풀수 있다. 보통 O(V+E) text/html 2023-02-20T09:13:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/dfs?rev=1676884425&do=diff 깊이 우선 탐색 (Depth-first search; DFS) * 작성 예정 구현 관련 * Recursive or Iterative? * 원하는 동작을 가장 간명하고 직관적으로 구현하는 방법은 재귀적으로 짜는 방식이다. * 방문만 처리할때에는 스택을 써서 비재귀적으로 구현할수 있다 text/html 2022-11-07T14:06:44+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/disjoint_set?rev=1667830004&do=diff Disjoint Set * 웬만하면 한글 번역된 이름을 먼저 쓰고 싶었는데, 이거는 사용 빈도가 압도적인 번역이 있는 것도 아니고, 번역된 이름들도 다 마음에 들지 않는다. 서로소 집합, 분리 집합 다 어색하고, 그냥 디스조인트 셋 또는 유니온파인드 셋 이렇게 쓰는게 사용 빈도가 더 많아 보인다.. text/html 2023-11-10T05:44:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/fft?rev=1699595072&do=diff 고속 푸리에 변환 (Fast Fourier Transform, FFT) text/html 2022-10-21T06:54:02+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/formatter?rev=1666335242&do=diff Python Formatter * 세줄요약 * 2022년 10월 21일 부터는 * YAPF 대신 * BLACK으로 포매팅한다 요약 안된 버전 * 파이썬의 auto-formatter중 많이 쓰이는 것은 AutoPEP8, BLACK, YAPF 이 있다. * 이 세개를 뽑은 이유는, vscode의 기본 선택 옵션이 이렇게 세개이기 때문 text/html 2023-11-10T06:36:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/fwht?rev=1699598192&do=diff Fast Walsh Hadamard Transform (FWHT) * Hadamard는 프랑스 이름이라서 '아다마르' 라고 읽는다 (위키피디아 - 아다마르 행렬) * 참고 * <https://velog.io/@dnr6054/Fast-Walsh-Hadamard-Transform> : 개념설명이 좋음 * <https://gina65.tistory.com/30> : FFT를 모르는 상태에서도 이해가 가능한 설명 + 코드가 포함되어있음 + or/and convolution에 대해서도 설명되어있음$ (f*g)(m)=\sum _{n}{f(n)g(m⊕n)}\ $ text/html 2024-11-08T07:44:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/import_inliner?rev=1731051889&do=diff Import Inliner * 작성예정. * 같은 목적이지만 다른 방식으로 구현된 라이브러리로 <https://github.com/bayashi-cl/expander/blob/main/README-en.md> <- 이런걸 찾았다 text/html 2025-11-13T07:04:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/inversion_counting?rev=1763017483&do=diff Inversion Counting * 어떤 수열 A에서, i<j 인데 A[i]>A[j] 인 (i,j)쌍을 inversion이라고 하고, inversion의 개수를 반전수라고 한다. inversion counting은 반전수를 계산하는 것이다. * 반전수는 분할정복 또는 Order statistic tree 를 이용해서 O(nlogn)에 계산할수 있다. text/html 2023-04-25T12:03:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/k-means_clustering?rev=1682424213&do=diff k-means clustering * [작성중] * 이걸 써서 푼 문제는 17978이 유일한데, 이것도 사실 정해는 아니다. * k-means clustering으로 나눠진 decision boundary는 linear하다 * 보로노이 다이어그램이 만들어진다 text/html 2022-12-21T12:51:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/kmp_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1671627113&do=diff KMP 알고리즘 * 기본적으로 KMP 알고리즘은 문자열 매칭을 선형시간에 해결해주는 알고리즘이다. * KMP 알고리즘에서는 문자열 매칭을 위해서 fail 함수라는 것을 정의해서, 패턴 P에 대한 fail함수의 table을 구하고, 이를 이용해서 스트링 S에서 P의 모든 occurrence를 효율적으로 찾는다. text/html 2024-01-10T09:16:05+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/lca?rev=1704878165&do=diff 최소 공통 조상 (Lowest Common Ancestor / LCA) * LCA를 구하는 알고리즘이라고 하지만, 그냥 노드 한쌍에 대해서만 LCA를 구하는 것은 어떻게 하든 O(n)에 처리된다. * 여기서 다루려는 알고리즘은, q개의 노드 쌍에 대해서 LCA를 구하는 것, 즉 LCA 쿼리들을 빠르게 처리하는 방법이다. text/html 2026-04-25T12:06:42+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/leetcode?rev=1777118802&do=diff LeetCode * 리트코드에서 중요한 문제들을 큐레이션해놓은 neetcode.io 라는 사이트도 있다 * Blind 75, NeetCode 150, NeetCode 250 의 문제셋이 있다 문제들 문제 번호Page분류시간복잡도해결날짜217Contains DuplicateO(n)2026/04/24207Course ScheduleO(v+e)2020/11/18373 text/html 2023-08-31T05:38:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/maximum_overlapping_intervals?rev=1693460303&do=diff Maximum overlapping intervals * 구간들이 여러개 주어졌을때, 구간이 가장 많이 겹치는 점에서의 갯수를 구하는 문제. * 그리디 알고리즘의 대표적인 예제문제인 최소 강의실 배정과 동일한 문제가 된다. text/html 2022-04-03T13:13:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/monotonic_priority_queue?rev=1648991634&do=diff Monotonic Priority Queue * Monotone priority queue를 참고 * 우선순위큐에서, extract-min 연산으로 추출되는 값이 항상 모노토닉할 때 사용할 수 있는 구조. 일반적인 우선순위큐보다 쓰는 데에 제약이 걸린 대신에 좀더 빠르게 동작하도록 구현할 수 있다. text/html 2020-12-10T05:22:40+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/n-queens?rev=1607577760&do=diff N-Queens * 유명한 Eight Queens Puzzle의 일반화 버전. * 백트래킹을 공부할때 흔히 사용되는 예제이기도 하다. * 워낙 유명한 문제다 보니 여기저기 자료들도 많으니, 기본적인 것만 요약하면 * N*N칸 중에 N칸을 고르는 방법으로 접근하면 C(N*N, N) 인데 이건 너무 비효율적이고.. text/html 2023-07-25T02:11:50+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/old_ps_%ED%83%88%EC%B6%9C_%EB%A6%AC%EC%8A%A4%ED%8A%B8?rev=1690251110&do=diff (OLD) PS 탈출 체크리스트 * 원래는 2023년 상반기 중에 탈 PS를 이루기 위해 관리하던 내용들이다. 2023년 7월말이 되도록 진행이 안돼서 폐기되었다. * 새로 짜여진 계획은 PS 탈출 체크리스트에 있다. 데일리 체크 text/html 2025-12-03T04:24:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/order_statistic_tree?rev=1764735893&do=diff Order Statistic Tree * 참고 <https://codeforces.com/blog/entry/89170> * 처음에는 이런 용어가 따로 있는지를 몰랐다. 그래서 적당히 Ordered Set이라는 타이틀로 페이지를 만들었는데, 위키피디아에서 <https://en.wikipedia.org/wiki/Order_statistic_tree> 문서를 발견하고 타이틀을 바꿨다. text/html 2026-04-18T12:39:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/ps_%EC%9D%BC%EC%A7%80?rev=1776515952&do=diff PS 일지 * PS를 시작한지 한참 되었지만, 뒤늦게 부정기적인 일지를 쓰기 시작한다. 목표는 떨어지는 모티베이션을 다시 높이는 것. 2026/4/18 * 아 맞다. 내가 이런것도 썼던 적이 있었지. 3년만에 떠올렸네; text/html 2024-01-08T07:27:28+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/ps_%ED%83%88%EC%B6%9C_%EC%B2%B4%ED%81%AC%EB%A6%AC%EC%8A%A4%ED%8A%B8?rev=1704698848&do=diff PS 탈출 체크리스트 * (7/25) 상반기가 이미 한참전에 지났지만 탈 PS는 커녕 계획했던 목표를 하나도 달성하지 못했다. ㅠㅠ.. 목표를 다시 세워보자. 기존에 쓰던 트래커들을 (OLD) PS 탈출 체크리스트에 백업해놓겠다. text/html 2022-12-13T03:05:22+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/python_%EC%BD%94%EB%93%9C_%EC%88%98%ED%96%89%EC%8B%9C%EA%B0%84?rev=1670900722&do=diff 파이썬 코드 수행시간 * Python 3.11.0 기준으로 BOJ에서 수행한 결과 * 비교의 기준이 되는 가장 미니멈한 코드의 수행시간은 30616KB / 36ms * 1000로 테스트. (코드 <https://www.acmicpc.net/source/52480129>) 타입 어노테이션 * 타입 어노테이션을 위해서 typing이나 collections.abc 모듈을 import하는 것은 로딩시간에 꽤 영향을 준다. text/html 2024-12-06T13:16:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/python?rev=1733491009&do=diff Python 몰랐던 문법과 팁들 * and와 or 는 True/False 가 아니라 마지막으로 이밸류에이트된 값을 돌려준다 (링크) * JS에서 흔히 쓰듯이, (x if x else default) 와 같은 식을 (x or default)로 줄여 쓸수 있다. 딱히 안티패턴도 아닌듯 하다. text/html 2022-09-22T07:13:38+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/shortest_path_faster_algorithm?rev=1663830818&do=diff Shortest Path Faster Algorithm (SPFA) * Shortest Path Faster Algorithm 참고 * worst-case 시간 복잡도는 벨만 포드와 똑같은 O(VE)이지만, 평균 시간복잡도는 O(E)라고 한다. 평균 복잡도만 보면 무려 다익스트라보다도 빠르기는 하지만, PS에서 이러한 문제가 나올때는 대부분의 경우 테스트 케이스에 SPFA가 O(VE)로 돌게 만드는 저격용 케이스가 들어있으므로 O(E)를 기대하기는 어렵다. text/html 2023-02-15T08:40:42+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/smawk?rev=1676450442&do=diff SMAWK 알고리즘 * SMAWKalgorithm * SMAWK라는 이름의 유래는, 만든사람 5명의 이름의 첫 글자를 모아서 나온 것이라고 한다. 발음은 스모크(smoke)처럼 읽는다고 어디선가 봤었는데 출처를 까먹었다; * totally monotone matrix에서 row minima들을 O(n+m)에 찾아주는 알고리즘이다. text/html 2026-04-16T14:19:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/start?rev=1776349185&do=diff Problem Solving 목표 * 즐거운 PS (강조!!) * 대회에 참가할 것도 아니고, 기업의 코딩테스트를 볼 것도 아니다. 그냥 나에게 PS는 취미인데, 취미라면 즐거워야 한다. * 따라서, 코딩테스트 수준의 문제로 난이도를 한정지을 필요도 없다. 시간에 맞춰서 푸는 연습을 할 필요도 없다. text/html 2023-08-08T08:06:13+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/stern_brocot_tree?rev=1691481973&do=diff Stern-Brocot Tree * [작성 예정] * 참고자료 * Stern–Brocot_tree * 유리수 범위에서의 이진탐색에 활용 * <https://blog.myungwoo.kr/126> * <https://gumgood.github.io/the-stern-borcot-tree> * 수론적 함수의 빠른 계산 (약수함수의 합) 에 활용 * <https://youngyojun.github.io/secmem/2022/02/18/sigma-sum-stern-brocot/> text/html 2023-03-13T02:02:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/strongly_connected_component?rev=1678672955&do=diff 강한 연결 요소 (Strongly Connected Component / SCC) * 내가 학생시절 배울때 들었던 이 용어의 번역은 '강결합 요소'였다. 그런데 검색해보니 강결합요소, 강연결요소, 강한 결합 요소, 강한 연결 요소 등등이 모두 사용되고 있었다.. 일단 한국어 위키피디아를 기준으로 강한 연결요소라고 제목을 달아놓긴 했는데.. 웬만하면 그냥 SCC라고 부르는게 편할것 같다. text/html 2026-04-25T14:39:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/syntax_highlighter?rev=1777127989&do=diff Syntax Highlighter * 코드를 페이지에 올리기 위해 사용할 Syntax Highlighter을 찾아봤다. * 주로 올리게 될 언어는 Python과 C++이겠지.. * 사실 많은 기능은 필요 없다. 기능적으로는 라인 넘버를 붙여주는 기능정도만 있으면 좋겠고, 나머지는 그냥 적당히 눈에 안거슬리는 디자인으로 가볍고 빠르고 안정적이면 충분. text/html 2023-08-04T14:46:19+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/teflib?rev=1691160379&do=diff text/html 2025-03-11T01:18:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/tutorial?rev=1741655890&do=diff text/html 2022-12-27T02:03:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/z_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?rev=1672106589&do=diff Z 알고리즘 * Z 알고리즘은 Z array를 빠르게 구하는 알고리즘이다. O(n)에 Z array를 구할수 있다. * 참고 : * <https://cp-algorithms.com/string/z-function.html> * <https://blog.chodaeho.com/posts/2021/z-algorithm/> Z array * Z array는 S와 S[i:]의 최대공통접두사의 길이를 저장하는 배열이다. text/html 2023-11-15T03:15:13+00:00 Anonymous (anonymous@undisclosed.example.com) https://admin.teferi.net/ps/zeta_mobius_transform?rev=1700018113&do=diff Zeta / Mobius transform * <https://www.acmicpc.net/blog/view/127> * Poset, Zeta/Mobius transform, SOS DP, or/and convolution 으로 이어지는 상세하고 친절한 설명 * <https://codeforces.com/blog/entry/115438> * or convolution을 SOS DP로 접근하는 아이디어. 댓글에서 보다 일반적인 연산자들에 대한 convolution으로 접근하는 방법이 설명됨