본문 바로가기

ALGORITHM

 (71)
[c++] 2042 구간 합 구하기 (세그먼트 트리) 세그먼트 트리 이해 https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 전체 코드 #include #include #include #include using namespace std; typedef long long ll; ll N, M, K, input, a, b, c; ll init(vector &arr, vector &tree, ll node, ll start, ll end..
[c++] 11723 집합 (비트마스크) https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스크에 대해 알아보자 & AND 비트가 모두 1이면 1 | OR 비트가 다르면 1 SHIFT (오른쪽) 비트를 오른쪽으로 이동 ^ XOR 비트가 다르면 1, 같으면 0 ~ NOT 비트를 반전 GOOD BIT 변수는 0으로 초기화하고 사용하자 시간 초과가 난다면 입출력 시간을 줄이자 전체코드 #include #include using namespace std; int M, num, bit; string input; int mai..
[c++] 1655 가운데를 말해요 (힙!) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 짭 중간값 구하는 문제 ! 시간 제한이 0.1초에 데이터의 삽입이 끊임없이 이뤄지므로 수행속도가 빠른 heap을 사용한다 max heap : 가장 큰 값이 top (기준 값보다 작은 값들을 나열, 기준 값 포함) 기준 값 ! min heap : 가장 작은 값이 top (기준 값보다 큰 값들을 나열, 기준 값 제외) 해서 중간값이 max heap 의 top에 위치하도록 한다. = m..
[c++] 11054 가장 긴 바이토닉 부분 수열 (이분탐색) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 앞에서부터 가장 긴 부분수열 사이즈 찾아서 배열에 넣고, 뒤에서부터 사이즈 찾아서 넣고 더한 값 중에서 가장 큰 값을 찾았다. 중복값이 만날 때 발생하니까 하나 빼주기 생각해보니 dp가 아니라 이분탐색으로 풀었다. lower_bound 찾아서 했으니 흠 🧐 전체 코드 #include #include #include using namespace std; int N, arr[1000], dp_bottomUp[1000],..
[c++] 2805 나무 자르기 (이분탐색) 파라메트릭 서치 ㅇㅅㅇ 오늘의 교훈 : unsigned 를 함부로 쓰지말자 -5 > 0 이 값이 true 로 나온다 또하나 그냥 long long 쓰자 ^^ 전체 코드 #include #include #include using namespace std; typedef long long ll; ll N, M, input; vector treeHeight; ll getTree(ll height) { ll res = 0; for (int i=0; i 0) { res += t; } } return res; } int main(int argc, const char * argv[]) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll start, en..
[c++] 1654 랜선 자르기 (파라메트릭 서치(Parametric Search)) 파라메트릭 서치(Parametric Search) 이진 탐색과 다르게 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘 (하다 보니 이진 탐색과 고냥 거의 똑같다._.) 자료형은 처음에 unsigned int로 했다가 더하면 overflow 날 것 같아서 그냥 unsigned long long으로 했는데. long long으로 다들 하더라카더라.. ㅇㅅㅇ 주의해야 할 것은 while문 안의 조건문에서 mid + 1, mid - 1을 넣어주었으니 while문 탈출 조건을 minLength > N; for (int i=0; i> input; lan.push_back(input); } sort(lan.begin(), l..
[c++] 14425 문자열 집합 - Trie (트라이), set, unordered_set set 과 unordered_set 으로 푸는것이 훨씬 간단한 문제. set 에 넣고 있는지 비교만 하면된다. #include #include #include #include using namespace std; int N, M, cnt; string input; unordered_set s; int main(int argc, const char * argv[]) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; for (int i=0; i> input; s.insert(input); } for (int i=0; i> input; if (s.find(input) != s.end()) { cnt++; } } cout > M; T..
2580 스도쿠 백트래킹 문제 처음에는 가로, 세로 , 3x3 네모칸 안에서 없는 숫자를 찾아서 넣으려고 했더니 런타임 에러가 떠서.. 1부터 9까지 넣어놓고 안되면 지우는 방식으로 고쳤다. 지금 생각해보니 없는 숫자를 배열로해서 찾고 포문을 돌리면 될거같은데.. 더 시간이 걸리려나 (isRowOK 를 두번써서 하루종일 왜틀렸는지 찾고있엇다ㅜㅜㅜ) #include #include #include using namespace std; typedef pair pii; int sudoku[9][9], zeroCount; vector zero; bool IsRowOK(int x, int num) { for (int i=0; i

티스토리툴바