고양이와 별무리 도서관 Post List

2805번: 나무 자르기 (acmicpc.net) 문제는 이진 탐색(Binary search) 문제 중 파라메트릭 서치(Parametric search) 문제입니다. Parametric Search란? Parametric search는 이진 탐색(binary search)의 변형 중 하나로, 주로 최적화 문제를 결정 문제로 변환해 푸는 데 사용됩니...

1654번: 랜선 자르기 (acmicpc.net) 문제는 이진 탐색(Binary search) 문제 중 파라메트릭 서치(Parametric search) 문제입니다. Parametric Search란? Parametric search는 이진 탐색(binary search)의 변형 중 하나로, 주로 최적화 문제를 결정 문제로 변환해 푸는 데 사용됩니...

개요 헤더 파일: <vector> STL 시퀀스 컨테이너 (sequence container): 선형 자료구조 탐색 시간: $O(1)$ (임의 접근) 요소 추가/삭제 $O(1)$ (재할당 하는 경우를 제외하고 배열의 마지막 위치에 요소를 추가하거나 삭제하는 경우) $O(N)$ (중간에 삽입/삭...

개요 헤더 파일: <array> STL 시퀀스 컨테이너 (sequence container): 선형 자료구조 탐색 시간: $O(1)$ (임의 접근) std::array는 배열의 STL 버전입니다. 자료 구조의 형태는 고정된 크기의 배열 그 자체지만, 기존의 배열을 사용하는데 있어서 문제점은 인덱스를 직접 지정해 줄 수 있...

배열이란, 연속적인 메모리 공간에 동일한 타입의 데이터를 저장하는 기본적인 형태의 자료구조 입니다. 여기에서 중요한 것은 물리적으로 연속적인 메모리 공간이고 동일한 타입을 저장한다는 것입니다. C++ (C++ 11)에서는 std::array라는 표준 템플릿 라이브러리(Standard Template Library, STL)가 추가되었습니다. 특징...

STL 알고리즘(Algorithm)은 데이터를 처리하고 조작하는 데 사용되는 함수 템플릿의 집합입니다. C++ STL의 <algorithm> 헤더 파일에는 다양한 알고리즘 함수들이 포함되어 있습니다. 이 알고리즘들의 일부를 나름대로 카테고리별로 나누어 표로 정리해 봤습니다. 정렬 알고리즘 설명 ...

히스토그램이란, 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형으로, 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 문제에서는 이 히스토그램에서 가장 넓이가 큰 직사각형을 분할 정복으로 구하는 방법을 물어보고 있습니다. 분할 정복(Divide and Conquer)이란, 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과...

반복자, 흔히 이터레이터(Iterator)라 불리는 이것은 STL(Standard Template Library)에서 매우 중요한 역할을 합니다. (이후 반복자라는 단어 보다는 이터레이터라는 단어를 사용하겠습니다.) 이터레이터는 컨테이너에 저장된 데이터를 순회하여 각 데이터에 대한 접근을 제공하는 객체입니다. 단순히 array나 vector와 ...

STL 컨테이너란? STL 컨테이너는 프로그래밍 언어에서 데이터를 저장하고 관리하는 다양한 방법을 말하는 자료 구조입니다. 동일한 타입의 여러 종류의 객체를 저장하는 일종의 집합이라고 볼 수 있습니다. 다양한 종류의 컨테이너가 있으며, 각각 고유한 방식으로 데이터를 저장하고 관리합니다. 주요 컨테이너 유형 1. 시퀀스 컨테이너 (Seque...

11444번: 피보나치 수 6 (acmicpc.net) 문제도 분할 정복(Divide and Conquer)으로 풀어볼 수 있습니다. 분할 정복이란, 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 합쳐 원래 문제의 해결책을 찾는 방법입니다. 이 문제는 행렬의 곱셈과 관련있기 때문에, 다음의 문제들을 풀어보고 푸는 것을 추천 드립니다. ...