본문 바로가기
반응형

전체

[C++] vector container 정리 및 기본 사용법과 응용 [목차] 1. vector란? 2. vector의 장단점 3. vector 사용 준비 4. vector 생성자 5. vector 멤버 함수 6. 2차원 vector 7. vector의 응용 그동안 PS를 하면서 vector가 반드시 필요한 문제를 접하지 못해서 그런지, 항상 그동안 익숙했던 배열을 이용해 왔다. 하지만 vector를 이용하면 훨씬 편리하다는 주변의 조언에 따라 이제라도 최대한 vector를 이용하려고 한다. (사실 처음에 vector가 indexing이 안 되는 줄 알고 사용을 안 했는데, 배열과 똑같이 indexing이 되니 배열을 쓸 이유가 없는 것 같긴 하다....) 1. vector란? C++ STL에는 크게 두 개의 container가 있다. 배열처럼 원소들을 순서대로 보관하는 ..
[C++] lower_bound & upper_bound STL에서 제공하는 lower_bound와 upper_bound에 대해서 알아보자. LIS(Longest Increasing Subsequence)를 공부하다가 알게 된 개념이다. 필자 개인적으로는 STL에 대해서 잘 몰랐는데, 처음으로 STL이 매우 유용하다는 것을 깨닫게 해준 함수이다. (이를 계기로 계속 STL을 이용하려고 노력중이다) 우선 lower_bound와 upper_bound는 이진 탐색(Binary Search)을 기반으로 탐색하는 함수이다. 따라서 배열이나 리스트, 벡터 등이 기본적으로 정렬이 되어있어야 하고, 시간복잡도는 O(logn)이다. 기본적으로 이진 탐색은 찾고자 하는 원소가 있는지, 있다면 어디에 위치해 있는지를 찾는다면, lower_bound와 upper_bound는 이진 ..
[BOJ 2517] 달리기 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 세그먼트 트리(Segment Tree)를 이용한 문제이다. 각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다. 각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 여기..
[BOJ 2568] 전깃줄 - 2 문제 출처 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 유형의 문제이다. 전깃줄이 순서없이 입력되기 때문에 A 또는 B를 기준으로 정렬을 해주어야 한다. A를 기준으로 정렬한다면, 정렬된 후의 B 수열을 가지고..
LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 주어진 수열에서 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다. (당연히 어려운 문제로는 NlogN을 요구하는 문제가 나온다...) [개념] LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다. 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다. 예를 들어 위와 같은 길이가 8인 수열이..
[C++] STL - sort STL에서 제공하는 sort 함수를 알아보자. 우선 sort 함수를 이용하기 위해서는 헤더 파일을 include 해주어야 한다. sort함수는 퀵정렬을 기반으로 하므로 O(nlogn)의 평균 시간 복잡도를 가진다. sort 함수의 형태는 아래와 같다. 1 2 3 4 5 template void sort(T start, T end); //default 오름차순 template void sort(T start, T end, Compare comp); //compare 함수 정의 가능 위처럼 정렬 기준이 되는 함수 (comp) 를 추가하지 않는다면 기본적으로 '오름차순'으로 정렬해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; ..
[C++] STL - 스택(Stack) & 큐(Queue) 우선 스택(Stack)과 큐(Queue)의 기본 원리는 생략한다. STL에서는 스택과 큐를 템플릿 클래스로 제공하고 있다. [Stack] stack은 기본적으로 LIFO구조이며, STL에서는 default로 deque(덱) 컨테이너를 사용한다. 즉, 실제로 내부적으로는 deque 구조로 구현되어 있지만, stack과 같이 이용할 수 있도록 제공하는 것이다. stack container을 이용하기 위해서는 헤더를 include 시켜주어야 한다. 1. stack container 선언(생성자)은 다음과 같다. stack 이름 만약 내부 컨테이너 구조를 바꾸고 싶다면 다음과 같이 선언하면 된다. stack 이름 1 2 3 ..
[C++] 입출력 ( cin / cout ) C++에서 입출력을 수행하기 위해서는 헤더 파일을 이용한다. C에서의 와 동일하다. 1. 출력 (cout) C++에서 출력을 하기 위해서는 cout 함수를 이용한다. C에서의 printf와 같은 역할을 하는데, printf에서는 출력하는 변수의 자료형 (%d , %f 등)을 표현해주어야 했지만, cout은 출력 자료형을 지정하지 않아도 된다. 호출 예시는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 #include using namespace std; int main(void) { int a = 10; cout

티스토리툴바