'컴퓨터 과학 > 자료구조' 카테고리의 다른 글
| [자료구조] 6. 동적 메모리 할당 (3) | 2018.12.12 |
|---|---|
| [자료구조] 5.포인터 (1) | 2018.12.12 |
| [자료구조] 4.구조체 (0) | 2018.12.11 |
| [자료구조] 3.배열 (0) | 2018.12.11 |
| [자료구조] 2. 순환 (1) | 2018.11.29 |
컴퓨터 과학
- [컴퓨터 과학 총론] 컴퓨터 과학 총론 2021.03.12
- [git] git으로 협업하기 - 시나리오 2021.03.12
- [git] github 기본 개념 및 사용법 2021.03.12
- [알고리즘] 5. 정렬 2020.06.22 1
- [알고리즘] 4. 탐색 2020.06.22
- [알고리즘] 3. 재귀 호출 2020.06.22
- [알고리즘] 2. 알고리즘 기초 2020.06.22
- [알고리즘] 1. 알고리즘이란 2020.06.09
[컴퓨터 과학 총론] 컴퓨터 과학 총론
2021. 3. 12. 14:47
[git] git으로 협업하기 - 시나리오
2021. 3. 12. 14:15
'컴퓨터 과학 > github' 카테고리의 다른 글
| [git] github 기본 개념 및 사용법 (0) | 2021.03.12 |
|---|
[git] github 기본 개념 및 사용법
2021. 3. 12. 13:35
1. Git과 GitHub
Git : 컴퓨터에 로컬로 설치하여 버전 제어를 처리하는 소프트웨어
-> 소스 코드 관리를 위한 분산 버전 관리 시스템
GitHub : Git을 호스팅해주는 웹 서비스 (개발자들의 페이스북)
Git 데이터를 저장하는 서버 -> Git 저장소 서버를 대신 유지 및 관리 해줌
(Git 저장소를 직접 설치하지 않고 GitHub를 통해 Git 사용가능)
2. Git 명령어
ppt 참고
'컴퓨터 과학 > github' 카테고리의 다른 글
| [git] git으로 협업하기 - 시나리오 (0) | 2021.03.12 |
|---|
[알고리즘] 5. 정렬
2020. 6. 22. 17:15
정렬 : 자료를 특정 순서대로 정렬하는 것
정렬의 종류 : 선택정렬, 삽입정렬, 병합정렬, 퀵정렬, 거품정렬
1. 선택정렬
선택정렬 : 리스트 중에 순서대로 선택해서 정렬시키기!
1) 선택정렬 알고리즘 (쉽게)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def find_min_idx(a):
n=len(a)
min_idx=0
for i in range(1,n):
if a[i]<a[min_idx]:
min_idx=i
return min_idx
def sel_sort(a):
result=[]
while a:
min_idx=find_min_idx(a)
Value = a.pop(min_idx)
result.append(Value)
return result
d=[2,4,5,1,3]
print(sel_sort(d))
|
cs |
2) 선택정렬 알고리즘 (일반)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
def sel_sort(a):
n=len(a)
for i in range(0,n-1):
min_idx = i
for j in range(i+1,n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx],a[i]
d=[2,4,5,1,3]
sel_sort(d)
print(d)
|
cs |
3) 알고리즘 분석
시간복잡도 = O(n^2)
2. 삽입정렬
삽입정렬 : 리스트를 하나하나 뽑아서 제자리로 정렬
1) 삽입정렬 알고리즘 (쉽게)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def find_ins(r,v):
for i in range(0,len(r)):
if v < r[i]:
return i
return len(r)
def ins_sort(a):
result=[]
while a:
value = a.pop(0)
ins_idx = find_ins(result,value)
result.insert(ins_idx,value)
return result
d=[2,4,5,1,3]
print(ins_sort(d))
|
cs |
2) 선택정렬 알고리즘 (일반)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def ins_sort(a):
n = len(a)
for i in range(1, n):
key = a[i]
j = i - 1
while j >= 0 and a[j] < key: # 부등호 방향 뒤집기
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)
|
cs |
3) 알고리즘 분석
시간복잡도 = O(n^2)
'컴퓨터 과학 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 4. 탐색 (0) | 2020.06.22 |
|---|---|
| [알고리즘] 3. 재귀 호출 (0) | 2020.06.22 |
| [알고리즘] 2. 알고리즘 기초 (0) | 2020.06.22 |
| [알고리즘] 1. 알고리즘이란 (0) | 2020.06.09 |
[알고리즘] 4. 탐색
2020. 6. 22. 16:15
1.순차탐색
순차탐색 : 리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색한다
1) 순차 탐색 알고리즘
리스트에서 특정값을 찾아서 해당 위치 번호를 반환
|
1
2
3
4
5
6
7
8
9
|
def search_list(a,x):
for i in range(0,len(a)):
if x == a[i]:
return i
return -1
v=[12,13,46,78,69]
print(search_list(v,46))
|
cs |
2) 알고리즘 분석
시간복잡도 = O(n)
연습문제
7-1.
|
1
2
3
4
5
6
7
8
9
|
def search_list(a,x):
answer=[]
for i in range(0,len(a)):
if x == a[i]:
answer.append(i)
return answer
v=[12,13,46,78,69,46]
print(search_list(v,46))
|
cs |
7-2. n
7-3.
|
1
2
3
4
5
6
7
8
9
10
|
def search_list(stu_no,stu_name,n):
for i in range(0,len(stu_no)):
if n == stu_no[i]:
return stu_name[i]
return '?'
stu_no=[39,14,67,105]
stu_name=["justin","john","mike","summer"]
print(search_list(stu_no,stu_name,39))
|
cs |
'컴퓨터 과학 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 5. 정렬 (1) | 2020.06.22 |
|---|---|
| [알고리즘] 3. 재귀 호출 (0) | 2020.06.22 |
| [알고리즘] 2. 알고리즘 기초 (0) | 2020.06.22 |
| [알고리즘] 1. 알고리즘이란 (0) | 2020.06.09 |
[알고리즘] 3. 재귀 호출
2020. 6. 22. 11:35
1. 팩토리얼 구하기
팩토리얼 알고리즘 : 1부터 n까지 연속한 정수의 곱 구하기
1) 팩토리얼 알고리즘 (재귀없이)
|
1
2
3
4
5
6
7
8
|
#1부터 n까지 곱하기
def fact(n):
f = 1
for i in range(1,n+1):
f = f*i
return f
print(fact(10))
|
cs |
2) 팩토리얼 알고리즘 (재귀)
재귀 호출 : 어떤 함수 안에서 자기 자신을 부르는 것
|
1
2
3
4
5
6
7
|
#1부터 n까지 곱하기
def fact(n):
if n <=1: #종료조건
return 1
return n*fact(n-1)
print(fact(10))
|
cs |
3) 알고리즘 분석
시간복잡도 = O(n)
2. 최대공약수 구하기
최대공약수 : 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값
1) 최대공약수 알고리즘
|
1
2
3
4
5
6
7
8
9
10
|
def gcd(a,b):
i = min(a,b)
while True:
if a % i ==0 and b%i==0:
return i
i = i-1
print(gcd(3,6))
|
cs |
2) 유클리드 알고리즘
유클리드 최대공약수 : 1. a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다.
-> gcd(a,b)=gcd(b,a%b)
2. 어떤 수와 0의 최대공약수는 자기자신이다. -> gcd(n,0)=n
|
1
2
3
4
5
6
7
8
|
def gcd(a,b):
if b==0:
return a
return gcd(b,a%b)
print(gcd(3,6))
|
cs |
3. 하노이의 탑 옮기기
1) 하노이의 탑 알고리즘
하노이의 탑 알고리즘 : 원반이 n개일 때 n-1개를 다른 기둥에 옮기는 것이 포인트!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# n = 옮기려는 원반의 개수
# from_pos = 옮길 원반이 현재 있는 출발점 기둥
# to_pos = 원반을 옮길 도착점 기둥
# aux_pos = 보조 기둥
def hanoi(n,from_pos, to_pos, aux_pos):
if n==1:
print(from_pos, "->", to_pos)
return
hanoi(n-1, from_pos,aux_pos,to_pos) #n-1개의 원반을 보조기둥으로
print(from_pos,"->",to_pos)
hanoi(n-1,aux_pos,to_pos,from_pos) #n-1개의 원반을 도착점 기둥으로
print("n=1")
hanoi(2,1,3,2)
|
cs |
2) 알고리즘 분석
시간복잡도 = O(2^n)
연습문제
4-1.
|
1
2
3
4
5
6
|
def sum(n):
if n <=1:
return 1
return n+sum(n-1)
print(sum(10))
|
cs |
4-2.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#처음에는 a[0]를 max로
#그뒤로 a[1],a[2]....비교하기
def find_max(a,n):
if n ==1:
return a[0] #max값 첫번째 값으로
max = find_max(a,n-1)
if max > a[n-1]:
return max
else:
return a[n-1]
a=[12,13,14,15,2]
print(find_max(a,5))
|
cs |
5-1.
|
1
2
3
4
5
6
7
8
|
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-2) + fibonacci(n-1)
print(fibonacci(5))
|
cs |
'컴퓨터 과학 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 5. 정렬 (1) | 2020.06.22 |
|---|---|
| [알고리즘] 4. 탐색 (0) | 2020.06.22 |
| [알고리즘] 2. 알고리즘 기초 (0) | 2020.06.22 |
| [알고리즘] 1. 알고리즘이란 (0) | 2020.06.09 |
[알고리즘] 2. 알고리즘 기초
2020. 6. 22. 09:53
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 |
[알고리즘] 1. 알고리즘이란
2020. 6. 9. 09:53
- 이 블로그 내의 알고리즘 내용은 모두의 파이썬 with 파이썬, 알고리즘 문제 해결전략 내용을 요약및 참고한 것입니다.
- 제가 이해한 대로 정리한 내용이기에 본문의 내용과 상이할 수 있습니다.
1. 알고리즘
알고리즘 : ‘어떤 문제를 풀기 위한 절차나 방법’
알고리즘 분석 : 알고리즘의 성능이나 특징을 분석하는 것
알고리즘의 특징 : 알고리즘의 각 단계는 구체적이고 명료해야됨
2. 계산 복잡도 표현
계산 복잡도: 알고리즘의 계산이 얼마나 복잡한지 나타낸 정도
O(1) : 입력 크기 n과 필요한 계산의 횟수가 무관( 입력 크기 커져도 계산 시간 늘어나지 않음)
'컴퓨터 과학 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 5. 정렬 (1) | 2020.06.22 |
|---|---|
| [알고리즘] 4. 탐색 (0) | 2020.06.22 |
| [알고리즘] 3. 재귀 호출 (0) | 2020.06.22 |
| [알고리즘] 2. 알고리즘 기초 (0) | 2020.06.22 |