전공/알고리즘
-
백준 23327 (리그전 오브 레전드)전공/알고리즘 2021. 11. 4. 00:22
https://www.acmicpc.net/problem/23327 23327번: 리그전 오브 레전드 첫 번째 줄에 참가를 원하는 팀의 수 $N$($2 \le N \le 100 \, 000$), 후보 디비전의 개수 $Q$($1 \le Q \le 200 \, 000$)가 주어진다. 두 번째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. $a_i$는 $i$번째로 잘하는 www.acmicpc.net 어떤 쿼리가 주어질때 그게 만약 연속된 어떤 것을 구하는 거라면 그게 누적합으로 접근 할 수 있겠구나를 느꼈다. 머 사실 N, Q = 10^5이고, 1초인데 O(N*Q)는 불가능하니 O(Q)일텐데 먼가 전처리가 필요하겠구나 싶은 문제이다. 그래서 전처리를 해보자 전처리를 하기 전에 뚝딱 하다보면 ..
-
백준 23324 (어려운 모든 정점 쌍 최단거리)전공/알고리즘 2021. 11. 4. 00:09
https://www.acmicpc.net/problem/23324 23324번: 어려운 모든 정점 쌍 최단 거리 첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다. 다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$ www.acmicpc.net 매우 흥미로운 문제였다. 플로이드 와샬이라는 알고리즘을 지문에 제시해두고 그거 안되니깐 다른거로 풀어봐라 이런 것도 좋았고, 가중치 있는 간선이 딱 하나인 것도 좋았다. 물론 여러개의 간선에 가중치가 존재하게 된다면 문제는 완전 다른 문제가 되겠지만 관찰 문제이다. 만약 ..
-
백준 2357(최솟값과 최댓값)전공/알고리즘 2021. 9. 3. 13:51
https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 전형적인 세그먼트 트리 개념 문제 웃기게도 알고리즘 시작할 때 공부한 개념이었는데 묻어뒀다가 까먹어서 다시 공부 세그는 최대 N*4의 배열 크기가 필요 N개의 원소들이 주어지면 바텀업이 훨씬 편하다. 요정도? 그리고 최댓값 구할 때나 최솟값 구할 때 빈 공간 잘 찾아주기 그니깐 0으로 초기화 된 공간이 0이어도 괜찮은지 만약 최솟값을 찾는 거라면 0이 무조건 ..
-
백준 20974(Even More Odd Photos)전공/알고리즘 2021. 3. 27. 15:58
www.acmicpc.net/problem/20974 20974번: Even More Odd Photos In this example, one way to form the maximum number of five groups is as follows. Place 2 in the first group, 11 in the second group, 13 and 1 in the third group, 15 in the fourth group, and 17 and 3 in the fifth group. www.acmicpc.net N마리의 소가 있고, 소들 마다 숫자가 부여된다. 이 소들을 그룹할건데 숫자의 합이 짝, 홀, 짝, 홀로 반복되게끔 하는 그룹의 최댓값을 구하는 문제 우선 처음에는 짝부터 시작되는 것이..
-
백준 1915(가장 큰 정사각형)전공/알고리즘 2020. 12. 15. 17:28
www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이 문제도 Rebro님이 추천해주신 문제 10109 Troyangles랑 비슷한 유형의 2차원 dp문제이다. dp가 된다는 것을 알면 이제 남은건 간단하다 dp가 되는 규칙찾기 이 문제는 i,j가 정사각형의 맨왼쪽위로 설정한뒤에 앞선 문제와 동일한 방식으로 dp 테이블을 채워 나가면 된다. dp[i][j] = min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1]) +1 #include #include using namespace std; #define MAX 1..
-
백준 10109(Troyangles)전공/알고리즘 2020. 12. 15. 17:19
www.acmicpc.net/problem/10109 10109번: Troyangles Troy loves triangles. He especially likes counting triangles. He has an N-by-N grid consisting of either “.” or “#” characters. Help him count the number of triangles formed only by “#” characters in the grid. Triangles are of the form # # ### www.acmicpc.net Rebro님이 최근 코포와 동일한 문제가 있다고 해서 풀어보았다. * *** 이런식의 좌우 대칭이면서 i번째 높이에는 2i-1 갯수의 별이 존재하는 트리의 갯수..
-
백준 13430(합 구하기)전공/알고리즘 2020. 12. 8. 20:08
www.acmicpc.net/problem/13430 13430번: 합 구하기 첫째 줄에 k와 n이 주어진다. (1 ≤ k ≤ 50, 1 ≤ n ≤ 1,000,000,000) www.acmicpc.net 행렬의 점화식을 이용한 문제이다. 문제에 행렬의 점화식을 이용해서 풀라 이런 문구는 없어서 풀이방법을 찾아내기 어렵겠지만 아마도 이런 점화식이 주어진 문제를 보면 또 N이 엄청나게 큰 문제를 보면 행렬의 점화식을 떠올릴 수 있을 것 같기도 한 문제였다. 먼저 우리에게는 점화식이 주어진다. S(0,N) = N S(K,N) = S(K-1, 1) + ... + S(K-1, N) 여기서 내가 짚고 넘어갈 것은 N의 범위가 10억까지이다. 따라서 N은 엄청나게 크고, O(N)의 풀이는 안되고, O(logN)같은 ..
-
백준 2749 피보나치 수 3(피사노 주기)전공/알고리즘 2020. 11. 28. 12:58
www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net blog.naver.com/PostView.nhn?blogId=richard0326&logNo=221142014183&categoryNo=83&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView 피사노 주기(Pisano Period) 1) 설명 피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period... blog.naver.com 피보나치 수를 임의..