문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 해설 공유기의 갯수가 아니라 공유기가 설치되는 거리를 이분탐색으로 탐색하면 되는 문제였다. 완전탐색으로 할 경우엔 1부터 1000000000까지 가능하므로 시간초과가 나고 이분탐색으로 탐색시 logN이므로 시간안에 풀수있다. 공유기 거리가 늘어날수록 공유기 갯수가 줄어들므로 c보다 공유기 갯수가 적을때 거리(이분탐색하고자 하는 값)를 줄여가..
Koala - 5기/코딩테스트 준비 스터디
문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 해설 자른 종이안에 1, 0, -1 중 하나만 저장 되어 있는지 확인 하는 과정을 일일이 하면 시간 초과가 날까봐 어렵게 푼 문제이다.. (시간 복잡도 계산해보면 최악의 경우에도 가능) 구간합을 공부했던 것에 착안을 얻어 이차원 배열에서 d[i][j] = (1,1) ~ (i,j) 까지 -1,0,1의 개수를 저장해줬다 구조체를 사용했기 때문에 연산의 편의성을 위해 연산자 오버로딩을 ..
문제 링크 https://www.acmicpc.net/problem/2435 2435번: 기상청 인턴 신현수 첫째 줄에 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 주어진다. N은 온도를 측정한 전체 날짜의 수이다. N은 2이상, 100이하이다. K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사 www.acmicpc.net 풀이 입력받은 온도의 누적합(psum)을 구합니다. 온도를 측정한 날짜 N+1의 길이로 배열 psum을 만듭니다. (line 3) N+1인 이유는 첫째날이 포함되어 계산 시(left-1) 오류가 나지 않게 하기 위함입니다. (배열 맨 앞에 0을 추가) 반복문을 돌며 그 전날까지의 누적합과 해당 날짜의 온도를 더해줍니다. (line 5 ~ 6) 투 포인터를 이용..
문제링크 누적합을 이용한 문제 누적합이 뭐예요?? 리스트, 배열을 차곡차곡 누적하는 알고리즘이라고 보면 편할 듯하다. 문제 예제 입력 1 4 7 4 JIOJOIJ IOJOIJO JOIJOOI OOJJIJO 3 5 4 7 2 2 3 6 2 2 2 2 1 1 4 7 예제 출력 1 1 3 2 3 5 2 0 1 0 10 11 7 EX : (3,5) (4,7) 사이에 있는 J,I,O의 갯수를 출력 Solution 누적합을 저장할 osum,jsum,isum 배열을 맵 배열(arr)보다 1씩 크게 만들기 arr[i-1][j-1] == J 이면 jsum[i][j] +=1 하고 jsum[i][j] = jsum[i][j-1] + jsum[i-1][j] - jsum[i-1][j-1] + jsum[i][j] 더해준다. 전체소..
오늘은 백준 알고리즘 17179번 케이크 자르기 문제를 풀어보도록 하겠습니다. 문제부터 보겠습니다. 문제를 보시면 가장 작은 조각의 길이의 최댓값을 구하는 문제입니다. 탐색문제죠. 처음에 일반적으로 완전탐색을 고려합니다. 근데 범위를보니까 L이 400만이고 N이 1000입니다. 완전탐색으로 고려했을때 최소 40억의 연산이 필요하기 때문에 불가능하다는 사실을 알 수 있습니다. 연산의 수가 너무 크기때문에 이분탐색을 생각해보아야 합니다. 그래도 좀 까다로웠던 문제가 아닌가 싶습니다. 일단 저는 left = 0, right = l 로 잡고 mid = (left+right )/2로 했습니다. 여기서 mid는 가장작은 조각의 길이의 최대값이라고 가정하였습니다. 그리고 왼쪽부터 오른쪽으로 케이크를 자르도록 하였..
BOJ 17245번 서버실 Intro 처음에는 Python으로 풀었는데 80%대에서 시간 초과가 계속해서 났습니다. 더 이상 시간을 줄일 수 있는 곳이 보이질 않아서 동일한 코드를 Swift로 바꿔 풀었더니 시간 초과가 해결되었습니다. Solution 입력을 받으면서 가장 높은 높이와, 컴퓨터 개수의 총 합을 구합니다. 컴퓨터 개수의 총 합의 절반을 target으로 설정합니다. 이분 탐색을 통해 target 이상의 컴퓨터가 켜지는 최소 높이를 찾습니다. Code Swift import Foundation func count(_ mid: Int, _ coms: [[Int]]) -> Double { var count = 0 for com in coms { for c in com { count += min(c..
링크 https://www.acmicpc.net/problem/17951 17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야 시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다. www.acmicpc.net 풀이 과정 강의에서 설명했던 파라메트릭 서치 문제인 듯 하다. 이 문제를 통해서 이분 탐색을 어떻게 적용시켜서 문제를 해결할 지 감을 잡을 수 있게 됐다. 우선 그룹을 나눌 기준 점수가 mid이다. 이 기준값(mid)대로 나눴을 때 그룹의 수가 K개 이상이면 기준값이 작다는 뜻이므로 left를 mid + 1로 이동한다. K개 이하라면 기준값이 크다는 뜻이므로 right를 mid - 1로 이동한다. 최초의 right 값의 경우, 시험지..
https://www.acmicpc.net/problem/5549 5549번: 행성 탐사 상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 www.acmicpc.net 문제 풀이 n이라는 배열에 지도의 크기 M과 N을 각각 저장하고, qn에는 조사 영역의 개수를 입력받는다. 지도의 내용은 data배열에 저장하는데, 지역은 정글, 바다, 얼음으로 총 3 종류이므로 data배열과 크기가 같은 배열 jdata, odata, idata를 생성한다. data에 값을 입력받는 동시에 해당 위치의 영역이 J라면 jdata에, O라면 odata에, I라면 idata에 1을 입력..
https://www.acmicpc.net/problem/16713 16713번: Generic Queries 첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸 www.acmicpc.net 누적합(prefix sum)알고리즘을 사용해서 O(N)시간에 답을 구하는 것이 핵심인것 같습니다. 다만 더하기(+) 연산 대신 XOR(^) 연산을 사용해서 문제를 풀어야합니다. 전체적인 알고리즘 흐름은 "11659번: 구간 합 구하기4" 문제와 비슷합니다. 누적 XOR 배..
오늘은 백준 알고리즘 1644번 소수의 연속합문제에 대해 알아보도록 하겠습니다 문제부터 보겠습니다. 이 문제는 소수구하기 + 투포인터가 결합된 문제입니다. 개념이랑 기본코드만 알고있으면 쉽게 풀수 있는 문제입니다. 소수를 구하는 방법은 여러가지가 있겠지만 에라토스테네스의 체라는 방식을 이용하여 구현을 합니다. 왜냐하면 이 방법의 시간복잡도가 O(root(n))이기 때문입니다. 코드는 다음과 같습니다. #include #include #include #include using namespace std; vector a; int number; long long a1[4000001]; // 에라토스테네스의 체 void primeNumber(){ for (int i = 2; i
문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 사용해 n 보다 작거나 같은 소수들을 구합니다. (line 2~ line 8) 소수를 담을 배열 prime을 선언합니다. 배열 a는 소수가 아닌 수를 지우기 위해 사용됩니다. 2 ~ n 범위의 수 중에서 소수를 채택하고, 그 소수의 배수는 모두 지우게 됩니다. 투 포인터를 이용해 연속된 수열(소수)의 부분합을 구합니다. (line 9 ~ line 19) left, right의 초기 인덱스를 0,0으로 설정합니다. 우측 포인터를 가리키는 right의 인덱스가 소수를 담은 배열 pr..
링크 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 과정 투포인터로 풀면 O(n)시간 안에 풀리는 문제이다. 다만 유의해야할점은 4 4 1 5 2 2 와 같은 예시에서 5지점에서 포인터가 역전될수도 있으므로 단순히 high>=low를 반복조건으로 두면 틀리게 된다. 따라서 포인터가 역전당했을때 다시 포인터를 옮겨주거나, 혹은 조건에서 high>=low를 제거하면 된다. 코드 #include usi..
