투 포인터는 매우 쉽고 효율적인 테크닉으로, 일반적으로 소팅된 배열에서 검색하는 방법이다. 주어진 배열 A(sorting in ascending order), 그리고 N integers 가 있다.(target값). 해당 배열에서 임시로 설정한 pair( A[i], A[j] ) 의 합이 target 과 같은 것이 있는지 찾는 것이다. 예시를 보며 이해해보자. A[] = {10, 20, 35, 50, 75, 80} X = =70 i = 0 j = 5 A[i] + A[j] = 10 + 80 = 90 Since A[i] + A[j] > X, j-- i = 0 j = 4 A[i] + A[j] = 10 + 75 = 85 Since A[i] + A[j] > X, j-- i = 0 j = 3 A[i] + A[j] = ..

1. vector of pairs vector 와 pair를 섞어 쓰는 방법이다. 연습이 필요하다 ㅠㅅㅜ 단순하게 생각하면서 익히자...! // C++ program to demonstrate vector of pairs ! #include #include using namespace std; bool sortbysecond(const pair &a, const pair &b) { return (a.second < b.second); } int main() { vector vec; int arr[] = {10,20,5,40}; int arr1[] = {30,60,20,50}; int n = sizeof(arr)/sizeof(arr[0]); for(int i =0; i < n; i++) { // assig..

* 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+..