본문 바로가기

Python5

[Python] BFS (너비 우선 탐색) 알고리즘 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) | 김태원 - 인프런김태원 | 파이썬(Python)을 이용해 코딩 테스트 문제 풀이를 합니다., 개발자 취업 & 이직을 위한 핵심 코스 📝코딩테스트 대비 파이썬 알고리즘 문제풀이!  📢 수강 전 반드시 확인해주세요! 강www.inflearn.com BFS는 너비 우선 탐색 알고리즘입니다. DFS처럼 트리 구조를 탐색하는 알고리즘이지만 큐로 구현된다는 점에서 차이가 있습니다. BFS 문제 예시를 하나 들어보겠습니다.초기 위치값이 5라고 합시다. 여기서 +1, -1, +5 중 하나를 선택해 이동한다고 생각합니다. 그리고 그 다음에도 세 가지 중 하나를 선택해 이동하는 것을 반복합니다. 이동할 때마다 트리의 레벨은 하나씩 증가합니다.위치가 3이 되려면 최소 .. 2024. 6. 16.
[Python] DFS(깊이우선탐색) 알고리즘 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 강의 - 인프런 파이썬(Python)을 이용해 코딩 테스트 문제 풀이를 합니다., 개발자 취업 & 이직을 위한 핵심 코스 📝코딩테스트 대비 파이썬 알고리즘 문제풀이! 📢 수강 전 반드시 확인해주세요! 강의에서 제 www.inflearn.com 위 강의의 내용을 정리한 글입니다. DFS는 깊이 우선 탐색이라고 하는 알고리즘으로, 트리 구조를 탐색할 때 사용됩니다. 트리의 가장 높은 레벨까지 갔다가 더 이상 없어서 막히면 되돌아가는 동작으로 구현됩니다. 트리 순회 트리 순회 방법은 전위, 중위, 후위 순회의 3가지가 있는데 대부분의 문제는 전위 순회를 통해 풀고, 예외적으로 병합 정렬 문제에서는 후위 순회를 이용하기도 합니다. 이 과정은 중첩 반복문의 대체제이.. 2024. 1. 28.
[Python] 지역변수와 전역변수 1. 메인함수에 정의된 변수는 전역변수이다. def testFunc(): print(n) # 5 if __name__=="__main__": n = 5 testFunc() 2. 사용자 함수에 전역변수와 같은 이름의 변수를 정의했다면, 그 변수는 해당 함수 안에서 더는 전역변수로 쓰이지 않고, 함수 내부에서만 쓰는 지역변수가 된다. def testFunc(): if n == 5: n = n + 1 # 오류 발생 print(n) if __name__=="__main__": n = 5 testFunc() testFunc() 안에서 n = n + 1 이란 부분 때문에 n은 지역변수로 새로 정의되었다. 그런데 n에 숫자값을 대입하기도 전에 n에 n + 1 을 대입하니 오류가 발생한다. 3. 사용자 함수에서 전역변.. 2024. 1. 18.
[Python] 최소힙(heap) 자료구조 최소힙 자료구조란? 완전이진트리 (포화이진트리와 헷갈리지 말자) 로 구성된 자료구조. 부모 노드값이 자식 노드의 값보다 작게 트리를 구성한다. 그래서 트리의 루트 노드는 입력한 값들 중 최소값이 저장된다. 동작 방식 힙에 자료가 push되었을 경우 "업 힙" 동작을 한다. 부모와 비교하며 자식이 작을 경우 swap한다. 힙에서 자료가 pop되었을 경우 "다운 힙" 동작을 한다. 자식과 비교하며 자식이 클 경우 swap한다. 가장 깊은 레벨의 노드(7)가 루트로 올라간다는 점에 유의. 파이썬에서 자료구조 구현 heapq 자료구조를 import하여 간단하게 구현 가능하다. import heapq as hq heap = [] hq.heappop(heap) # 루트 노드의 값을 pop시킨다. hq.heappus.. 2024. 1. 8.
[Python] 코딩테스트에서 알아놓으면 유용한 파이썬 문법 ※ 파이썬 복습 겸 필자가 몰랐던 것 위주로 정리 람다 함수(lambda x, y: x + y)(1,2) # 3(lambda li: li[1])([1,2,3]) # 2  리스트 관련elements = ["a", "b", "c"]# 리스트 요소의 인덱스elements.index("요소명")# 리스트에 요소 추가elements.append("요소")# 리스트 맨 마지막 인덱스인 요소 추출elements.pop(-1)# 리스트 값으로 삭제element.remove("a")# set 자료형(중복이 제거된 자료형)으로 변환set(elements) # {'a', 'b', 'c'}# 리스트에 0 채우기zeros = [0 for i in range(3)] # [0, 0, 0]# 2차원 배열에 0 .. 2023. 8. 31.