6epsilon의 등록된 링크

 6epsilon로 등록된 티스토리 포스트 수는 14건입니다.

백준 14458 소가 길을 건너간 이유 10 [내부링크]

https://www.acmicpc.net/problem/14458 14458번: 소가 길을 건너간 이유 10 소가 왜 길을 건너는지는 미해결 난제지만, 농부 존의 소들이 길을 자주 건넌다는 것은 잘 알려진 사실이다. 소들이 길을 건너는 일이 너무 잦아서 건너면서 부딪히는 일도 생기는데, 존은 이 상 www.acmicpc.net 초기 상태의 가로지르는 쌍은, inversion counting이므로 nlogn에 처리할 수 있다. 세그트리나 BIT, 또는 병합 정렬로 구현할 수 있다. 그러면 초기 상태가 아닌, k개를 옮긴 상황은 어떻게 생각해야 할까? 아이디어만 설명할 것이기 때문에, 편의상 왼쪽의 목초지는 1...N이라고 두자. 또, 마지막 n-k개를 옮기는 상황이나 처음의 k개를 옮기는 상황이나 같은데..

백준 6101 식당 [내부링크]

https://www.acmicpc.net/problem/6101 6101번: 식당 [1] [2] [3] [4] [5, 6] [7, 8, 9, 10, 11] [12] [13] 과 같이 묶으면, 1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11의 비용이 든다. www.acmicpc.net 먼저 DP를 하는데, DP[i]를 i번째까지를 적절히 그룹을 나눠서 얻을 수 있는 비용의 최소값이라고 가정하자. 그러면 DP[i]를 업데이트 할 때, j~i까지 음식의 종류가 k가지일 때 이것들을 하나의 그룹으로 만들어 DP[i]와 DP[j-1] + k^2 의 최소값으로 업데이트하면 된다. 그리고 이 k가 √n을 넘을 경우, 하나씩 그룹으로 나누는 것보다 손해이므로, O(n√n)짜리 풀이를 생각해 볼 수 있다..

백준 3321 가장 큰 직사각형 [내부링크]

https://www.acmicpc.net/problem/3321 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net n개의 행 각각에 대해 그 행을 밑변으로 하는 직사각형을 확인하면 된다. 각 행에서 각 위치에 대해 위로 연속한 1의 개수를 위 행에서의 값을 참조하여 O(m)만에 update할 수 있다. 대충 아래와 같은 그림을 생각해 보면 되겠다. 이 연속한 1의 개수를 내림차순으로 정렬하면, 그 행을 밑변으로 하는 직사각형 중 가장 큰걸 쉽게 확인할 수 있다. TC의 답을 나타낸 아래 그림과 같이, 내림차순인 히스토그램에서 가장 큰 직사각형을 구하는..

백준 20189 사탕 돌리기 [내부링크]

https://www.acmicpc.net/problem/20189 20189번: 사탕 돌리기 원기둥 형태의 뚜껑이 없는 깡통 N개가 원형으로 배열되어 있다. 각 깡통에는 시계 방향 순서대로 1번부터 N번까지의 자연수 번호가 붙어 있으며, 각 깡통에는 사탕이 K개씩 들어 있다. 따라서, www.acmicpc.net 제자리가 아닌 사탕이 있으면, 결국 그 사탕을 원래 자리로 옮겨줘야 하고, 그 과정을 잘 나누고 이어서 진행하면 문제가 해결될 것이라고 생각해 볼 수 있다. 특히 사탕을 옮겨 놓게 되면 그 위치는 사탕의 개수가 K+1개이므로, 제자리가 아닌 사탕이 있어 항상 그 자리에서 유의미한 이동을 이어 나갈 수 있음을 확인할 수 있다. 제자리에 가져다 놓은 사탕은 더 이상 이동할 일이 없다는 것이다. 한..

확장 유클리드 호제법의 재귀적 구현 [내부링크]

https://rebro.kr/97 PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법 [목차] 1. 유클리드 호제법 2. 확장 유클리드 호제법 3. 모듈러(modular) 연산에서의 곱셈의 역원 4. 예시 문제 1. 유클리드 호제법 유클리드 호제법은 정수론을 조금이라도 공부했다면, 혹은 공부하 rebro.kr 오랜만에 확장 유클리드가 필요해서 내용을 찾아봤는데, 위의 블로그의 코드를 찾게 되었다. 블로그 설명에서는 해당 코드를 완벽히 설명한거 같진 않아서 정리해 본다. 재귀적으로 작성하였는데, 그 부분을 설명해 보자면, \[gcd(a, b)=sb+t(a \% b)\] 를 만족한다고 두고, \[a\%b=a-(a/b)b\] 를 대입하면 \[gcd(a,b)=ta+\left\{s-t\left(a/b..

백준 9376 탈옥 [내부링크]

https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 먼저 1명이 탈출한다고 생각해보자. BFS를 통해 Flood Fill을 돌리는데, 지나온 문의 개수가 0개일때, 1개일때, ... 순서대로 방문하면 된다. 구현은 각각의 위치를 방문할 때 인접한 위치가 비어 있으면 현재 사용중인 큐에 넣고, 문이면 다음 큐에 넣어서 BFS를 돌리는 방식으로 하였다. 각각의 위치에 몇번째 큐에서 방문하였는지를 기록하면 된다. 필자는 귀찮아서 큐 10000개로 처리하였지만, 큐2..

백준 3653 영화 수집 [내부링크]

