Algorithm
코드를 탐구합니다.
-
* 교재 "쉽게 배우는 알고리즘"을 기준으로 알고리즘 수업에서 배운 내용을 정리하는 글입니다. 점근적 표기법이란 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다. 대표적으로 상한(O), 하한(Ω), 차수(Θ)가 있다. 교재에는 o(리틀오) ω(리틀 오메가) 표기법도 나와있다. O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합 O-표기법 빅오 표기법은 점근적 상한으로 볼 수 있으며, g(n) ∈ O(f(n))일 때, f(n)이 g(n)의 상한이 된다. 주어진 복잡도함수 f(n..
[알고리즘] 점근적 표기법 - 상한 하한 차수* 교재 "쉽게 배우는 알고리즘"을 기준으로 알고리즘 수업에서 배운 내용을 정리하는 글입니다. 점근적 표기법이란 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다. 대표적으로 상한(O), 하한(Ω), 차수(Θ)가 있다. 교재에는 o(리틀오) ω(리틀 오메가) 표기법도 나와있다. O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합 O-표기법 빅오 표기법은 점근적 상한으로 볼 수 있으며, g(n) ∈ O(f(n))일 때, f(n)이 g(n)의 상한이 된다. 주어진 복잡도함수 f(n..
2023.10.11 -
소수를 구하는 문제였다. 풀이 def isPrime(data): cnt = 0 for i in data: for j in range(2, i + 1): if i % j == 0: if j == i: cnt += 1 break print(cnt) n = int(input()) data = list(map(int, input().split())) isPrime(data) 위에서 사용한 코드의 설명을 들어보겠다. 예를 들어 3이라면 (입력값 = 1 \n 3) i = 3 j = 2(에서 4까지 증가) 만약 i % j 가 나누어떨어진다면, i 와 j 가 같은지 비교, 같다면 카운트 증가(= 소수이다) 이므로 3일경우 3 % 3이 될 때 3 == 3이므로 카운트는 증가할 것이다. 트러블 슈팅 (해결) 처음에 데이터..
[백준] 1978: 소수 찾기소수를 구하는 문제였다. 풀이 def isPrime(data): cnt = 0 for i in data: for j in range(2, i + 1): if i % j == 0: if j == i: cnt += 1 break print(cnt) n = int(input()) data = list(map(int, input().split())) isPrime(data) 위에서 사용한 코드의 설명을 들어보겠다. 예를 들어 3이라면 (입력값 = 1 \n 3) i = 3 j = 2(에서 4까지 증가) 만약 i % j 가 나누어떨어진다면, i 와 j 가 같은지 비교, 같다면 카운트 증가(= 소수이다) 이므로 3일경우 3 % 3이 될 때 3 == 3이므로 카운트는 증가할 것이다. 트러블 슈팅 (해결) 처음에 데이터..
2023.10.11 -
일단 문제 이해를 못했었다.. N이 2이 2일때 약수를 더했는데 어떻게 4가 나오지...? 이러고 있었다가 10에서 함수를 사용해 대입해보니, g(10) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) + f(8) + f(9) + f(10) g(10) = 1 + 3 + 4 + 7 + 6 + 12 + 8 + 15 + 13 + 18 g(10) = 87 이 도출되었다. 처음에 이렇게 했다가O(n^2) 이라 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 이 조건을 만족하지 못해서 a = int(input()) ans = 0 for i in range(1, a+1): for j in range(1, a+1): if i % j == 0: ans += j ..
[백준] 17427: 약수의 합 2일단 문제 이해를 못했었다.. N이 2이 2일때 약수를 더했는데 어떻게 4가 나오지...? 이러고 있었다가 10에서 함수를 사용해 대입해보니, g(10) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) + f(8) + f(9) + f(10) g(10) = 1 + 3 + 4 + 7 + 6 + 12 + 8 + 15 + 13 + 18 g(10) = 87 이 도출되었다. 처음에 이렇게 했다가O(n^2) 이라 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 이 조건을 만족하지 못해서 a = int(input()) ans = 0 for i in range(1, a+1): for j in range(1, a+1): if i % j == 0: ans += j ..
2023.10.01 -
7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 내 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int[] rank = new int[num]; int[] w_list = new int[num]; int[] h_list = new int[num]; for (int i = 0; i < n..
[백준] 7568: 덩치7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 내 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int[] rank = new int[num]; int[] w_list = new int[num]; int[] h_list = new int[num]; for (int i = 0; i < n..
2023.07.15 -
1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 내 코드 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int max = sc.nextInt(); int result = 0; ArrayList list = new ArrayL..
[백준] 2798: 블랙잭1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 내 코드 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int max = sc.nextInt(); int result = 0; ArrayList list = new ArrayL..
2023.07.15