본문 바로가기

BOJ81

백준(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.
백준(BOJ) 9328 열쇠(Python) BFS 문제. 고려해줄 게 많아서 좀 귀찮았다. 먼저 맵을 확장시켜줬다. 시작을 건물 밖에서 하거니와 건물의 어떤 방향으로도 입장할 수 있기 때문에 (w+2)*(h+2) 크기로 맵을 확장시킨 후 가장자리를 모두 '.'로 둘렀다. 코딩을 처음 시작할 때 이런저런 문제를 풀면서 이미 해봤던 방법이라 쉽게 떠올릴 수 있었다. 그 후에는 현재 가진 키를 통해 갈 수 있는 문을 체크하는 배열을 만들고, BFS를 진행했다. 이미 지나온 오브젝트는 모두 '.'으로 만들어주고, 만약 열쇠를 주운 경우에는 visited와 queue를 초기화해줬다. 왜냐하면, 열쇠를 새로 줍는 순간 기존에는 갈 수 없었던 곳을 갈 수 있게 되어 이미 지나왔던 곳을 모두 다시 가봐야하기 때문이다. 코드는 다음과 같다. # -*- codin.. 2022. 7. 15.

티스토리툴바