본문 바로가기

전체 글91

백준(BOJ) 2110 공유기 설치(Python) 이분 탐색 문제. 공유기 간의 거리를 이분 탐색의 변수로 두고, 모든 집을 탐색하며 현재 거리로 두 집 간에 공유기를 설치할 수 있는 지를 확인한다. 공유기를 설치할 수 있다면 공유기 개수를 늘린다. 탐색이 끝나고 설치할 수 있는 공유기 개수가 입력받은 공유기 개수 이상이라면 ans를 갱신하고 start를 변경한다. 그렇지 않다면 end를 변경한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,m=map(int,input().split()) L=[] for i.. 2022. 7. 18.
백준(BOJ) 1060 좋은 수(Python) 그냥 시키는 대로 하면 되는 문제. 우선순위 큐가 태그에 있던데 그거 안 쓰고도 풀렸다. 집합 S에 속하는 수들을 정렬하고, 정렬된 리스트를 기준으로 i번째 수와 (i+1)번째 수의 차이를 구한 뒤 (i번째 수)+1과 함께 새로운 리스트에 저장한다. 이는 좋은 구간이 존재할 수 있는 구간이다. 이때 집합 S의 최솟값이 2라면 ans에 [0,1]을 추가하고, 그 외에도 구간의 길이가 1이라면 위에서 좋은 구간이 될 수 있는 리스트에 구간을 저장하지 않고 ans에 [0,구간에 해당하는 수]를 추가한다. 좋은 구간의 조건에 따르면 구간의 경계값은 같을 수 없기 때문에, 구간의 길이가 1이라면 좋은 구간의 개수가 0이라 뒤에서 탐색할 이유가 없기 때문이다. 그 후 집합 S에 속하는 수들에 대해서도 ans에 [0.. 2022. 7. 18.
백준(BOJ) 16946 벽 부수고 이동하기 4(Python) BFS 문제. 모든 칸에 대해 탐색하는데, 벽이 아닌 칸에서 BFS를 진행한다. 인접한 모든 벽이 아닌 칸의 개수를 세고, 그 모든 칸에 동일한 고유 넘버를 지정해준 뒤 딕셔너리에 그 넘버에 해당하는 칸의 개수를 저장한다(해싱). visited에서 진행할 것이기 때문에 위의 예제에서 진행하면 다음과 같은 visited가 생성될 것이다. 000 010 000 -> 203 000 040 그 후에는 다시 모든 칸을 탐색하며 벽이 있는 칸인 경우 상하좌우의 칸이 벽이 아닌 경우 고유 넘버를 모두 저장하되, 이들이 중복되지 않도록 한다. 그 후 고유 넘버에 해당하는 칸의 개수를 모두 세서 입력받은 맵의 해당하는 칸에 더해주면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sy.. 2022. 7. 17.
백준(BOJ) 1082 방 번호(Python) DP 문제. 현재 가지고 있는 금액을 i로 하고, 최대 방 번호를 dp[i]로 하는 배열을 설정한다. 초기 설정은 모두 0이다. 이는 숫자의 가격을 고려하지 않고 만들어질 수 있는 최소 방 번호가 0이기 때문이다. 같은 숫자 구성을 한 경우 내림차순으로 정렬된 경우가 가장 번호가 큰 경우이므로, 9부터 0까지 번호를 채워나간다. 숫자를 살 수 있으면 사기 전의 금액에서 최대 번호의 맨 뒤에 현재 구매한 숫자를 추가하는 방식으로 dp를 갱신한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionli.. 2022. 7. 17.
백준(BOJ) 1039 교환(Python) BFS 문제. 현재 숫자와 바꾼 횟수에 따라 방문 처리를 해줘야 한다. 그 외에는 크게 어려울 게 없었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,k=input().split() visited=[[0]*11 for i in range(1000001)] visited[int(n)][0]=1 n=list(n) l=len(n) k=int(k) queue=deque() queue.append([n,0]) def swap(i,j): temp=a[i] a[i]=a[.. 2022. 7. 16.
백준(BOJ) 3366 수열 줄이기(Python) 스택 문제. reduce 연산의 비용의 합을 최소로 하기 위해서는, 수열의 최솟값부터 reduce를 해주면 된다. 어짜피 reduce를 진행해나가게 되면 어떤 수 양 옆에 존재하는 수는 절대 작아질 수 없기 때문이다. 즉, 어떤 수가 수열의 최솟값인 경우가 그 수에 대해 reduce를 진행했을 때 reduce의 최솟값인 것이다. 이를 이용하면 쉽게 문제를 해결할 수 있다. 수열의 처음부터 내림차순으로 stack에 수를 집어넣다가 현재 집어넣는 수가 내림차순을 만족하지 않는 경우 reduce를 진행하면 된다. 왜냐하면, 내림차순을 만족하지 않는 수가 등장하게 되면 그 순간 스택의 수들 중 스택의 맨 위에 위치한 수(a)가 현재까지 확인한 부분수열의 최솟값이고, 위에서 설명한 알고리즘대로 문제를 해결하면 되.. 2022. 7. 16.

티스토리툴바