백준

백준 1035번 - 조각 움직이기

https://www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net # Approach) 전형적인 완전탐색 문제이다. 1) 보드의 처음 별모양의 위치를 벡터에 넣는다. 2) 그 순서대로 각 별모양이 어디로 이동할지 정하고 다음 별모양이 선택하도록 DFS탐색을 진행해준다. # Time Complexity) 시간복잡도는 $_{25}\mathrm{P}_{5}$ $ = 5!{25 \choose 5} $ $= 6,375,600 < 10^9 $ 으로 2초안에 충분히 탐색..

백준 및 코드포스

2021/6 - 백준 첫 시작(한달동안 기초문제들만 슬쩍봄) 2021/12 ~ 현재(2022/4/1기준) 백준 5개월, 푼 문제 420개, 플레티넘 2 20점 2021/2/8 codeforces 첫 시험 2021/4/1 기준 contest 9회 참여, 레이팅은 1484... 아직은 푸는 속도와 실수에 발목을 많이 잡히는 것 같다. virtual이 도움이 될까 싶은 마음에 안하고 있었는데 최근에 한번 쳐본 후로 생각이 바뀌어서 앞으로 virtual을 가끔씩 해보려고 한다. 2022/4/10 극심한 슬럼프 요새 문제들이 손에 잡히지 않고 글씨가 둥둥 떠다니는 느낌이다. 실수도 너무 많고, 실수를 한 문제를 디버깅하는게 너무나도 귀찮은 상태다. 대충 머리속으로 알고리즘을 생각한후 TLE가 날 것 같으면 sub..

백준 1395번 - 스위치

https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자. 해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Time Complexity) 업데이트를 진행할때 s~t구간의 스위치를 모두 토글해야한다. 각 원소를 하나하나 토글한다면 세그먼트 트리를 사용했을때 시간복잡도는최대 한번의 업데이트에 $O(log(n))$으로 전체의 쿼리에 ..

백준 3653번 - 영화 수집

https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자. 해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Point) DVD의 번호를 기준으로 세그먼트 트리를 만들면 로직이 꼬이기때문에 DVD 컬렉션상의 특정 위치의 DVD의 존재 유무를 기준으로 잡는 것이 좋다. DVD 하나를 빼서 맨 위로 올리는 것을 '액션'이라고 하자. 트리의 원본배열의 크기(구간합이 ..