04_cotest
12_탐색_선수내용_while_재귀_SQ
탐색 --> 최단거리
선수내용1. while 반복문!
# while은 조건 중심으로 반복을 하는 것!!!
- 특정 조건이 만족할 때 까지 롤링!!!!!
참고 : for ( 값/ 갯수 중심 )
while( 조건 중심!!!!)
--> 빠져나갈 조건에 대해서 값/ 조건상황!!!! 직접 본인이 설계!!!
**** 빠져나갈 구조적인 부분을 꼭!! 설계 해야 함!!!
# 예) 1부터 20까지 출력하자!!!!
====> for문 관점 : range(1,21,1) 롤링
for i in range(1,21,1):
print(i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# while 관점 : 조건 중심으로 바라봐야 함!!!
# m1) 값을 늘리는 방향으로 설계!!!!!
i = 1 # --> 출력을 위한 변수.
while i<21:
print(i)
i += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# m2) 다른 설계 방식 : 값을 줄이는 스타일로,,,
i = 20
while i>0:
print(21 - i)
i -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# m3) 명확하게 때려치자!!!!
i= 1
while True: # 주구장장 돌아가는 무한루프!!! ---> 제어문에서 break
print(i)
i+= 1
if i ==21:
break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# m4) 구조에 미묘한 차이에 따라서 조건 값, 구조가 다를 수 있음!!!
i= 1
while True: # 주구장장 돌아가는 무한루프!!! ---> 제어문에서 break
print(i)
if i ==20:
break
i+=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 정리 : for--> 주어진/필요한 값 중심 롤링!!
while --> 특정 조건이 만족할 때 까지 롤링!!!!
+++ 빠져나갈 조건 설계!!!!!
: 탐색, 최단거리..........
++++ pass, continue, break + if 같이 잘 사용해야 함!!!!
# 사전 내용2) 자료구조형 --> 스케줄링 Stack, Queue
기본적인 내용 : 값을 처리하는 방식!!!! ---> 스케줄러 사용방식!!!
===> 새롭게 해야할 일을 추가....
===> 한 것들은 지우거나/제거한다
Stack : 지하철 --> 제일 늦게 탄 사람이 제일 먼저 내린다!!!
Last In First Out : LIFO
비유 : 지하철의 출입!!!
==> 새로운 것 : 뒤로 쌓아둠 --> .append()
==> 처리할 것 : 맨 뒤에서부터 뽑아서 처리 --> .pop()
Queue : 놀이공원매표소 --> 제일 먼저 온 사람이 먼저 들어간다!!!!
First In First Out : FIFO
비유 : 놀이공원에서 매표소에서 처리하는 방식!!!!!!
==> 새로운 것 : 뒤로 쌓아둠 --> .append()
==> 처리할 것 : 맨 앞에서부터 뽑아서 처리 --> .pop()
a = [1,2,3,4,5]
a
[1,2,3,3,4,5]
a.append(7)
a.append(8)
a
[1,2,3,4,5,7,8]
# 할 일을 추출해서 해결 : ==> stack --> 맨 뒤부터 차출
a.pop()
8
a
[1,2,3,4,5,7]
a.pop()
[1,2,3,4,5]
# 큐
a.append(7)
a.append(8)
a
[1,2,3,4,5,7,8]
a.pop(0)
1
a
[2,3,4,5,7,8]
a.pop(0)
2
a
[3,4,5,7,8]
# 참고) 파이썬의 대표적인 자료형인 리스트로 큐를 구현!!!!
====> 파이썬의 언어 종특상 거의 속도 이슈가 걸림!!!!!!
이유 : 제일 앞의 있는 원소 pop(0)
--> 코테에서는 파이썬으로 queue를 하기 위해서는
무조건 deque 패키지를 불러서 사용하면 됨!!!
==> 코테에서 정규식처럼 거의 그냥 가져다 쓸 수 있는 패키지 중 하나1!!
** 해결책 : deque 패키지를 불러서 deque 자료형을 하면 됨!!!
[ ] ---> deque([])
참고 : 데이터를 처리할 떄 리스트보다 deque 속도가 빨라요!!!
# 사전 지식3 : 재귀 함수!!!!
==> 일반적인 코드, 데이터 분석에서 거의 사용하지 않는 스타일!!!
==> 코테에서는 종종~~~사용됨!!!! 무조건 알아야 함!!!
why?
구조적인 반복을 코드화 하기에 유용함!!!!!! --> 코테 코드가 심플!!!!
DP / DFS ==> 기능 중심으로 심플하게 코드!!!!!!
==> 구조적으로 뭔가 기능이 반복될 때!!!!!!!
# 참고) 파이썬에 재귀함수 limit 걸려있음!!!
# ===> whule 종료 조건을 설계!!!!!!!
def recursive_func():
print("재귀함수에요~~~~")
recursive_func()
recursive_func()
재귀함수에요~~~~
재귀함수에요~~~~
재귀함수에요~~~~
재귀함수에요~~~~
재귀함수에요~~~~
재귀함수에요~~~~
재귀함수에요~~~~
...
//RecursionError
# 재귀함수 예 ) 4!
# m1) 직접 계산하는 과정 : 4! = 4 * 3 * 2 * 1
# 1) for
n = 4
fact = 1
for i in range(1, n+1,1):
fact *= i
#print(i)
print(fact)
24
# 2) while
n = 4
fact = 1
cnt = 1 # <---- while 빠져나갈 기능적인 세팅!!!!
while cnt <= n:
fact *= cnt
cnt += 1 # <--- 종료를 위한 변수 & 필요한 동작.......
print(fact)
24
# 할 일 : 정의가 아니라 기능 중심으로 바라보자!!!
===> 점화식!!
n! = n* (n-1)! // a_n = n * a_n-1 ,1! =1
===> "기능 중심"의 규칙!!!!!!!
===> 바로 코드화!!!
def my_fact(n):
# 호출 되는 체크
print("My_Face호출"+ str(n))
if n<=1:
return 1 # 1! = 1
else:
return n * my_fact(n-1)
==> 기능적인 규칙성을 그냥 코드화 작업이 가능함!!!!
코드가 상당히 직관적으로 작성이 됨!!!!
==> 규칙성이 있는 것들에 대한 관계 중심으로 코드를 작성하는게 유용!!
퀵정렬, 탐색(dfs), dp, 규칙적인 부분 구현 : 코테용!!!
my_face(4)
My_Face호출4
My_Face호출3
My_Face호출2
My_Face호출1
24
# 재귀 함수 정리 : Stack처럼 처리를 한다!!!!
관점 : 기능 중심의 관계/규칙성을 간단한게 코드화!!!!
# 재귀 함수 : 자기 자신을 계속 호출하는 구조를 사용을 함!!!
해결의 순서는 맨 마지막에 호출된 친구부터
해결이 순차적으로 이루어져야 문제를 해결할 수 있음!!
==> DFS탐색은 Stack형식을 사용해서 탐색을 진행 Algo
DFS의 정의대로 구현 or 재귀함수로도 구현이 가능함!!!
==> BFS탐색은 Queue형식을 사용해서 탐색을 진행 Algo
BFS 정의대로 구현 but 재귀함수로 하면 XXX
파이썬에썬에서는 deque
# 사전 지식 4 : 그래프에 대한 코드화 작업
# 기본적인 대상 : 지도, 네트워크 ,연결성
==> 현실적인 현상/대상을 점/선을 추상화!!!!
==> 추상화 되어 있는 그래프들을 어떻게 "코드화"(코드로 표현 방식!!)
1) 행렬 방식으로 표현!!!
2) 리스트 방식으로 표현!!!!
# 탐색 문제 : 모든 경우들을 다 체크하는 문제!!
==> 수학적으로 모든 경우의 수를 푸는 문제*****
==> 지도가 있는 경우 좀 명확한 문제 유형!!!!
==> 그 외 : 평면, 미로, 다양한 유형......
===> 여러 유형의 문제들을 많이 풀고 / 유형 정리!!!!!******
( 왜 이 문제가 탐색의 문제인지 파악!!!!)
( 여러 탐색의 알고리즘 중에서 어떤 방식이 좋은가 선택!!!)
++++ 중간에 컷 : 백트레킹...
# 무한을 표현 : 연결이 없습니다!!!!
# 방법1) 그냥 엄청 큰 수를 직접 입력!!!
INF = 999999999999999999999999
# 방법2) 명시적으로 파이썬의 무한대 인식!!!! ****
INF = float("inf")
INF
int
m = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
m
[[0, 7, 5], [7, 0, inf], [5, inf, 0]]
# =--> 0번 도시에서 1번 도시 연결되었나요?
m[0][1]
7
# =--> 2번 도시에서 1번 도시 연결되었나요?
m[2][1]
inf
==> 행렬로 표현을 한다면 : 가로줄 --> srtart : 지도[인덱스]
세로줄 --> end : 지도[st][end]
==> 쌩파이썬의 입장에서 지도를 표현하는 인접행렬방식으로
:지도[출발점][종료점]
cf) 명시적인 2차원 numpy array, pandas DF, tensor : 다른패키지
: 지도[출발점, 종료점]
# 인접 리스트 방식 : 연결성만 바라보고 구성--> 컴팩트하게!!!
# --> 인접리스트를 코드화 : 리스트 활용!!!!
g_1 = [
[(1,7), (2,5)], # --> 0번 도시의 연결 리스트
[(0,7)], # --> 1번 도시의 연결 리스트
[(0,5)] # --> 2번 도시의 연결 리스트
]
g_1
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
==> 0번 도시하고,1번 도시가 연결이 되어 있나요??????? 얼마인가요?
g_1[0][0][1]
==> 구체적인 연결성에 대한 질문에 있어서는 직접 탐색!!!
행렬로 표현하는 방식보다는 직관성이 떨어질 수 있음!!!!!
7
# 인접리스트방식으로 코드화 : Dict
g_dict = {
"0":[ ("1",7), ("2",5)],
"1":[("0",7)],
"2":[("0",5)]
}
g_dict
{'0': [('1', 7), ('2', 5)], '1': [('0', 7)], '2': [('0', 5)]}
# ==> 0번도시에서 1번 도시가 연결되었나요????
g_dict["0"][0][1]
# --> 연결이 엄청 많고, 도시도 엄청 많다면,,,,, Dict 빠르지 않을까...
7
# 참고) 인접리스트 방식으로 리스트 자료형으로 코드화!!!!!
==> 0번 도시가 없을 수 있음!!!!
실제 문제 상 도시는 1~3번까지
: 1-->0, 2-->1, 3--->2
==> 가상의 0번도시를 있다고 가정하고 많이 함!!!!!!
g_2 = [
[], # --> 가상의 0번 도시를 세팅!!!!
[(2,7),(3,5)], # --> 1번 도시의 연결 리스트업
[(1,7)], # --> 2번 도시의 연결 리스트업
[(1,5)] # --> 3번 도시의 연결 리스트업!!!
]
g_2
[[], [(2, 7), (3, 5)], [(1, 7)], [(1, 5)]]
g_1[1-1]
[(1, 7), (2, 5)]
g_2[1]
[(2, 7), (3, 5)]
13_DFS
# DFS 예제 !!
0) 탐색을 지도에서 해야하므로 --> 지도를 코드화!!!!
==> 인접리스트 방식 표현을 하자!!!!
1) 파이썬 리스트 vs 2) 파이썬 Dict
---> 선택 : 파이썬 리스트!!!!!!
1번 도시부터네;;;
graph_list = [
[], # <--- 가상의 0번 도시가 있따고 가정,
[2,3,8], # <--- 1번 도시의 연결된 도시(직접)
[1,7],
....
...
....
...
]
*** 기본 코테의 앞에 유형에 대한 연습!!
--> 재귀 함수
--> S/Q
--> 지도에 대한 표현!!
==> 20일(세미나), 수업!!
*** 퇴실 버튼 체크!!
'ASAC 빅데이터 분석가 7기 > ASAC 일일 기록' 카테고리의 다른 글
| ASAC 빅데이터 분석가 과정 8일차 - 2 (24.12.13) (3) | 2024.12.13 |
|---|---|
| ASAC 빅데이터 분석가 과정 8일차 - 1 (24.12.13) (2) | 2024.12.13 |
| ASAC 빅데이터 분석가 과정 7일차 - 1 (24.12.12) (0) | 2024.12.12 |
| ASAC 빅데이터 분석가 과정 6일차 - 2 (24.12.11) (1) | 2024.12.11 |
| ASAC 빅데이터 분석가 과정 6일차 - 1 (24.12.11) (0) | 2024.12.11 |