파이썬 알고리즘 인터뷰 그래프 간단 정리

그래프

• 그래프 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 정점(Vertex) 와 정점들을 연결하는 변(Edge) 으로 구성됨
  • 유향 그래프 변을 화살표로 나타내는 경우 해당 방향으로만 이동할 수 있는 그래프
  • 무향 그래프 변이 선분으로 표현되는 경우 양방향 모두 이동이 가능한 그래프
  • 오일러 경로 모든 간선을 한 번씩 방문하는 유한 그래프
  • 해밀턴 경로 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 최적 알고리즘이 없는 대표적인 NP-완전 문제
    • 해밀턴 순환 해밀턴 경로에서 원래의 출발점으로 돌아오는 경로
    • 외판원 문제 해밀턴 순환에서 최단 거리 찾는 문제
  • 그래프 순회 그래프 탐색이라고 불리며 각 그래프의 각 정점을 방문하는 과정 DFS 가 BFS 보다 널리 쓰임
    • 깊이 우선 탐색 (Depth-First Search, DFS) 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식 스택으로 구현하며 재귀로 좀 더 간단하게 구현 코딩 테스트 시에도 재귀 구현이 더 선호됨
      • 재귀 사전식 순서로 방문
      • 스택 가장 마지막에 삽입된 노드부터 꺼내서 반복하게 되다보니 역순으로 방문
    • 너비 우선 탐색 (Breadth-First Search, BFS) 갈림길에 연결되어 있는 모든 길을 한 번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 방식 DFS 보다 쓰임새는 적지만 최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용하게 쓰임
      • 큐 반복 구조로 구현
      • 재귀 재귀로 구현 불가
    • 백트래킹 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘 가보고 되돌아오기를 반복함 시행착오를 덜 거칠 수도 있지만 모든 경우를 다 거친 다음에 도달할 수도 있기 때문에 브루트포스와 유사 한번 방문 후 가능성이 없는 경우 즉시 후보를 포기하기 때문에 브루트 포스 보다 우아함 제약 충족 문제에 유용 DFS 의 슈퍼세트 DFS 는 백트래킹의 골격을 이루는 알고리즘
    • 제약 충족 문제 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제 백트래킹이 푸는데 필수적인 알고리즘
  • 그래프 표현 인접 행렬과 인접 리스트로 표현됨
    • 인접 리스트 출발 노드를 키로, 도착 노드를 값으로 표현한 것
• 중첩 함수 함수 내에 위차한 또 다른 함수 바깥에 위치한 함수들과 달리 부모 함수의 변수를 자유롭게 읽을 수 있다는 장점 있음 실무에서는 자주 쓰이는 편은 아님 단일 함수로 해결해야 하는 경우가 잦은 코딩 테스트에서 자주 쓰임 가변 객체인 경우 여러 가지 연산으로 조작 가능 재할당이 일어날 경우 참조 ID 가 변경되어 별도의 로컬 변수로 선언됨
• 객체 복사 파이썬은 모든 것이 객체 값을 별도로 복사하지 않는 한 변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조 [:]로 리스트 복사 copy() 메소드로 복사 deepcopy() 메소드로 복잡한 리스트 복사
• defaultdict 순회 문제 순회 시 존재하지 않는 키를 조회할 때 오류를 내지 않기 위해 항상 디폴트를 생성하는 구조 때문에 순호 중 변경되어 오류 발생 list 로 묶어서 새로운 복사본 생성으로 해결