전체 글91 백준(BOJ) 9466 텀 프로젝트(Python) DFS 문제. 팀을 구성하는 사이클을 찾아주면 된다. DFS를 진행하는 첫 노드를 조상 노드라고 임의로 칭할 때, 이 조상 노드를 끝까지 들고 가면서 탐색을 진행한다. 그러면 탐색이 끝나는 노드의 경우, 내가 나를 가리키는 노드 내가 다른 사이클을 가리키는 노드 내가 내 사이클을 가리키는 노드 이 세 경우만 존재하게 될 것이다. 그 중 팀을 구성하는 사이클인 경우는 3.하나이므로, 3.인 경우에 한해 노드를 거슬러 올라가며 3.에서 가리킨 마지막 노드가 나올 때까지 개수를 세주면 해당 개수가 하나의 사이클을 이룬 노드들의 개수가 된다. 이 사이클을 모든 노드에 대해 찾아주면 된다. 그리고 내가 나를 가리키는 경우만 따로 빼줬다. 코드는 다음과 같다. # -*- coding: utf-8 -*.. 2024. 3. 21. 백준(BOJ) 2573 빙산(Python) 그래프 탐색 문제. 빙산 한 번 줄이고 BFS로 빙산 덩어리 개수 찾고 또 빙산 한 번 줄이고 BFS로 빙산 덩어리 개수 찾고 이 과정을 빙산 덩어리가 2개 혹은 빙산이 더 없을 때까지 반복하면 된다. 이때 주의할 점은, 빙산을 줄일 때 순차적으로 줄여나가면 이미 줄인 빙산이 다음에 줄일 빙산에 영향을 주기 때문에 빙산이 줄어드는 높이를 다른 테이블에 따로 관리해줘야 한다는 것이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product from itertools import combinations.. 2024. 3. 20. 백준(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. 이전 1 2 3 4 ··· 16 다음
