ALGORITHM/OTHER (25) 썸네일형 리스트형 [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.. 2231 분해합, 7568 덩치, 1018 체스판 다시칠하기, 1436 영화감독 숌 단계별로 풀기 - 브루트포스 규칙을 찾지 않아도 되는 편안함..? 2231 분해합 #include #include #include #include using namespace std; int main(int argc, const char * argv[]) { int N; cin >> N; for (int i=1; i 14621 나만 안되는 연애 www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 트리(MST) 에서 남고-여고 조건이 추가된 문제 #include #include #include #include #include #include using namespace std; typedef pair pipii; int N, M, u, v, d, length = 0; bool check; int parent[1001]; char school[1001].. 12789 도키도키 간식드리미 https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 한 명씩만 설 수 있는 공간이 매우 스택을 쓰고싶게 생겨서 오랜만에 스택을 써서 구현 #include #include #include using namespace std; vector student; stack temp; int main() { int N, input, out = 1, i = 0; cin >> N; for (int i = 0; i > input; s.. 11585 속타는 저녁 메뉴 https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net KMP 알고리즘 문제 처음에 한칸한칸 모두 확인하니 75% 쯤에서 시간초과 발생 알고리즘 시간에 배운 KMP 알고리즘으로 해결해야 O(N+M) 시간으로 시간초과가 발생하지 않는다. 분명 머리로는 이해하고 납득했는데 코드가 이해가 안가서 한참 생각한 문제._. 푸는 방법을 글로 써내려가면, 환형 문자열의 문제들은 문자열을 두배해서 문제를 푸는 것이 일반적이라고 한다. 'I W A N T M E .. 이전 1 2 3 4 다음
