HTD

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net > 풀이 가장 최근의 파이프가 끝나는 지점과 방향을 기준으로 다음 탐색을 진행하는 DFS를 기반으로 코드를 작성하면 된다. 다만, 시간초과를 고려하여 DP를 이용한다. 짠 코드는 top-bottom 형식이며, DP는 다음과 같이 구성된다. DP[x][y][dir] 즉, DFS 함수의 파라메터를 그대로 사용한 것이다. #include #define ROW 0 #define ..

> Layouts - Add padding to recycler view so that you can see a part of the adjacent items. - In the item, set width to match_parent > Recycler view acting like view pager2 - Just use PagerSnapHelper snapHelper = PagerSnapHelper() snapHelper.attachToRecyclerView(YOUR_RECYCLER_VIEW) > Add button in last index of recycler view - Add 'add_button_item.xml' which contains: - Divide view holder into tw..

https://www.acmicpc.net/problem/1153 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. www.acmicpc.net > 접근 골드바흐의 추측을 이용한다. 2보다 큰 짝수는 두 개의 소수의 합으로 이루어질 수 있다. 입력값이 짝수이면 소수 두 개를 2, 2로 미리 정해두고, 홀수이면 2, 3으로 정해두어서 짝수를 만들어준다. 그렇게 남은 짝수를 두 개의 소수로 만들어주면 된다. 추가로 에라토스테네스의 채를 활용하여 시간복잡도를 줄였다. #include using namespace std; int N; bool isPrime[1000001]; vector pr..

https://www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 이 글은 Segment Tree의 Lazy Propagation을 배경으로 작성하였다. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-2 [Python] Laz..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net > 풀이 문제에 나와있는 설명을 그대로 구현하면 된다. 단, 주의할 점이 있는데, 얼음을 1씩 줄이는 작업을 할 때, 줄이는 조건을 체크하는 로직과 얼음을 줄이는 로직이 서로 영향을 주면 안 된다. 얼음이 '동시에' 녹아야 하기 때문이다. 나는 이것을 위해 toDecrease라는 좌표를 담는 vector에 줄이게 될 좌표들을 담은 뒤에 따로 처리하였다. #include usin..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net > 풀이 큰 틀은 최대 6개까지 있는 연산을 브루트포스 돌려서 최소값을 얻어오는 식이다. 예를 들어 연산이 3개가 있다고 하면, 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1와 같은 시퀸스의 모든 집합에 대해서 연산을 수행한다. 그 다음으로는 '배열 돌리기'를 구현만 하면 된다. 단, 백트래킹을 이용하므로 반시계방향 회전도 구현해야..

https://www.acmicpc.net/problem/11046 11046번: 팰린드롬?? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net > 풀이 Manacher's algorithm의 기본 활용 문제이다. 해당 알고리즘은 A라는 array를 완성시키는 것이 목적이며, A[i]에는 i 위치에서의 팰린드롬의 길이가 들어간다. 집합 S가 있고, 그 길이가 N이라고 할 때, 0~N-1 인덱스에 대해서 반복문을 돌아주게 된다. 반복문 안에서는 다음과 같은 3개의 steps가 진행된다. 1. A[i]의 초기값을 설정해준다. 이 때 'r'이라는 값이 쓰이는데 이것은 3번째 ste..

https://www.acmicpc.net/problem/10277 10277번: JuQueen The input contains a single test case. It starts with a line containing three integers C, N, and O, where C is the number of cores (1 ≤ C ≤ 4 587 520) to manage, N is the number of frequency steps for each core (1 ≤ N ≤ 10 000) and O is the number www.acmicpc.net > 들어가기 전에 해당 글은 Lazy Propagated Segment Tree를 밑바탕으로 하여 작성하였다. https://rccode.tis..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net > 풀이 트리를 체크하는 DFS 함수(setIsTree)를 짬으로써 해결할 수 있다. 방문한 적이 있는 노드에 방문한다는 것은 트리가 아니라는 것을 말해준다. 해당 조건을 만나더라도 DFS 함수를 끝까지 진행시켜서 isVisited가 올바른 정보를 담도록 해야한다. 이를 고려하여 global variable인 isTree의 값을 정해주는 식으로 설계하였다. #include usi..

https://www.acmicpc.net/problem/1960 1960번: 행렬만들기 첫째 줄에 n(1 ≤ n ≤ 500)이 주어진다. 다음 줄에는 각 행에 있는 1의 개수가 1행부터 n행까지 차례로 주어진다. 그 다음 줄에는 각 열에 있는 1의 개수가 1열부터 n열까지 차례로 주어진다. 행 또는 www.acmicpc.net > 접근 그리디하게 풀릴 수 있을 것이라고 직감하여 고안해낸 방법은 다음과 같은 순서를 따른다. 즉, 1. row 단위로 크게 돌면서, 2. 현재 채워넣어야할 1의 개수가 가장 많은 곳을 채워넣는 것이다. > 풀이 이것을 위해 우선순위큐를 이용한다. 우선순위큐(columnInfo)에는 (채워넣어야할 1의 개수, 해당 column의 인덱스)를 넣어준다. 이후에 row 단위로 for..