본문 바로가기

BOJ79

백준(BOJ) 1185 유럽여행(Python) 최소 신장 트리 문제. 크루스칼 알고리즘으로 해결했다. 입력받은 간선의 가중치를 수정해서 문제를 해결했는데, 가중치를 (원래 가중치)*2+(양 노드의 방문 비용)으로 수정했다. 모든 길을 제거한 상태가 트리이므로, 어떤 한 노드에서 출발해 다른 모든 노드를 방문하고 다시 원래 노드로 돌아오기 위해서는 모든 간선을 2번씩 거쳐야 하기 때문이다. 그 과정에서 양 노드의 방문 비용도 발생하기 때문에 처음부터 간선의 가중치를 그 간선을 왕복할 때의 비용으로 수정해서 문제를 풀 수 있었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readlin.. 2022. 7. 11.
백준(BOJ) 1197 최소 스패닝 트리(Python) 간단한 최소 신장 트리 문제. 별다른 설명을 할 게 없다. 크루스칼, 프림 등등 최소 신장 트리 알고리즘 중 하나 선택해서 적용하면 바로 풀린다. 나는 크루스칼을 사용했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) v,e=map(int,input().split()) L=[] cycle=[i for i in range(v+1)] ans=0 n=0 for i in range(e): a,b,c=map(int,input().split()) heapq.heappush(.. 2022. 7. 11.
백준(BOJ) 1113 수영장 만들기(Python) BFS 문제. 가장 먼저 물을 채울 시작점을 구해야한다고 생각했다. 물을 채울 수 있다는 근거는, 칸의 상하좌우 중 현재 칸의 높이보다 높은 칸이 존재하는 것이라고 생각했다. 그렇게 칸을 정하고 나면 상하좌우 중 가장 높은 높이부터 가장 낮은 높이까지 물을 채워본다. 편의상 물의 높이를 w라 하겠다. w보다 칸의 높이가 더 낮다면 queue에 칸의 좌표를 push하는 방식으로 BFS를 진행했다. 만약 BFS를 진행하다 리스트 범위를 벗어나는 좌표가 나타나면 이는 물이 넘치는 것이므로 BFS를 중단한다. 그렇지 않고 끝났다면 현재 w는 그 칸에서 시작해 채울 수 있는 가장 높은 물의 높이일 것이므로, BFS를 하며 계산한 수영장의 부피를 ans에 더한다. 만약 물을 채우는 데에 성공했다면 모든 칸의 높이를.. 2022. 7. 11.
백준(BOJ) 1724 그림판(Python) BFS로 풀 수 있었던 문제. 일반적인 BFS 문제와는 달리 벽을 생성해야 하는 문제였다. 컴실1 maze project에서 이와 비슷한 유형의 자료구조를 구현해봤기 때문에 쉽게 풀 수 있었다. 2차원 리스트의 각 칸을 하나의 픽셀로 생각하고, 그 픽셀의 상, 하, 좌, 우 방향으로 이동할 수 있는지를 체크해줬다. 처음에는 모두 이동할 수 있도록 초기화하고, 가장자리 픽셀에서 리스트 밖으로는 벗어나지 못하도록 한 뒤 선분을 입력받는다. 입력받은 선분이 리스트의 가장자리에 위치한다면 pass하고, 그렇지 않은 경우 두 점의 x좌표가 동일하다면 x좌표를 기준으로 변화하는 y좌표에 대해 해당하는 선분의 위 픽셀은 아래로 이동할 수 없고, 아래 픽셀은 위로 이동할 수 없도록 설정한다. y좌표는 x좌표와 마찬가지.. 2022. 7. 10.
백준(BOJ) 3111 검열(Python) 문자열 테크닉으로 해결할 수 있는 문제였다. 앞에서부터 stack(L1)에 문자를 하나씩 넣다가 L1의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop, 그 다음에는 새 stack(L2)에 뒤에서부터 문자를 하나씩 넣다가 L2의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 reversed(A)와 같으면 len(A)개 만큼 pop한다. 위의 모든 작업이 끝나면 L2에서 pop한 문자를 L1에 push하면서 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop해준다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collecti.. 2022. 7. 10.
백준(BOJ) 7344 나무 막대(Python) 간단한 그리디 문제. 문제를 풀기 위한 아이디어를 떠올리기 쉬웠던, 문제에 나온 대로만 하면 되는 문제였다. 입력받은 막대의 l, w 값을 l의 오름차순에 w의 오름차순으로 정렬하고, [[[0,0]]] 형태의 리스트를 만든다. 이 리스트를 L이라 하자. L은 가동되는 기계가 어떤 막대를 가공할 지를 담고 있을 것이다. L의 최종 개수는 기계의 개수이고, 이는 최소 작동 준비 시간일 것이다. 우리는 각 막대의 l, w 값을 L의 모든 원소의 마지막 원소의 0, 1번째 인덱스에 위치한 값과 비교할 것이다. 그리고 l=L3[k][-1][1]: L3[k].append(X) flag=1 break if not flag: L3.append([X]) print(len(L3)) 풀고 난 느낌은, 문제가 overrate.. 2022. 7. 9.

티스토리툴바