문제 링크 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/11880 11880번: 개미 승현이는 방학을 맞아 심심하지만, 공부는 하기 싫습니다. 이렇게 방 안에서 하루하루 시간을 낭비하던 중, 승현이는 자신의 직육면체 모양의 지우개에 개미 한 마리가 붙어 있다는 것을 알게 www.acmicpc.net 문제 코드 #include using namespace std; #include #define PI 3.141592653589793 #define ll long long int main(void) { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { ll a, b, c; cin >> a >> b >> c; ll big = max(a, b)..
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net n=int(input()) se=[] for i in range(n): sa=list(input().split()) se.append(sa) se.sort(key=lambda x:[-int(x[1]),int(x[2]),-int(x[3]),x[0]]) for i in range(n): print(se[i][0]) 문제푼과정 처음에는 여러개의 조건을 바탕으로 정렬할 방법이 대체 ..
https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문제 해석 한 단어를 입력받고 입력받은 단어의 접미사는 앞글자가 하나씩 줄은것이 된다. 이 접미사들을 사전순으로 정렬한 후 출력하는 문제이다. 코드 read = input() arr = [] for i in range(len(read)): arr.append(read[i:]) arr = sorted(arr) print("\n".join(arr)) 문제 풀이 read에 단어를 입력받는다. 접미사들을 저장하기 위해 arr 배열을 만들어준다. 앞부분이 하나씩 없어지므로 i가 0부터..
https://www.acmicpc.net/problem/5789 5789번: 한다 안한다 첫째 줄에는 테스트 케이스의 개수 N이 주어진다. (1 ≤ N ≤ 1000) 각 테스트 케이스는 한 줄로 이루어져 있으며, 0과 1로 이루어진 문자열이 주어진다. 문자열의 길이는 항상 짝수이고, 1000보다 작 www.acmicpc.net 문제분석 문제를 따라서 그대로 풀이하면 스택을 사용해야할 것 같지만 결국 마지막 원소만 비교하면 되기 때문에 단순히 마지막 문자열이 팰린드롬인지 아닌지만 판단하면 된다. 문자열로 받으라고 써있기는 하지만 팰린드롬인지를 판단하는 것이기 때문에 리스트로 받아도 무방하다. 코드 t = int(input()) for _ in range(t): n = list(input()) k = le..
링크 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을 입력..
엄청 많은 시도가 있었는데, 처음에 복잡하게 for문과 while 문 여러 개를 써서 구현했더니 시간초과 / 메모리초과가 계속 떴고, 이후 완전히 다르게 생각해 맞추었다. 일단 여기서 중력이 위에서 아래로 작용하기 때문에 이를 조금 손쉽게 처리하기 위해 list로 바꾸어 sort하려고 했다. a와 .은 문자열에서 sort시 '.'가 먼저고 'a'가 나중이기 때문에 그를 이용하였다. 그렇게 #가 나오기 전까지 .과 a를 하나의 list에 넣어 sort해주고 #는 그냥 넣어주는 식으로 구성한다. 이후 그림에 보이는 것처럼 꺼내주기 위해서 2차원을 1차원으로 압축시켜준 후 순서에 맞게 차례대로 print하였다. import sys sys.setrecursionlimit(100000) #중력 문제임!! N,M=..
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 배..
