본문 바로가기

programming study/Algorithm

 (275)
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (23)(2021.2.16) 본 내용은 해당 강의 토대로 작성 1. 최대 점수 구하기(DFS) 문제 해설 부분집합 문제를 푸는 경우, 안 푸는 경우로 나누기 최대 점수가 나오면 갱신 문제 풀이 def DFS(score, time, s): global maxScore; if time > m: # 시간초과한 경우 중단 return; else: if maxScore < score: maxScore = score; for i in range(s, n): DFS(score + p[i][0], time + p[i][1], i + 1); # 푼 경우 DFS(score, time, i + 1); # 풀지 않은 경우 if __name__ == "__main__": n, m = map(int, input().split()); # 문제의 개수, 제한 ..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (22)(2021.2.15) 본 내용은 해당 강의 토대로 작성 1. 조합 구하기(DFS) 매우 중요! 문제 해설 매개변수를 두 개로 할 것 D(L, s) s : 가지가 뻗기 시작하는 번호 문제 답안 def DFS(L, s): global cnt; if L == m: for j in range(L): print(res[j], end=" "); cnt +=1; print(); else: for i in range(s, n + 1): res[L] = i; DFS(L + 1, i + 1); if __name__ == "__main__": n, m = map(int, input().split()); res = [0] * (n + 1); # 조합을 넣을 리스트 cnt = 0; # 카운트 DFS(0, 1); print(cnt); DFS를 호출하..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (21)(2021.2.14) 본 내용은 해당 강의 토대로 작성 1 . 순열 구하기 문제 해설 체크리스트 만들기 중복 순열 방지 DFS함수 호출의 밑 지점 : 명령을 하고 난 후 적용한다. 문제 풀이 def DFS(L): global cnt; # 글로벌 변수 if L == m: # 종료 for i in range(m): print(a[i], end = " "); print(); cnt += 1; return; else: for i in range(1, n + 1): # 순열 만들기 if ch[i] == 0: ch[i] = 1; a[L] = i; DFS(L + 1); ch[i] = 0; if __name__ == "__main__": n, m = map(int, input().split()); a = [0] * m; ch = [0] *..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (20)(2021.2.12) 본 내용은 해당 강의 토대로 작성 1. 바둑이 승차(DFS, Cut Edge Tech) 나의 전략 주어진 바둑이의 무게들을 리스트로 정리 상태 트리를 사용하여 각각의 무게를 더한 경우와 안 더한 경우를 나눈다. DFS 재귀함수의 첫 번째 인자는 레벨, 두 번째 인자는 더한 무게를 기록 탐색 완료 후 별도의 리스트에 무게를 append max 함수를 사용하여 구한 무게 중 최댓값 출력 문제 풀이 c, n = map(int, input().split()); b = []; # 바둑이의 무게 리스트 for _ in range(n): # 바둑이 무게를 입력 받기 b.append(int(input())); wList = [] # 바둑이를 실을 수 있는 무게 리스트 def DFS(L, w): if w > c: # 허..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (19)(2021.2.11) 본 내용은 해당 강의 토대로 작성 전역변수와 지역변수 정수 자료형인 경우 def DFS1(): print(cnt); # 5 출력 def DFS2(): cnt = 3; # 지역변수 생성 print(cnt); # 3 출력 def DFS3(): if cnt == 5: # error cnt = cnt + 1; # 지역변수 생성, cnt에 1을 더해야하는데, 이 시점에서는 cnt가 없음 print(cnt); def DFS4(): global cnt; # cnt는 전역변수라고 선언 if cnt == 5: cnt = cnt + 1; print(cnt); # 6 출력 if __name__=="__main__": cnt = 5; # 전역변수 DFS1(); DFS2(); DFS3(); DFS4(); print(cnt); ..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (18)(2021.2.11) 본 내용은 해당 강의 토대로 작성 이진트리 순회(깊이우선탐색) 아래와 같은 노드가 있을 때, 전위순회, 중위순회, 후위순회를 해보기 0 레벨 : 1 왼쪽 서브 트리 : 2, 4, 5 오른쪽 서브트리 : 3, 6, 7 부모노드를 기준으로 왼쪽 자식 노드는 부모노드 * 2 오른쪽 자식 노드는 부모노드 * 2 + 1 ## 전위순회 루트 노드 출발 왼쪽 자식으로 왼쪽 자식으로 말단 노드이면 다시 뒤로 간 뒤 오른쪽 자식 2~4 반복 이동 전, 해야할 함수를 호출한다. 알고리즘 def DFS(v): if v > 7: # 제일큰 노드보다 크면 중단 return; else: print(v, end =" "); # 전위순회 출력 DFS(v * 2); # 왼쪽 노드 호출 DFS(v * 2 + 1); # 오른쪽 노드 호출..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (17)(2021.2.9 ~ 10) 본 내용은 해당 강의 토대로 작성 재귀함수와 스택 재귀함수 자기 자신을 호출하는 함수 반복문처럼 사용할 수 있다. 스택 자료구조 사용 예시 1 def DFS(x): if x > 0: print(x, end = " " ); DFS(x - 1); # 자기자신 호출 if __name__=="__main__": n = int(input()); DFS(n) # 깊이 우선 탐색 정수를 넣으면 내림차순으로 출력한다. 10 입력시: 10 9 8 7 … 1 출력 예시 2 def DFS(x): if x > 0: DFS(x - 1); # 자기자신 호출 print(x, end = " " ); if __name__=="__main__": n = int(input()); DFS(n) # 깊이 우선 탐색 정수를 넣으면 오름차순으로..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (16)(2021.2.8) 본 내용은 해당 강의 토대로 작성 1. 최소힙 힙 트리 노드 : 숫자가 쓰인 원 간선 : 노드를 잇는 선, 엣지라고도 함 루트 노드 : 가장 상위의 노드 자식 노드 : 상위 노드의 아래에 있는 노드 이진트리의 기본 구성 단위: 부모 노드와 자식 노드 왼쪽 서브 트리 : 2 , 5, 4 오른쪽 서브 트리 : 3, 6, 7 0 레벨 : 1 1 레벨 : 2, 3 2 레벨 : 5, 4, 6, 7 최소힙 부모노드가 자식노드보다 작아야 한다. 0레벨부터 왼쪽을 채운다. 부모가 자식보다 큰 경우, 바꿔준다.(업힙) heap.pop 하면, 루트 노드 값이 나온다. 빈 루트 노드 자리에 아래 레벨, 가장 오른쪽(큰 값)이 가게 된다. 더 작은 값이 부모노드가 되도록 자리를 바꾼다.(다운힙) heap.push가 되면, 업..

티스토리툴바