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 알고리즘을 이용하여 위 그..

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

최소 비용 신장 트리 알고리즘 작동원리 이해하기 ( Prim / Kruskal ) 서론 [파이썬/Python] 최소 비용 신장 트리 알고리즘 구현하기 ( Prim / Kruskal ) 최소 비용 신장 트리 알고리즘 구현하기 서론 신장 트리(Spanning tree)란 연결된 비방향성 그래프에서, 노드는 그대로 유지한 채로, 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 develop247.tistory.com 이전 시간 구현하였던 Prim, Kruskal 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다. 본론 문제 1. Prim 알고리즘을 이용하여 위 그래프의 최소비용 신장 트리를 구하는 과정을 제시하시오. 처음 start_node = 1이므로, d[1] =..

동적 프로그래밍 - 행렬 곱셈 순서 계산하기 ( Brute-Force Algorithm ) 서론 동적 프로그래밍(Dynamic Programming)은 최적 부분 구조(Optimal Substructure)를 가지고 있고, 재귀 호출 시 비효율적인 중복이 발생하는 경우(Overlapping Recursive Calls) 사용하면 효과적이다. 최적 부분 구조(Optimal Substructure)란 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함되는 것을 말한다. 동적 프로그래밍을 적용하기 위해 항상 최적 부분 구조를 갖고 있는지 먼저 확인해야 한다. 그렇다면, 대표적인 동적 프로그래밍 문제로 행렬 곱셈 순서에 대해 동적 프로그래밍을 적용해보자. 본론 i × j 행렬과 j × 행렬을 곱하기 위해서..

최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall ) 서론 최단 경로(Shortest Paths)는 두 정점 사이의 경로를 구성하는 모든 간선의 가중치 합이 최소인 경로를 말합니다. 최단 경로는 단일 시작점 최단 경로와 모든 쌍 최단 경로, 그리고 싸이클이 없는 그래프의 최단 경로로 구분됩니다. 단일 시작점 최단경로는 단일 시작점으로부터 각 정점에 이르는 최단경로를 구하고, 모든 쌍 최단경로는 모든 정점 쌍 사이의 최단경로를 모두 구합니다. 그 중에서도 단일 시작점 최단 경로인 다익스트라 알고리즘(Dijkstra Algorithm)과 벨만-포드 알고리즘(Bellman-ford Algorithm), 그리고 모든 쌍 최단경로인 플로이드-워샬 알고리즘(F..

최소 비용 신장 트리 알고리즘 구현하기 서론 신장 트리(Spanning tree)란 연결된 비방향성 그래프에서, 노드는 그대로 유지한 채로, 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 부분그래프입니다. 최소 신장 트리(Minimum spanning tree, MST)는 주어진 그래프의 부분 그래프인 여러 신장 트리 중에서 모든 간선의 가중치 합이 최소가 되는 신장트리입니다. 신장 트리의 의미와 최소 신장 트리를 구하는 두 가지 알고리즘인 프림 알고리즘(Prim algorithm)과 크루스칼 알고리즘(Kruskal algorithm)에 대해 코드를 통해 이해해보도록 하겠습니다. 본론 minimum_spanning_tree.py import sys class Graph: def __i..

HTML로 간단한 웹페이지를 만들고 있었다. 아무리 봐도 내가 코드를 잘못 작성한게 아닌데, CSS 속성이 적용이 안되는 경우가 있었다. 무엇이 문제일까 알아보던 중 아래를 통해 문제를 해결할 수 있었다. 1. 브라우저에서 F12를 눌러 개발자 도구를 킨다. 2. 브라우저 좌측 상단의 새로고침 버튼에 커서를 두고 우클릭을 한다. 3. 캐시 비우기 및 강력 새로고침을 누른다. ※ 강력 새로고침은 개발자 모드를 켰을 때만 나온다. 위를 통해 문제를 해결할 수 있었다. 코드를 작성할 때마다 새로고침을 눌러서 결과를 확인했었는데, 아무래도 캐시가 남아있어 코드가 적용이 안됐던 것 같다.

백준 1271번 엄청난 부자2 - 사용언어 : 파이썬 www.acmicpc.net/problem/1271 문제 갑부 최백준 조교는 동전을 최소로 바꾸는데 성공했으나 김재홍 조교가 그 돈을 발견해서 최백준 조교에게 그 돈을 나누자고 따진다. 그 사실이 전 우주로 알려지자 우주에 있던 많은 생명체들이 자신들에게 돈을 분배해 달라고 당장 달려오기 시작했다. 프로토스 중앙 우주 정부의 정책인, ‘모든 지적 생명체는 동등하다’라는 규칙에 입각해서 돈을 똑같이 분배하고자 한다. 한 생명체에게 얼마씩 돈을 줄 수 있는가? 또, 생명체들에게 동일하게 분배한 후 남는 돈은 얼마인가? 코드 money, life = map(int, input().split()) print(money//life) print(money%lif..