ImJay

색칠 문제 - 백트래킹(Backtracking) 상태 공간 트리와 알고리즘 서론 상태 공간 트리(State Space Tree)는 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리입니다. 백트래킹(Backtracking)은 상태 공간 트리에서 새로운 탐색이 무의미하다고 판단되면, 다른 새로운 탐색이 가능한 선택 포인트(choice point)로 backtrack하여 새로운 탐색을 시도합니다. 더 이상의 선택 포인트가 존재하지 않으면, 탐색은 실패로 끝납니다. 되추적은 갈림길에 표시를 해두고 막다른 골목에 다다르면 갈림길까지 되돌아가서 다른 골목으로 가보는 방법입니다. 깊이 우선 탐색과 관련 있습니다. 색칠 문제(Coloring Problem)는 주어진 그래프에서 인접한 정점은 같은 색을 칠할 수..

허프만 알고리즘을 통한 최적 이진 문자 코드 구축 과정 분석하기 (허프만 코드) 서론 허프만 코드(Huffman Code)란 문자들로 이루어진 데이터 파일 크기를 작게 만들기 위해 문자 각각을 코드화 하는 방법 중 하나입니다. 더 자주 출현하는 문자에 대하여 더 짧은 코드를 할당합니다. 최적 이진 코딩 문제(Optimal Binary Code)는 주어진 텍스트 파일에 있는 문자들을 이진 코드로 표현하기 위해 필요한 비트의 개수가 최소가 되는 이진 문자 코드를 찾는 문제입니다. 즉, 허프만 코딩 문제는 주어진 문자 집합에 대해 최적 코드에 해당하는 이진 트리를 구축하여 최적 이진 문자 코드(Huffman code)를 만들어 보는 문제입니다. 본론 허프만 코딩 문제 알고리즘 1) Priority Queue ..

[파이썬/Python] 최단 경로 알고리즘 작동원리 이해하기 ( Floyd-washall ) 서론 [파이썬/Python] 최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall ) 최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall ) 서론 최단 경로(Shortest Paths)는 두 정점 사이의 경로를 구성하는 모든 간선의 가중치 합이 최소인 경로를 말합니다. 최단 경.. develop247.tistory.com 이전 시간 구현하였던 Floyd-washall 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다. 본론 문제 1. Floyd-washall 알고리즘을 이용하여 위 그..