~2023 (160) 썸네일형 리스트형 [Python] 백준 1245번 문제, 농장 관리 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 [Python] 백준 1916번 문제, 최소 비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 우선순위 큐를 사용한 다익스트라를 사용하면 문제를 쉽게 해결할 수 있다. 모든 상황을 고려하는 것보다 우선순위 큐를 사용해 최소 비용들을 갱신하면 속도를 올릴 수 있다. 가중치가 작은 순서대로 정렬되어 있는 우선순위 큐에서 하나씩 꺼내 distance와 city에 값을 넣는다. 그런 다음 cost[city]가 초기화 되어 -1이 아니거나 이미 갱신이 됐지만 dis.. [Python] 백준 9251번 문제, 최장 공통 부분 수열(LCS) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 최장 공통 부분 수열을 그대로 적용시키면 해결할 수 있는 문제이다. 반복문의 i는 compared_str의 길이만큼 작동하며, j는 standard_str의 길이만큼 작동해 i와 j를 비교한다. dp[i][j]를 채우는 수식은 다음과 같다. i == j인 경우, 전 단계의 최고 누적합에다가 +1를 한다. i != j인 경우, 현재 수열의 누적.. [Python] 백준 1697번 문제, 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 너비 우선 탐색입니다. 그런데 입력을 그래프가 아닌 시작점과 끝점만 입력을 받을까? 그래프 정보가 없기 때문에 직접 그래프를 만들어주면서 탐색을 진행해야 한다. 그럼 그래프는 어떻게 만들까? 현재 foucs 값을 현재 노드의 값으로 지정하고 가중치가 없는 3개의 간선을 갖는다. 그 간선의 노드 값들은 focus의 { -1, +1, *2 }한 값들이다. 예제 입.. [Python] 백준 1991번 문제, 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리 순회로 전위 순회, 중위 순회, 후위 순회를 수행해야 한다. 기본적인 자료구조 문제이기 때문에 그닥 어렵진 않다. 각각의 순회 작동 원리를 알면 누구나 쉽게 구현할 수 있다. 그럼 여기서 말하는 순회 작동 원리가 무엇이냐? { 나 자신 -> 왼쪽 자식 -> 오른쪽 자식 }인 트리 탐색 순서를 이야기하는 것이다. 이 원리만 알고 있으면, OO 순회에서 OO 부분에 알맞게 원리 적용만 바꿔.. [Python] 백준 1987번 문제, 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 백트래킹을 사용해서 시간을 단축해야 하는 문제이다. 기존 DFS를 수행한다면, 매 경우를 탐색해야 하기 때문에 비효율적이다. 그래서 일정 조건에 부합할 경우 그 위치 p를 저장해 한 턴이 끝났을 때 처음부터 시작하는 것이 아닌 저장해둔 그 위치 p부터 시작한다. 예시를 하나 들기 위해 구조가 (1) -> (2) -> (3)처럼 되어 있고 노드가 가진 자식 노드를 dic으로 표현하.. [Python] 백준 1753번 문제, 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘을 사용해 최단 경로를 구하는 문제이다. 그런데 리스트를 사용한 다익스트라 알고리즘은 모든 정점에 대해 모든 경우를 처음부터 탐색해야 하기 때문에 비효율적이라고 한다. 그래서 우선순위 큐를 이용한다면 최소한으로 모든 경우의 최단 경로를 업데이트 할 수 있다. 이 우선순위 큐는 min_path를 업데이트 했을 때만 push가 되며, 최소힙으로 정렬된다. .. [Python] 백준 7662번 문제, 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이중 우선순위 큐를 큐 한 개만 이용해서 풀려고 했는데 안 됐다... 최소힙이 기준인 heapq 라이브러리를 이용해도 0-index가 최소값이기 때문에 반대편인 len(que)-1-index가 최대값일 것이라고 생각했다. 하지만 아니였다. 최소힙 기준으로 정렬되는 것이기 때문에 뒷부분에서 최대값들로 정렬된다는 보장이 없기 때문이다. 그렇기 때문에 최대힙과 최소힙으로 이루어진 우선순위 큐가 필요.. 이전 1 ··· 11 12 13 14 15 16 17 ··· 20 다음
