백준80 백준(BOJ) 5549 행성 탐사(Python) 누적 합 문제. 2차원 누적 합을 정글, 바다, 얼음에 대해 각각 만들고 값을 출력하면 된다. 계산하기 쉽도록 0으로 이루어진 행과 열을 각각 0번째로 두고 풀었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product from itertools import combinations """ from itertools import combinations from itertools import combinations_with_replacement from itertools import permutation.. 2023. 4. 20. 백준(BOJ) 27447 주문은 토기입니까?(Python) 그리디 문제. 문제의 핵심은 결국 토기를 최대한 많이 만들어두고, 극한의 이득을 취하면서 커피를 담아둬야 한다고 생각했다. 따라서 0부터 시간을 증가시키며 커피를 담아둘 수 있는 시간이 아니고, 손님이 방문하는 시간이 아닌 경우에는 모두 토기를 만들었다. 그리고 커피를 담아둬야 하는 경우 토기가 있다면 커피를 즉시 담고, 토기가 없다면 토기를 만들고 커피를 담았다. 이때 모든 과정 중 한 번이라도 커피를 담을 수 없거나 토기를 만들 수 없으면 fail을 출력했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools impor.. 2023. 4. 19. 백준(BOJ) 3663 고득점(Python) 그리디 문제. 문제의 핵심은 A로만 이루어진 가장 긴 구간을 찾는 것이라고 생각했다. 이미 A인 문자를 방문하는 것 자체가 손해이기 때문이다. 처음에는 해당 구간만 찾아서 문제를 푸려고 했는데, 길이가 같은 최장 구간이 여럿인 경우에는 문제가 발생했다. 그래서 브루트포스를 적용했다. 모든 문자에 대해서 인덱스가 증가하는 방향으로 가장 가까운 A가 아닌 문자를 찾고, 정방향과 역방향 두 방향을 고려해 이동 횟수를 계산해줬다. 그 중 최솟값을 최종적인 이동 횟수로 설정하게 되면, 결국은 A로만 이루어진 최장 구간에 대한 이동 횟수가 나오게 될 것이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heap.. 2023. 4. 19. 백준(BOJ) 24041 성싶당 밀키트(Python) 이분 탐색 문제. 현재 날짜에 따라 세균수를 체크해야 하는데, 날짜는 최대 2e9까지 가능하므로 O(logn)으로 값을 탐색해야 할 것이라고 판단했고, "특정 조건을 만족하는 범위 내의 최댓값"을 구해야 하므로 이분 탐색을 사용해야함이 자명하다고 생각했다. 이때 각 날짜에 맞는 세균수를 구해야 하는데, 가장 먼저 k개의 중요하지 않은 재료를 빼야했다. 그리디하게 생각해보면 당연히 k번의 횟수를 모두 소모해야하는데, 중요하지 않은 재료가 k개 이상인 경우에는 현재 날짜를 기준으로 가장 세균수가 큰 재료들부터 빼줘야한다. 따라서 이분 탐색을 한 번 진행할 때마다 중요하지 않은 재료들을 현재 세균수를 기준으로 내림차순 정렬한 뒤, 그 중 순서대로 k개를 제외한 나머지 재료들의 세균수를 모두 더했다. 그 후에는.. 2023. 4. 18. 백준(BOJ) 2258 정육점(Python) 그리디 문제. 원하는 양의 고기를 살 수 없는 경우부터 살펴보면, 이는 당연히 모든 고기를 사도 무게가 부족한 경우일 것이다. 따라서 위의 경우는 제외해준다. 그 후에는 입력받은 고기들을 가격으로 오름차순 정렬한 뒤 무게로 내림차순 정렬해줬다. 문제에서는 어떤 고기를 샀을 때 해당 고기보다 싼 고기들만 가격을 내지 않고 가져갈 수 있으므로, 같은 가격의 고기들을 사는 경우 가장 무게가 많이 나가는 고기를 사는 것이 유리하기 때문에 위와 같이 정렬해줬다. 그 후에는 정렬된 순서대로 고기를 담으며 무게를 체크해줬다. 이때 현재까지 담은 고기의 무게가 목표 무게 이상인 경우, 목표 무게를 달성했을 때의 전체 가격 중 최솟값으로 ans를 수정해준다. 코드는 다음과 같다. # -*- coding: utf-8 -*.. 2023. 2. 24. 백준(BOJ) 20530 양분(Python) DFS 문제. 일반적인 트리에서는 u번 정점에서 v번 정점으로 가는 단순 경로가 1개 존재한다. 그러나 트리에 하나의 간선이 추가되면, 이 때는 이야기가 달라진다. 트리에 하나의 간선이 추가됨으로써 그래프 내에는 반드시 하나의 사이클이 발생한다. 사이클이 발생하게 되면 해당 사이클을 기점으로 단순 경로의 개수에 변화가 생긴다. 사이클 위에 있는 정점은 모두 사이클을 도는 두 가지의 방향에 따라 단순 경로가 생기고, 그 외에도 사이클 위에 있는 정점에서 다른 사이클 위에 있는 정점과의 간선을 제거해 얻을 수 있는 각 트리 간의 단순 경로 역시 2개이다. 즉, 사이클 위에 있는 각 정점에서 다른 사이클 위에 있는 정점과의 간선을 제거해 얻을 수 있는 트리들을 구하고, 각 쿼리마다 들어오는 정점들이 서로 다른.. 2023. 2. 18. 이전 1 2 3 4 ··· 14 다음
