참조 분류 URL 문제 스택 이 글에서 설명하는 코드 10828_스택 개요 시간복잡도: $ O(N) $ 공간복잡도: $ O(N) $ N은 명령의 수이다. 문제 풀이 이 문제는 말 그대로 스택 그 자체이다. 여기 에서 설명한 5가지 연산만 수행하면 끝이다. 구현 특히나 이 문제는 코딩의 순서를 문제에서 주어진 5가지 명령에 쓰인 그대로...

참조 분류 URL 문제 괄호 이 글에서 설명하는 코드 09012_괄호 개요 시간복잡도: $ O(TC \cdot L) $ 공간복잡도: $ O(L) $ TC는 테스트 케이스의 수, L은 문자열의 길이이다. 문제 풀이 괄호 짝 맞추기는 스택 문제의 단골손님이다. 이 문제의 핵심 아이디어는 다음과 같다. 문자열을 하나씩 읽는다. 여는 괄호 ( 가 나오면...

sharifa_header.h 코드 필자가 만든 라이브러리…라고 하기는 좀 그렇고, 그냥 헤더 파일이랑 #define 약간을 모아 놓은 헤더 파일이다. 필자의 코드에서 처음 보는 토큰들이 좀 있을 텐데, 잘 모르겠다면 위의 링크를 참조하면 된다. 예를 들면, ll은 long long이다. bit_library.h 코드 비트 관련 사용자 정의 함수를 모아 놓은 헤더 파일이다. bit 연산을 안다면...

참조 분류 URL 문제 큰 수 곱셈 응용 문제 koosaga BOJ FFT 문제집 참조 라이브러리 sharifa_header.h, bit_library.h 이 글에서 설명하는 라이브러리 fft.h 개요 시간복잡도: $ O(N log N) $ 공간복잡도: $ O(N) $ N은 두 수열의 길이의 max값이다. FFT는 convolution을 빠르게 해 주는 것이지만, PS에서는 거의 대부분 곱셈을 빠르게 하기...

참조 분류 URL 문제 히스토그램에서 가장 큰 직사각형 이 글에서 설명하는 코드 06549_히스토그램에서 가장 큰 직사각형 개요 시간복잡도: $ O(TC \cdot N) $ 공간복잡도: $ O(N) $ N은 직사각형의 수, TC는 테스트 케이스의 수이다. 즉 사실상 $ O(N) $이다. 이 글에서는 히스토그램에서 가장 큰 직사각형의 가장 빠른 풀이인 스택을 활용한...