본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 24266 알고리즘 수업 - 알고리즘의 수행 시간 5 (Swift) 문제 https://www.acmicpc.net/problem/24266 24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 문제의 알고리즘은 n에 따라서, 중첩된 for문이 $n^3$번 실행되므로, 빅오 표기법으로 $O(n^3)$ 입니다. 따라서 수행횟수는 $n^3$번, 최고차항의 차수는 3 입니다. ($n^3$) 소스코드 후기 시간 복잡도를 계산하는 방법에 대해 안다면 쉽게 풀 수 있는 문제입니다.
[BOJ] 백준 24265 알고리즘 수업 - 알고리즘의 수행 시간 4 (Swift) 문제 https://www.acmicpc.net/problem/24265 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 문제의 알고리즘은 n에 영향을 받아, 중첩된 for문이 약 $n^2$번 실행됩니다. 빅오 표기법으로 $O(n^2)$ 입니다. 수행횟수는 어떻게 될까요? 7을 예시로 들어보겠습니다. 첫 번째 for문에서는 1, 2, 3, 4, 5, 6 까지 실행되겠네요. 두 번째 for문에서는 첫 번째 for문이 1일 때, 6번 실행 (2, 3, 4, 5, 6, ..
[BOJ] 백준 24264 알고리즘 수업 - 알고리즘의 수행 시간 3 (Swift) 문제 https://www.acmicpc.net/problem/24264 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 문제의 알고리즘은 n에 따라서, 중첩된 for문이 $n^2$번 실행되므로, 빅오 표기법으로 $O(n^2)$ 입니다. 따라서 수행횟수는 $n^2$번, 최고차항의 차수는 2 입니다. ($n^2$) 소스코드 후기 시간복잡도를 계산하는 방법에 대해 안다면 쉽게 풀 수 있는 문제입니다.
[BOJ] 백준 24263 알고리즘 수업 - 알고리즘의 수행 시간 2 (Swift) 문제 https://www.acmicpc.net/problem/24263 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 문제의 알고리즘은 n에 따라서 for문이 n번 실행되므로, 빅오 표기법으로 $O(n)$ 입니다. 따라서 수행횟수는 n번, 최고차항의 차수는 1 입니다. ($n^1$) 소스코드 후기 시간복잡도를 계산하는 방법에 대해 안다면 쉽게 풀 수 있는 문제입니다.
[BOJ] 백준 24262 알고리즘 수업 - 알고리즘의 수행 시간 1 (Swift) 문제 https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 문제에 주어진 알고리즘의 수행시간은 빅오 표기법으로 $O(1)$ 입니다. n에 따라 수행시간이 전혀 변화가 없습니다. 따라서 수행횟수는 1 최고차항의 차수는 n이 존재하지 않기 때문에 0 입니다. 소스코드 후기 시간복잡도를 계산하는 방법을 알면 아주 쉬운 문제입니다.
[BOJ] 백준 9506 약수들의 합 (Swift) 문제 https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 풀이 먼저, 입력받은 n의 약수들을 구하는 로직을 작성해야 합니다. n을 1 ~ n까지 하나씩 나누어 떨어지는지 확인하면서, 약수를 구하는 방법이 있지만, 1 ~ $\sqrt{n}$까지 확인하는 방법이 더 빠릅니다. 예를 들어 18 이라는 수가 있다면, 1 * 18 2 * 9 3 * 6 6 * 3 9 * 2 18 * 1 과 같이 대칭을 이룹니다. $\sqrt{18}$은 약 4.2 입니..
[BOJ] 백준 2501 약수 구하기 (Swift) 문제 https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 풀이 n의 약수를 확인하는 방법중 1 ~ n 까지로 나누어서 나누어 떨어진다면 약수인 것으로 확인할 수 있습니다. 시간복잡도는 $O(n)$ 입니다. 더 빠르게 약수인 수를 판단할 수는 없을까요? 단순히 1부터 n의 제곱근 까지만 확인하는 방법이 있습니다. 1 ~ $\sqrt{n}$ 까지 수를 확인한 후, 나누어 떨어진다면 그 수가 약수일 것이고, n / i의 수도 약수일 것입니다. 예를 들어 20이란 수가 있다면, 20의 제곱근은 약 4.4로 1부터 4까지의 수를 ..
[BOJ] 백준 5086 배수와 약수 (Swift) 문제 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 풀이 첫번째 숫자를 두번째 숫자로 나눈 나머지가 0 이라면 첫번째 숫자가 두번째 숫자의 배수입니다. 두번째 숫자를 첫번째 숫자로 나눈 나머지가 0 이라면 첫번째 숫자가 두번째 숫자의 약수입니다. 둘다 아니라면, 약수와 배수가 모두 아닙니다. 단순히 조건문을 사용해서 풀이할 수 있습니다. 소스코드 후기 단순히 조건문 사용과, 배수와 약수의 성질에 대해 안다면 쉽게 풀 수 있는 문제입니다. 문제에도 힌트가 있어서 문제를 잘 읽으면 풀 수..
반응형

티스토리툴바