* Pair 란? pair는, 두개의 값을 하나로 묶어주는 역할을 하는 struct로 데이터 쌍(pair)을 표현할 때 사용한다. 주로 vector로 묶어 2차원 배열처럼 사용하거나, 좌표를 표현할 때 사용된다. 헤더는 algorithm , vector 에 utility 헤더가 포함되어 있기 때문에, 따로 추가 안해줘도 된다. pair의 기본 형태는 pair p_name; 으로 정의해준다. pair는 따로 초기화 하지 않고, make_pair 를 사용해 필요할 때 원소를 삽입하는 방식으로 사용한다. * Pair 멤버 함수 p.first - pair의 첫번 째 인자를 반환한다. p.second - pair의 두번 째 인자를 반환한다. make_pair(val1, val2) - val1, val2를 가진 p..

ㅠㅠ 나 그래프 영원히 못풀줄 알았는데...... 이제 이해했다.... DFS, BFS 로 모두 풀어봤다. main 함수에서 원하는걸로 주석 처리하면된다. #include #include #include #include #include using namespace std; #define MAX 101 vector graph[MAX]; int visited[MAX]; int cnt = -1; void bfs(int r) { deque qq; visited[r] = 1; qq.push_back(r); while(!qq.empty()) { int tmp = qq.front(); qq.pop_front(); cnt++; for(int i = 0; i < graph[tmp].size(); i++) { int y ..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net * BFS 는 큐로 푼다. 완전 기본문제니까 이걸로 먼저 이론을 생각하면서 풀면 될거같다. ! 그리고 sort는 compare 함수를 써서 이용해버릇 하자. + cin/ cout 쓰면 시간초과구만.... 그냥 scanf / printf 로 쓰자. #include #include #include #include using n..

* DFS -> 재귀 , stack 으로 푼다. * sort의 헤더는 algorithm 이다. compare 함수로 내림차순 오름차순 구분할 수 있다. a > b 면 왼쪽이 오른쪽보다 크면 true로, 내림차순이고, return a < b; 면 오름차순이다. https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net #include #include #include #include u..

Header : , 1. pow ( 제곱 함수 ) double pow ( double a, double b ) pow(10,2) // -> 10의 제곱. 2. sqrt ( 제곱근 함수 ) double sqrt ( double x ) sqrt(4) // -> 2 3. ceil ( 올림 ) ceil(3.14) // -> 4 4. floor ( 내림 ), floor ( a+0.5 ) -> 반올림 floor(1.89) // -> 1 floor(1.89+0.5) // -> 2 헤더 cstdlib 에 있는 함수들 . 1. int abs ( 절대값 ) int abs(int num); long int abs(long int num); long long int abs(long long int num); 2. min, m..

Deque는 vector 의 단점을 보완하기 위해 만들어진 컨테이너라고 한다. 동일하게 배열 기반의 구조이고, 벡터의 단점인 동적 할당 과정을 보완했는데, 벡터처럼 새로 재할당 후 원소를 복사하는것이 아니고, * 새로 일정한 크기의 메모리 블록을 할당 함으로써 이전 원소를 복사하지 않는다. * 데이터의 삽입 삭제를 front, back에서 할 수 있다. * deque 중간에 원소를 삽입하거나 삭제 가능하다. (push_back, push_front, pop_back, pop_front.... 엥 다 할수 있잖아..?) 연습용으로 아래 포스팅의 다양한 예제들 한번씩 입력해보자... ! # 앞뒤 값 삽입 그리고 역순 출력 # #include #include using namespace std; int mai..

c++ stack의 헤더는, #include 이다. stack은 LIFO(Last In First Out) 후입 선출 ! 근데 stack 은 코테에서 많이 안쓰는 것 같다. 왜냐면 stack 의 단점이 있기 때문인데, vector처럼 [] 해당 요소 접근이 불가하다는 점 때문인듯. stack 선언 : stack stk; stack 삽입/삭제 : push(i) , pop(); -> 스택의 pop은 맨 위의 값을 pop한다. 큐의 pop은 맨 앞의 원소를 삭제한다. stack의 꼭대기값, 비었는지 확인하는 함수 : top(), empty() queue 도 쓰는 것 비슷하다. 근데 queue는 확실히 안쓰고, deque를 주로 쓴다고 한다. 왜냐면 보니까 deque()에 왠만한 함수 다 있다 ! #includ..

list 의 헤더는 #include 이다. 리스트는 아시다시피 양방향 연결구조를 가진 자료형이다. 벡터의 단점은 임의의 위치에 원소를 추가하려면 그 위치를 찾아가서 삽입/제거 해야하기때문에 시간 복잡도가 O(n)이지만, 리스트는 O(1)이다. vector와 다른점은, 위치를 이동할때 (loop 쓸때) lst + 5 요런건 불가능하다는거다. (vec.begin() + 5 이런것.. ) 함수는 vector와 동일한듯. push_back, pop_back... #include #include using namespace std; int main() { list lst; //list pointer 선언.. list::iterator iter = lst.begin(); for(int i = 0; i < 5; i+..

C++ 에서는 , 정적배열 선언시 배열의 크기를 정해야하는 단점을 보완한 것이라고한다. 애초에 동적배열 . vector는 push_back() , pop_back() 로 삽입과 삭제가 이루어진다. vector 배열의 size는 vec.size() 로 정의된다. vector 자료형은 값이 추가가 될 때마다 공간을 늘려가며 할당을 하므로, 더 큰 여유공간을 할당해둔다. 이걸 vec.capacity()라고 한다. 우선 자주 쓰이는 함수를 정리해보자. 임의의 위치 원소 접근 : vec.at[i] (시간복잡도 : O(1)) 원소 추가 및 제거 : push_back(i) / pop_back(i) (시간복잡도 : O(1)) 임의의 위치 원소 추가 및 제거 : insert(vec.begin() + 2, 15), era..

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G", "()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order. Given the string command, return the Goal Parser's interpretation of command. Examp..