본문 바로가기

전체 글

 (8)
백준 11718, 11719 그대로 출력하기 C++ STL을 기본적으로 공부했으니 문제풀이를 통해서 공부하여 보겠습니다. 우선 입출력 기초를 공부하기 위해 https://www.acmicpc.net/problem/11718 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net https://www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수..
C++ STL sort Sort C++ STL 개념의 마지막인 sort에 대해서 알아보겠습니다. 슬슬 개념공부가 지겨워서 빨리 문제를 풀고 싶은데 다행입니다. 1) Sort의 정의 C++의 sort() 함수는 기본적으로 오름차순의 정렬을 수행합니다. 정렬 방식은 quick sort를 기반으로 heap sort, insertion sort를 섞은 방식으로 nlogn의 시간복잡도를 가집니다. 2) Sort의 사용 sort() 함수를 사용하기 위해서는 을 include 해주어야 합니다. vector를 정렬한다고 가정하였을 때 sort(v.begin(), v.end()); 로 정렬을 진행하여 줄 수 있습니다. 만약 크기가 10인 배열 arr을 정렬한다면 sort(arr, arr+10); 으로 정렬을 해 줄 수 있습니다. 3) Sort..
C++ STL next_permutation 순열이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다. C++에서는 next_permutation과 prev_permutation을 이용하여 이것을 손쉽게 구할 수 있습니다. next_permutation 1) next_permutation의 사용방법 #include 으로 algorithm 헤더파일을 추가하여야 합니다. 그리고 next_permutation에게 컨테이너의 시작과 끝 iterator를 인자로 전달하여 줍니다. 해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 다음 순열로 순서를 바꾸고 true를 반환합니다. 만약 다음 순열이 존재하지 않는다면 false를 반환합니다. 설명만으로는 이해하시기 어려울테니 예시를 들어서 설명을 드리겠습니다. #include #i..
C++ STL lower_bound, upper_bound lower_bound와 upper_bound에 대해서 포스팅 하겠습니다. 둘 다 컨테이너에 적용할 수 있으며 주어진 범위에서 조건에 맞는 위치를 iterator로 반환합니다. 이진 탐색을 사용하기 때문에 컨테이너는 정렬되어 있어야합니다. 컨테이너 중 vector를 기준으로 자세하게 알아보겠습니다. lower_bound 1) lower_bound의 정의 시작 iterator ~ 끝 iterator 사이에서 value 이상인 값을 가지는 이터레이터를 반환하는 것이 lower_bound입니다. 즉, value와 같거나 큰 값이 처음 나타나는 위치를 iterator로 반환합니다. 여담) value와 같거나 큰 값을 처음 반환하는데 왜 lower_bound라는 이름이 붙었지? 하는 궁금증을 가지게 되어서 사전에 ..
C++ STL Iterator Iterator를 모른채로 여러 Vector, Map, Set 같은 컨테이너들을 공부하니까 함수들을 이해하는 부분에서 어려움을 겪었습니다. 오늘 Iterator에 대해서 공부해보고 앞에서 놓친 부분들까지 포스팅해보도록 하겠습니다. Iterator 1) Iterator의 정의 STL에서 Iterator는 포인터와 비슷하게 동작합니다. STL의 모든 컨테이너는 각각 반복자를 제공합니다. 이를 이용하여 컨테이너에 저장되어 있는 원소들을 참조할 수 있습니다. 그래서 각 컨테이너가 적절한 알고리즘(검색, 삭제, 복사 등)을 동작하는 것을 도와줍니다. 쉽게 이해하자면 컨테이너가 가지고 있는 원소에 접근할 때 사용하는 것이 iterator입니다. 2) Iterator의 종류 각 컨테이너가 제공하는 Iterator의 ..
C++ STL Set Set Set에 대해서 공부를 하여보니 이전에 포스팅했었던 Map과 거의 유사합니다. 다른 점이 있다면 Map은 key와 value의 pair를 데이터로 저장하고, Set은 key만을 데이터로 저장합니다. Map에 대해서 완벽하게 이해하셨다면 Set은 한번 읽어보면 쉽게 넘어갈 수 있을 것 입니다. 1) Set의 정의 Set은 key라고 불리는 원소들의 집합으로 이루어진 트리입니다. (key의 중복을 허용하지 않습니다.) Set은 데이터를 저장할 때 key를 기준으로 정렬하며 오름차순으로 정렬합니다. Set의 내부 구현은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구성되어 있습니다. 2) Set의 사용 Set을 사용하기 위해서는 다음의 과정을 거쳐 사용하면 됩니다. 1. 헤더파일 추가 : #in..
C++ STL Map Map 1) Map의 정의 Map은 각 노드가 key와 value의 쌍으로 이루어진 트리입니다. (key의 중복을 허용하지 않습니다.) Map은 데이터를 저장할 때 key를 기준으로 정렬하며 오름차순으로 정렬합니다. Map의 내부 구현은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구성되어 있습니다. 레드블랙트리의 index numbering에 주의합니다. 2) Map의 사용 Map을 사용하기 위해서는 다음의 과정을 거쳐 사용하면 됩니다. 1. 헤더파일 추가 : #include 2. using namespace std; (편의상) 3. map [변수 이름] ex) map m; -> key를 기준으로 오름차순 정렬 ex) map m; -> key를 기준으로 내림차순 정렬 3) Map의 함수 앞에서와..
C++ STL Vector 이때까지 C만 사용하다가 C++로 넘어오게 되었습니다. class 사용 가능 등 객체지향 프로그래밍이 가능하다는 장점도 있겠지만, 무엇보다 STL이 사용가능하다는 것이 C++를 공부하게 된 가장 큰 계기가 된 것 같습니다. STL은 사용법, 특성만 간단히 공부하고 문제를 풀어보면서 부족한 부분을 공부하는 방식으로 학습하겠습니다. Vector 1) Vector의 정의 Vector는 자동으로 메모리가 할당이 되는 배열이라고 생각하면 됩니다. C에서는 동적으로 사용할 것이 아니면 정적으로 크기를 지정해놓고 배열을 사용하여야 했지만 C++에서는 vector를 이용해서 쉽게 배열의 크기를 늘리고 데이터를 집어넣을 수 있습니다. 2) Vector의 사용 Vector를 사용하기 위해서는 다음의 과정을 거쳐 사용하면 ..

티스토리툴바