분류 전체보기150 1743 음식물 피하기 (C++) 역시 시험기간에는 생각 없이 PS 하는 순간이 가장 즐겁다 풀이 이차원 bool 배열에 입력으로 들어오는 부분을 true로 바꾸어주고 이후 기본적인 bfs를 사용해 가장 큰 인접한 쓰레기들을 찾는다 + 풀고 나니 드는 생각인데 vis 배열과 ar 배열을 합쳐서 풀 수 있을 것 같다. 시간 복잡도 : $O(n*m)$ 소요 시간 : 3분 아쉬운 점 : class 6 문제 풀다가 어려워서 여기로 도망 왔다 전체적인 감상 : 처음 bfs 구현 연습할 때 풀기 좋은 문제인 것 같다. /* basic setup {{{ */ #include #define ff first #define ss second #define pb push_back #define sz(x) ((int)x.size()) #define all(x.. 2022. 10. 11. 2670 연속부분최대곱 (C++) 잘 알아두어야 하는 dp 문제 풀이 이전의 정보가 앞으로 쓸모 있을 때만 사용해주는 방법을 사용한다. 해당 경우를 누적시키며 진행하면 답을 구할 수 있다. 시간 복잡도 : $O(n)$ 소요 시간 : 측정 불가 아쉬운 점 : 분명 쉬운 문제인데 풀이 떠올리는 게 쉽지 않더라.. 전체적인 감상 : 이정도는 당연하다는 듯이 알고 있어야 한다 고! 생각한다. #include #define fast_io ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; double ar[10010], ans = 0; int main(){ fast_io; int n; cin>>n; for(int i=0;i>ar[i]; ans = ar[0]; for(i.. 2022. 10. 10. 3653 영화 수집 (C++) 처음 보는 느낌의 segment tree 문제이다 재미있었다. 풀이 기본적인 segmet tree를 n+m개의 leaf node가 존재하게 선언한다. 처음에는 뒤의 n개 노드에만 1을 표시에 넣어준다 입력을 받을 때마다 새로운 id를 부여해주고 segment tree의 기존 위치에는 -1을 새 위치에는 1을 update 해준다 m이 충분히 작아서 여유공간을 만들어주고 활용할 수 있다는 점이 인상적인 문제이다. 시간 복잡도 : $O(m \log(n+m))$ 소요 시간 : 측정 불가 아쉬운 점 앞으로 맞이하게 될 문제들에 다양한 종류의 segment tree가 많을 건데 이번 문제에서는 처음 보는 형태라고 잘 알아차리지 못해 아쉽다. 전체적인 감상 구현에 직관적이고 흥미로운 아이디어들이 사용되어 재미있는 문.. 2022. 10. 9. 13241 최소공배수 (C++) 문제의 풀이가 말 그대로인 문제이다. 풀이 입력 a, b를 받았을 때 말 그대로 a와 b의 최소공배수를 출력해주는 문제이다. a와 b의 최소공배수는 a * b / (a와 b의 최대공약수)와 같다. 시간 복잡도 : $O(\log (a+b))$ 소요 시간 : 2분 아쉬운 점 원래 basic setup에서 코드 짧게 하겠다고 위에 쭉 지워서 제출했더니 컴파일 에러를 몇 번 받았다. 전체적인 감상 간만의 실버 5 기본 구현 문제였다. 간단하고 재밌다. #include using namespace std; typedef long long ll; ll a, b; ll gcd(ll f, ll s){ if(s == 0) return f; return gcd(s, f%s); } int main(){ cin>>a>>b; .. 2022. 10. 8. 7578 공장 (C++) 처음 문제를 읽고 세그먼트 트리 문제인지 바로 감을 잡지 못해 고민을 많이 하였다. 풀이 해당 문제는 A열에서 먼저 나왔는데 B 열에는 나중에 위치해있는 기계의 쌍을 찾는 문제이다. 주어진 n 순서대로 진행을 해주며 A열에서 자신보다 먼저 나온 기계의 번호가 B열에서 자신과 매칭 되는 기계 뒤에 몇 개나 있는지 구간합을 구해주는 것이다. 이를 segment tree를 통해서 처리해줄 수 있다. 정답을 받고 난 이후로 unordered_map이 아닌 그냥 int 배열을 통해 라벨링을 다시 하는 과정을 해주었는데 확실히 더 빠른 모습을 볼 수 있었다. 시간 복잡도 : $O(n \log n)$ 소요 시간 : 하루 아쉬운 점 segment tree를 통해 쉽게 해결해줄 수 있는 문제임을 금방 알았으면 좋았을것을.. 2022. 10. 7. 이전 1 ··· 23 24 25 26 27 28 29 30 다음
