Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 풀이 세그먼트트리를 이용하여 입력받은 X~Y의 구간합을 구한다음, A번째 숫자를 B로 교환을 Q번 진행한다. 세그먼트 트리를 제대로 구현을 했지만, 계속 틀렸습니다가 떠서 문제를 제대로 읽어보니, X>Y인 경우도 입력으로 주어진다는것을 알고, 저 경우 X와 Y를 교환해주었다. 그랬더니 정상적으로 돌아가겠지 했는데 시간초과가 떠서 잘 살펴봤는데, 로직상 문제가 없어서 ..

2021. 8. 16.

문제풀이/백준oj

https://www.acmicpc.net/problem/2268 2268번: 수들의 합 첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 www.acmicpc.net -풀이- 세그먼트트리의 기본적인 문제이다. 하지만 주의해야할점이 sum쿼리를 실행할때 i>j인 경우가 있으므로, 위와 같은 경우라면 i와 j를 swap해주어야한다. 또한 초기값이 모두 0이므로, 세그먼트트리를 초기화해주는 작업을 안해주어도 상관이없었다. -시간복잡도- sum과 modify 함수 모두 세그먼트트리의 쿼리이기 때문에 O(logN) 시간이 걸린다. 이 동작이 M번..

2021. 5. 19.