기록방

👉 문제링크 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 🔸 문제 분석 🔸 n개의 숫자의 합으로 m을 만들 수 있는 경우의 수를 출력한다. m은 3억이므로 int형으로 충분하다. n개의 수의 합이 m이 되는지 매번 더해서 확인하면 시간초과가 날 것이다. 따라서 미리 누적 합 리스트 sum를 만들어 둔다. 인덱스 i부터 인덱스 j 까지의 합은 sum[j] - sum[i] 로 구할 수 있다. sum[0]은 0이다. sum[j] - sum[i] > m이면, 계속 커지는 ..

👉 문제링크 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔸 문제 분석 🔸 입력받은 N개의 수를 오름차순으로 정렬했을때 K번재 수를 출력한다. N이 최대 5,000,000(5백만)이므로, O(nlogn)은 약 3천만이 나온다. 일반적인 정렬 알고리즘의 평균 시간 복잡도가 O(nlogn)이므로, 제한시간 2초안에 든다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java...

👉 문제링크 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(

👉 문제링크 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복 www.acmicpc.net 🔸 문제 분석 🔸 n개의 문자열에서 서로 비슷한 쌍의 수를 출력한다. 비슷하다는 의미는 문자열의 문자가 같은 방식으로만 변환 된 상태이다. 다른 두 문자가 하나의 문자로 중복되어 변환되지 못한다. 시간복잡도를 계산해보자 n개의 문자열이 갖을 수 있는 모든 쌍을 계산하므로 선택정렬과 같다. O(n^2) 그 안에서 문자열을 하나씩 검사해야한다. O(m) 따라서 시간 복잡도는 O(n^2 * m) 계산하면 100*100*50 == 500,000(5..

👉 문제링크 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 지그재그로 그린 배열에서 x번째 위치의 분수를 출력한다. 대각선으로 라인을 세었을때 짝,홀의 분자,분모 규칙이 반대이다. 🔸 코드 🔸 x = int(input()) line = 0 end = 0 while x > end: line += 1 end += line diff = end - x if line % 2 != 0: u = diff + 1 d = line - diff else: u = line - diff d = diff + 1 print(f'{u}/{d}') 🔸 코드 해석 🔸 line은 x가 해당하는 라인 번호이다. end는 x가 해당하는 라인의 끝 인덱스이다..