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..
Koala - 5기
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 배..
문제 길이가 같은 두 단어가 주어졌을 때, 각 단어에 포함된 모든 글자의 알파벳 거리를 구하는 프로그램을 작성하시오. 두 글자 x와 y 사이의 알파벳 거리를 구하려면, 먼저 각 알파벳에 숫자를 할당해야 한다. 'A'=1, 'B' = 2, ..., 'Z' = 26. 그 다음 y ≥ x인 경우에는 y-x, y < x인 경우에는 (y+26) - x가 알파벳 거리가 된다. 예를 들어, 'B'와 'D' 사이의 거리는 4 - 2 = 2이고, 'D'와 'B' 사이의 거리는 (2+26) - 4 = 24이다. 입력 첫째 줄에 테스트 케이스의 수 (< 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 단어가 공백으로 구분되어져 있다. 단어의 길이는 4보다 크거나 같고, 20보다 작거나 같으며, 알파벳 ..
오늘은 백준 알고리즘 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/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 코드 n=int(input()) sum1=0 for i in range(n): x=list(input()) a=['one'] for i in (x): if i!=a[len(a)-1]: a.append(i) else: a.pop(len(a)-1) if len(a)==1: sum1+=1 print(sum1) 문제푼과정 스택을 이용하면 매우 쉽게 풀리는 문제인데 단어를 어떻게 짝짓는지 고민하다가 시간을 ..
