1. 최댓값 찾기
최댓값 구하기 알고리즘 : 리스트 a에서 가장 큰 값 구하기
1) 리스트
리스트 : 정보 여러 개를 하나로 묶어 저장하고 관리할 수 있는 기능
| a = [1,2,3] | ||
| 함수 | 설명 | 예 |
| len(a) | 리스트 길이 구하기 | len(a) #3 |
| append(x) | x를 맨 뒤에 삽입 | a.append(4) # a = [1,2,3,4] |
| insert(i,x) | i위치에 x추가 | a.insert(0,0) # a = [0,1,2,3] |
| pop(i) | i번째 빼기, 빈칸시 마지막값 빼기 | a.pop() # a = [1,2] |
| clear() | 모두 지우기 | a.clear() # a = [] |
| x in a | x가 리스트 a에 존재하는지 확인 | 2 in a # True |
2) 최댓값 구하기 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#첫번째 값 기억
#두번째 값과 비교하여 큰 수 저장
def find_max(a):
max = a[0]
for i in range(1,len(a)):
if a[i] > max:
max=a[i]
return max
a = [17,92,18,33,58]
print(find_max(a))
|
cs |
3) 알고리즘 분석
시간복잡도 = O(n)
2. 동명이인 찾기
동명이인 찾기 알고리즘 : n명의 사람 중 같은 이름 찾아 집합으로 만들기
1) 집합
집합 : 정보를 여러 개 넣어서 보관가능, 리스트와 다르게 중복허용하지 않고 순서가 없음
| s = set() s = {1,2,3} |
||
| 함수 | 설명 | 예 |
| len(s) | 집합의 길이 구하기 | len(s) #3 |
| add(x) | 집합에 x 추가 | s.add(4) # s= {1,2,3,4} |
| discard(x) | x가 있으면 x 삭제 | s.discard(2) # s = {1,3} |
| clear() | 모두 지우기 | s.clear() # s = {} |
| x in s | x가 집합 s에 존재하는지 확인 | 3 in s #True |
2) 동명이인 찾는 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#첫번째 for문은 0~ n-1까지(마지막꺼는 안보기)
#두번째 for문은 끝까지 보기
#중복된 이름은 result에 넣기
def find_samename(a):
result = set()
for i in range(0,len(a)-1):
for j in range(i+1,len(a)):
if a[i]==a[j]:
result.add(a[i])
return result
a = ["A","B","C","A","B"]
print(find_samename(a))
|
cs |
3) 알고리즘 분석
시간복잡도 = O(n^2)
연습문제
3-1. 두 명씩 짝
|
1
2
3
4
5
6
7
8
9
10
|
def test_3_1(a):
result = set()
for i in range(0,len(a)-1):
for j in range(i+1,len(a)):
print(a[i],"-",a[j])
return result
a = ["A","B","C"]
print(test_3_1(a))
|
cs |
3-2. 시간복잡도 문제
A. 1
B. n
C. n^2
D. n^4
'컴퓨터 과학 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 5. 정렬 (1) | 2020.06.22 |
|---|---|
| [알고리즘] 4. 탐색 (0) | 2020.06.22 |
| [알고리즘] 3. 재귀 호출 (0) | 2020.06.22 |
| [알고리즘] 1. 알고리즘이란 (0) | 2020.06.09 |