https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 값을 삭제하고 앞에 삽입하는 걸 시간 내에 잘 해결해야 한다. m+n짜리 0/1 배열이 있다고 생각하면 문제를 쉽게 해결할 수 있다. 처음에는 i번째 영화를 m+i번째 자리에 놓아 값을 1으로 둔다. 그 영화를 k번째로 고르면 영화를 맨 앞으로 옮기는데, 원래 위치의 값을 0으로 바꾸고 m-k를 1로 바꾸면 된다. 이렇게 하면 문제에서 요구하는 순서를 가지게 됨을 알 수 있다. 각각의 쿼리..

백준 5896 효율적으로 소 사기 [내부링크]

https://www.acmicpc.net/problem/5896 5896번: 효율적으로 소 사기 첫 번째 줄에 소 시장에 나온 소들의 마릿수 N(1 ≤ N ≤ 50,000), 농부 존이 가지고 있는 쿠폰의 개수 K(1 ≤ K ≤ N), 농부 존이 가지고 있는 돈 M(1 ≤ M ≤ 1014)이 주어진다. 다음 줄부터 Pi (1 ≤ Pi ≤ www.acmicpc.net 그리디한 접근법을 적용할 수 있는 문제이다. 간단히는 소의 숫자가 i+1인 경우의 최적해에서 고른 소가 i인 경우의 소를 항상 포함하기에 그리디한 접근이 가능하다고 보면 되겠다. k개의 소를 구매할 때까지는, 쿠폰을 사용한 가격 중 낮은 순서부터 고르는 것이 최적임은 자명하다. 그 이후에는 2가지 경우가 있는데, 하나는 남은 소들 중 쿠폰을..

백준 10265 MT [내부링크]

https://www.acmicpc.net/problem/10265 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net Solved.ac에서는 문제에 SCC태그를 달아놔서 쫄았는데, 풀어 보니 필요 없었다. P4라는 난이도도 부풀려진게 아닐까. 풀이로 넘어가서, 문제 상황만 보면 x_i를 데려가야 i를 데려갈 수 있기에, x_i에서 i로 간선을 연결하고 위상정렬을 하고 싶어진다. SCC가 있을 테니, 그걸 잘 처리하면 될 거 같다고 생각하게 된다. 이제 그래프의 형태를 관찰하면, In-degree가 하나니까 사이클이 하나 있고,..

백준 3090 차이를 최소로 [내부링크]

https://www.acmicpc.net/problem/3090 3090번: 차이를 최소로 각각의 테스트 케이스에 대해서, 점수는 (100×(S+1)/(D+1))/(데이터 개수) 점이다. 이때, D는 출력한 수열에서 인접한 수의 차이의 최댓값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게 www.acmicpc.net 재밌는 파라메트릭 문제다. k를 매개변수로 잡고 차이가 k보다 작거나 같도록 만들 수 있는지에 대해 파라메트릭 서치를 하면 된다. 그러면 k가 주어졌을 때 그 여부를 알아내는 알고리즘을 작성해야 하는데, 이는 다익스트라에서 아이디어를 구했다. 전부 우선순위 큐에 때려박고, 작은 지점부터 보면서 양쪽에 k보다 차이가 큰 지점이 있으면 그 지점을 낮춰 주고 Update하고 큐..

백준 7469 K번째 수 [내부링크]

https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net i,j,k가 주어지면 배열 a[i...j]에서 k번째로 작은 수를 찾아내는 쿼리를 처리해야 한다. 구간 쿼리를 처리해야되니까 segment tree를 만들고 싶은데, 해당 쿼리를 처리하려면 merge sort tree를 만들면 된다. 머지 소트 트리를 만들면, 쿼리가 주어졌을 때 a[i...j]에서 임의의 수 x보다 작거나 같은 수의 개수를 알 수 있다. 각각의 구간에서 이분 탐색을 하면 된다. 그러면..

백준 15972 물탱크 [내부링크]

https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net 2018년 당시 서브태스크만 긁었던 문제. 당시에 생각한 아이디어 자체는 맞았기에 쉽게 AC를 받을 수 있었다. 어느 한 칸의 물의 높이가 정해졌다고 생각하면, 그 칸보다 높은 인접한 칸을 따져 줄 때 크게 세 가지 경우가 있을 것이다. 두 칸 사이에 인접한 칸의 현재 상태보다 낮은 구멍이 없거나, 구멍이 두 칸의 높이 사이에 있거나, 구멍이 주어진 칸의 높이보다 낮은 경우이다. 첫번째 경우는..

백준 22348 헬기 착륙장 [내부링크]

https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 테스트 케이스가 1만개라고 주어졌기에, 전처리를 잘 해서 쿼리에서 소요되는 시간을 줄여야 한다. 문제에서 관찰해야 하는 사실은 헬기 착륙장을 만들었을 때 빨강 페인트와 파랑 페인트의 통 수의 합이 447가지 경우밖에 없다는 것이다. 1, 1+2, 1+2+3,...1+2+...+447. 448까지의 합이 100128이므로 이 이후는 따질 필요가 없겠다. 결국 각각 447가지 경우에 대해서 빨강 페인트의 통 수..

백준 1315 RPG [내부링크]

https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net STR, INT로 [1000][1000] DP를 하면 된다는 걸 쉽게 생각할 수 있다.각 지점에서 남는 포인트를 활용해서 각 지점에 가는게 가능한지 생각해 보자.