From the bottom

PS/Tip 검색 결과

해당 글 6건

[C++/STL] 부분 합 partial_sum( )

특정 구간의 합을 O(1)에 구하고 싶을 때, 부분 합(partial sum)을 미리 구해놓으면 가능하다. 부분 합은 다음과 같다. i 0 1 2 3 4 v 1 2 3 4 5 psum 1 3 6 10 15 자 이제 여기서 특정 구간의 합만 구하는 방법은..? 원하는 구간 [a-b] (psum[-1] = 0 이라고 가정) psum[b] - psum[a-1] 부분합은 for 문을 사용해서 O(n)의 시간으로 직접 구할 수도 있고 c++ 의 경우에는 STL을 사용할 수 있다. #include #include // for copy #include // for multiplies #include // for partial_sum #include // for vector using namespace std; int..

PS/Tip 2019. 8. 7. 09:34

[비트연산] 비트연산자 & 비트마스크

아주 쉬운 연습문제 : https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 풀이는 여기! 2019/08/06 - [PS/백준 문제풀이] - [백준 11723] 집합 [백준 11723] 집합 문제 : https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진.. hyeonnii.tistory.co..

PS/Tip 2019. 8. 6. 12:45

[C++/STL] string : find() 와 substr() 함수

string변수명.find() : 찾고자하는 문자열이 존재하면 처음 나타나는 위치를 리턴함. : 없으면 string::npos를 반환. ex) 1 2 3 4 5 6 7 8 9 10 11 12 string original = "ababacbbacba"; string want = "bac"; size_t idx = original.find(want); if(idx == string::npos){ cout Colored by Color Scripter 3번 인덱스에서부터 4글자를 출력해야 하므로 결과는 bacb가 출력된다.

PS/Tip 2019. 8. 1. 18:20

[C++/STL] string 자료형 공백 포함 문자열 입력받기

string str; 과 같은 string 자료형이 있으면 cin >> str로는 공백을 포함한 문자열을 입력받지 못한다. 문자열을 입력받기 위해 다음과 같이 사용하면 된다. getline(cin, 변수명); original은 다음과 같다. getline(, , ) 마지막 delimiter 인자를 이용해 엔터 이외의 입력으로 문자열을 그만 받을 수도 있다.

PS/Tip 2019. 8. 1. 18:06

완전이진트리(Complete Binary Tree)

무조건 왼쪽 자식부터 차곡차곡 삽입. 현재노드 인덱스가 i라면 => 부모노드 인덱스는 i/2 이다. 현재노드 인덱스가 i라면 => 왼쪽 자식노드 인덱스는 i*2 // 오른쪽 자식노드 인덱스는 i*2 + 1 이다.

PS/Tip 2019. 8. 1. 16:33

[C++/STL] 이분탐색

이분탐색은 반드시 이미 정렬되어 있는 배열을 기준으로 한다. 이분탐색의 시간복잡도 : O(logN) 헤더 파일 : #include bool binary_search(, , , ) : 이분 탐색을 시도 후 있으면 true, 없으면 false 반환. ex ) if(binary_search(v.begin(), v.end(), num)) 이런식으로 벡터안에 num 있는지 체크할 때 유용! Iterator lower_bound(, , , ) : 찾고자하는 값 이상이 처음 나타나는 곳의 iterator를 반환. iterator 대신 해당 index로 나타내기 원한다면 lower_bound(~~~~) - v.begin() 과 같이 처음 시작 iterator를 빼주면 된다. Iterator upper_bound(, ,..

PS/Tip 2019. 7. 31. 13:16