그래프
#그래프 표현 개선 class Graph: def __init__(self,size): self.SIZE=size self.graph=[[0 for _ in range(size)] for i in range(size)]#2차원배열 # 전역변수 G1=None nameAry=['문별','솔라','휘인','쯔위','선미','화사'] 문별,솔라,휘인,쯔위,선미,화사 = 0,1,2,3,4,5 def printGraph(graph): print(' ',end=' ') for v in range(graph.SIZE): print(f'\t{nameAry[v]}', end=' ') print() for row in range(graph.SIZE): print(f'{nameAry[row]}',end=' ') for col in range(graph.SIZE): print(f'\t{graph.graph[row][col]}',end=' ') print() print() if __name__=='__main__': gSize=6 G1=Graph(gSize) G1.graph[문별][솔라]=1;G1.graph[문별][휘인]=1#한줄에 문장2개 넣고싶을때만 ; 사용 G1.graph[솔라][문별]=1;G1.graph[솔라][쯔위]=1 G1.graph[휘인][문별]=1;G1.graph[휘인][쯔위]=1 G1.graph[쯔위][솔라]=1;G1.graph[쯔위][휘인]=1;G1.graph[쯔위][선미]=1;G1.graph[쯔위][화사]=1 G1.graph[선미][쯔위]=1;G1.graph[선미][화사]=1 G1.graph[화사][쯔위]=1;G1.graph[화사][선미]=1 print('## G1 무방향 그래프 ##') printGraph(G1) --------------------출력--------------------- --------------------출력--------------------- ## G1 무방향 그래프 ## 문별 솔라 휘인 쯔위 선미 화사 문별 0 1 1 0 0 0 솔라 1 0 0 1 0 0 휘인 1 0 0 1 0 0 쯔위 0 1 1 0 1 1 선미 0 0 0 1 0 1 화사 0 0 0 1 1 0
DFS(깊이 우선 탐색)
# 깊이 우선 탐색 class Graph: def __init__(self,size): self.SIZE=size self.graph=[[0 for _ in range(size)] for i in range(size)]#2차원배열 G1=None stack=[] visitedAry=[] #방문한 정점 G1=Graph(4) G1.graph[0][2]=1;G1.graph[0][3]=1 G1.graph[1][2]=1 G1.graph[2][0]=1;G1.graph[2][1]=1;G1.graph[2][3]=1 G1.graph[3][0]=1;G1.graph[3][2]=1 print('##G1 무방향 그래프##') for item in G1.graph: print(item) current=0 # 시작 정점 stack.append(current) visitedAry.append(current) #스택, 방문기록 while(len(stack)!=0): next=None for vertex in range(4): if G1.graph[current][vertex]==1: if vertex in visitedAry : #방문한 적 있는 정점이면 탈락 pass else: #방문한적이 없으면 다음 정점으로 지정 next=vertex break if next!=None: # 다음 방문할 정점이 있으면 current=next stack.append(current) visitedAry.append(current) else: #다음 방문할 정점이 없으면 current=stack.pop() print('방문 순서 -->',end=' ') for i in visitedAry: print(chr(ord('A')+i),end=' ') --------------------출력--------------------- --------------------출력--------------------- ##G1 무방향 그래프## [0, 0, 1, 1] [0, 0, 1, 0] [1, 1, 0, 1] [1, 0, 1, 0] 방문 순서 --> A C B D--> 디버깅 하면서 이해 필요할듯
재귀호출(Recurvise Call)
count = 3 def openBox(): global count print('종이박스를 엽니다') count -=1 if count ==0 : print('반지 넣고 반환') return openBox()#openBox() 다시 호출 print('종이박스를 닫습니다') --------------------구분--------------------- openBox() --------------------출력--------------------- --------------------출력--------------------- 종이박스를 엽니다 종이박스를 엽니다 종이박스를 엽니다 반지 넣고 반환 종이박스를 닫습니다 종이박스를 닫습니다1) openBox()로 함수 호출
2) count=3인상태에서 들어가서 print 찍고 count->1감소/count=2
3) count!=0이기에 if문 건너뛰고 openBox()함수 재귀호출 <- openBox내부에서 재귀로 한번 호출
4) count=2로 들어가서 print 찍고 count 1 감소/count=1
5) count!=0이기에 if문 건너뛰고 openBox()함수 재귀호출 <- openBox내부에서 재귀로 두번호출
6) count=1로 들어가서 print 찍고 count 1 감소 /count=0
7) count=0 이기에 if문 실행, print찍고 return 만남
8) return 만나면 함수 호출한 곳으로 가기때문에 openBox()로 가서 바로 밑에 print 찍음
9) 재귀함수를 두번 호출했기에 return 만났을 때 호출한 openBox()의 위치로 두번 감
10) 따라서 출력문이 다음과 같이 엽니다/엽니다/엽니다/반환/닫습니다/닫습니다 의 형태로 출력
백준
백준 5597번 과제 안내신분?
num = [i for i in range(1,31)] for i in range(28): n=int(input()) num.remove(n) print(min(num)) print(max(num))1) 1~30 들어있는 리스트를 만들어놓고
2) 입력받을때마다 리스트에서 입력받은 값을 삭제
3) 시킨다는 생각을 왜 나는 하지 못하였을까
백준 3052번 나머지
arr=[] arr_rest=[] for i in range(10): n=int(input()) arr.append(n) arr_rest.append(arr[i]%42) print(len(set(arr_rest)))1) 비어있는 배열 2개 생성
2) 입력받으면서 바로 arr에 넣어주고
3) 입력받은 수를 42로 나눈 나머지 또한 arr_rest에 넣어줌
4) arr_rest를 set으로 집합형태로 바꾸면 중복되는 원소가 제거되고,
5) 이 집합의 길이를 구하면 결국 나머지의 개수가 나온다.
백준 8958번 OX 퀴즈
n=int(input()) for i in range(n): OxList=input()#그냥 문자열 score=0 #O만날때마다 1씩 증가 1,2,3 ... sum_score=0 #0만날때마다 증가된걸 계속더함 for n in OxList: if n=='O': #내가 입력한 문자열에서 'O' 만나면 score+=1 #score 1 증가 else: score=0 # 'X'만나면 0으로 초기화 sum_score+=score #score 증가시켜준걸 누적해서 더함 print(sum_score)--> 1시간정도 고민하며 풀어보다가 접근방식이 아예 잘못된 것 같아 구글링..
1) 퀴즈 o/x는 기본 문자열로 입력받고
2) 0 만날때마다 증가시킬 score와 증가시킨 score을 누적해서 합칠 sum_score 선언
3) 2중 for문 사용, 내가 입력한 문자열을 돌면서
4) 'O'를 만나면 score 1 증가 , 그 외는 score 0으로 초기화
5) 두번째 for문 내부에서 sum_score+=score로 누적해서 더함
