기본적인 배열을 통한 누적합은 구간합을 구하는 데 O(1)의 짧은 시간복잡도가 걸리지만 값이 변경됐을 때는 최대 N번을 통해 변경을 해야므로, 변경을 한 후 누적합을 구하는 시간복잡도는 O(N)이라고 할 수 있다. 하지만 세그먼트 트리를 구하면 O(lgN)만에 연산을 끝낼 수 있다 문제: https://www.acmicpc.net/problem/2042 깃허브주소: https://github.com/surinoel/boj/blob/master/2042.cpp

삼성 낚시왕과 유사한 시뮬레이션 문제지만 좀 더 어려운 문제라고 생각된다. 자료구조 선택이 중요한데 말의 순서를 위해서 앞과 뒤로 모두 데이터가 들어가기 때문에 덱을 이용했다. 말 순서대로 시뮬레이션을 했으며, 이동할 때마다 밑의 말이 바뀔 수 있으니 체크하는 것이 매우 중요하다 문제: https://www.acmicpc.net/problem/17780 깃허브주소: https://github.com/surinoel/boj/blob/master/17780.cpp

원판을 돌린다는 이유로 deque 자료구조를 이용했다. 그리고 이웃하는 수를 제거하는 과정은 bfs를 통해 각 노드들은 한 번만 접근하도록 했다. double 계산을 위해 합을 double로 선언했는데, 마지막에는 int로 선언해야 한다는 점을 망각해서 오류를 범했다 문제: https://www.acmicpc.net/problem/17822 깃허브주소: https://github.com/surinoel/boj/blob/master/17822.cpp

삼성전자 기출문제로, 경계선에 따라 구역을 나눌 수 있느냐를 물어보고 있다. 1. 모든 점들을 기준점으로 탐색한다 O(N^2) 2. 기준점을 기준으로 경계선의 꼭짓점이 맵 안에 존재하는지 확인한다 O(N^2) 3. 경계선이 성립이 된다면 그 구간을 그룹 5로 초기화한다 O(N) 4. 지도의 각 끝점에서 bfs를 돌리면서 구간선까지 탐색을 한다 O(N^2) 5. 최솟값을 구한다 O(상수) 위 시간복잡도는 나올 수 없다. 다만 계산을 편하게 하기 위해 다음과 같이 설정했고, 총 시간복잡도는 O = O(N^2)*O(N^2)*(O(N)+O(N^2)+O(상수)) = O(N^6) N제한이 20이므로 1억 이하므로 해결할 수 있다 문제: https://www.acmicpc.net/problem/17779 깃허브주소:..

벽을 부수는 옵션 이외에 낮과 밤을 두어 낮에만 벽을 부술 수 있는 옵션이 추가되었다. 따라서 좌표 이외에 벽을 부순 횟수와 낮과 밤을 구분할 수 있는 배열 요소를 추가해서 접근하도록 한다 1. 가만 있을 때 낮과 밤을 바꿔, 이동했는지 체크 2. 빈칸으로 이동할 때 낮과 밤을 바꿔, 이동했는지 체크 3. 벽으로 이동할 때 낮과 밤을 바꾸면서, 벽을 부술 수 있는지와 전에 이동했는지 체크 문제: https://www.acmicpc.net/problem/16933 깃허브주소: https://github.com/surinoel/boj/blob/master/16933.cpp

수학 문제로 분류되어 있지만, 작은 N을 고려했을 때 탐색 문제로 분류 된다 1. X인 점에 대해서 오른쪽으로 두 칸 이상 떨어졌는지 확인한다 2. 각 행과 열에 대해서 첫번째 X에 대해서는 왼쪽도 탐색하도록 한다 3. 짐이 없는 행과 열에 대해서도 따로 처리한다 문제: https://www.acmicpc.net/problem/1652 깃허브주소: https://github.com/surinoel/boj/blob/master/1652.cpp