안녕

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net _ = int(input()) # 필요 없음 N = list(map(int, input().split())) # 숫자들을 입력 받음 arr = [True] * (max(N) + 1) # True은 소수라는 뜻 arr[0] = arr[1] = False # False은 소수가 아님 for i in range(2, max(N) + 1): # 2부터 최고 숫자까지 에라토스테네스의 체를 계산함 if arr[i]: for j in range(i * 2, max(N) + 1,..

https://www.acmicpc.net/problem/1037 n = int(input()) # N의 진짜 약수의 개수 N = list(map(int, input().split())) # N이 진짜 약수 N.sort()# 오름차순으로 정렬 if n%2 == 1: # 약수의 개수가 홀수임 # 따라서 중간에 있는 값의 제곱이 원래 숫자 print(N[n//2]**2) else: # 약수의 개수가 짝수이므로, 맨 좌측과 맨 우측을 곱한 것이 원래 숫자 print(N[0] * N[-1])

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.04.16 - [Computer Science/알고리즘] - [알고리즘] 탐욕법이란? (What is the Greedy Approach?) [알고리즘] 탐욕법이란? (What is the Greedy Approach?) 1. 탐욕 알고리즘이란? 탐욕 알고리즘이란 각 순환마다 '가장 좋은' 선택을 합니다. 탐욕 알고리즘은 DP와 마찬가지로 최적화 문제를 푸는데 주로 사용됩니다. 또한 상대적으로 DP보다 알고리즘을 hi-guten-tag.tistory.com 2022.04.13 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 (Dynamic Programming) [알고리즘] 동적 계획법 (Dynamic Programming) ..

문제)

문제)

문제)

선택 문제란 키가 n개인 리스트에서 k번째로 큰 (혹은 k번째로 작은) 키를 찾는 것이다. 여기서 키는 정렬되어 있지 않은 리스트에 있다고 가정한다. 먼저 k = 1일 때, 우리는 가장 크거나, 가장 작은 키를 찾으면 된다. 그런 다음에, 최소키와 최대 키를 동시에 찾으면서 각각 따로 찾는 경우보다 더 적은 비교 횟수를 가짐을 볼 것이다. 마지막으로 k = 2일 때, 두 번째로 큰 값, 혹은 두 번째로 작은 값을 찾아볼 예정이다. 1. Finding the Largest Key problem : find the largest key in the array S of size n, indexed from 1 to n outputs : variable large, whose value is the larges..

문제를 푸는 알고리즘에 도전하는 방식은 두 가지가 있다. try to develop a more efficient algorithm for the problem try to prove that a more efficient algorithm is not possible 즉 알고리즘을 개선하던가, 아니면 더 효율적인 알고리즘은 만들 수 없다고 증명하던가 둘 중에 하나이다. 만약 더 효율적인 알고리즘을 만들 수 없다고 증명을 하면, 더 이상 알고리즘을 개선할 필요가 없다. 참고로 key의 comparison을 이용한 sorting algorithm은 nlgn보다 줄일 수 없다고 증명되었다. 1. Computational Complexity (계산 복잡도) 지금까지는 알고리즘의 복잡도를 계산했지만, 이 글에서..

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.05.26 - [Computer Science/알고리즘] - [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘) [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘) 1. BackTracking 이란? Backtracking is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion 즉, 되추적 기술은 특정 집합에서 주어진 기준에 대로 원소의 순 hi-guten-tag.tistory.com 1. Bran..

1. BackTracking 이란? Backtracking is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion 즉, 되추적 기술은 특정 집합에서 주어진 기준에 대로 원소의 순서를 정하는 문제를 푸는 데 사용됩니다. Backtracking은 modified depth-first-search(DFS)입니다. 일반적인 DFS와는 다르게 조금 변형된 구조를 가지고 있습니다. 지금은 Backtracking은 변형된 DFS라고 생각하고 preorder tree traversal을 한다고만 알고 있으면 될 것 같습니다. Backtr..