선택은 나의 것

이 문서는 마크다운으로 작성되었으며 github 스타일에 최적화되어있습니다. github 링크를 통한 열람을 권장합니다. Map & UnorderedMap std::map Map이란 Key와 Value를 가진 집합으로, 중복을 허용하지 않는 컨테이너를 말한다. 레드블랙 트리(Red-Black Tree)를 기반으로 구현되어 있다. 따라서 모든 데이터는 정렬되어 저장되며, 정렬이 필요하지 않은 경우에도 자동으로 정렬되기 때문에 불필요하게 감수해야 하는 오버헤드가 발생했다. 입력되는 key 값의 분포가 고르지 못할 경우 balancing에 대한 비용이 계속 들어가기 때문에 성능이 저하된다. 동시에 self-balancing이 있기 때문에 최악의 경우에도 탐색속도는 O(logN)으로 보장된다. std::unor..

문제 BOJ 14426 : https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 접근 이 문제는 입력으로 주어지는 N과 M의 최댓값이 10,000이고, 각각의 문자열의 최대 길이도 500밖에 안되기 때문에 단순하게 조합 가능한 모든 문자열을 대입해 해결하는 브루트 포스(brute force)로 해결할 수 있다. 하지만 나는 수행 시간을 단축하기 위해 이분 탐색(Bi..

문제 BOJ 1701 : https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 접근 두 번 이상 나오는 부분 문자열 중 가장 긴 부분 문자열을 구하는 문제이기 때문에 KMP 알고리즘을 이용해 문제를 풀었다. KMP 알고리즘에 관한 설명은 아래의 포스팅을 참고 바란다. [BOJ 백준] 1305번 광고 문제 BOJ 1305 : https://www.acmicpc.net/problem/1305 1305번: 광고 첫째 ..

문제 BOJ number : https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 접근 백준 1725번 히스토그램 문제와 풀이방법이 똑같은 문제이다. [BOJ 백준] 1725번 히스토그램 문제 BOJ 1725 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이..

문제 BOJ 1725 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 접근 백준 님의 문제 풀이 설명글에서 힌트를 얻어 문제를 해결하였다. 분할 정복을 이용하는 방법과 스택을 이용하여 문제를 해결하는 방법이 상세하게 설명되어있다. 코드 #include #include #include using namespace std; int n, ans = 0, top, arr[100005]; stack s; int main(..

문제 BOJ number : https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 접근 우선순위 큐와 set을 이용하여 자동으로 정렬이 되는 컨테이너라는 특성을 이용하여 문제를 해결할 수 있었다. 코드 #include #include #include #define endl "\n" using namespace std; priority_queue pe, out; se..