본문 바로가기

전체 글91

백준(BOJ) 14269 전설의 쌍검 용사(Python) 그리디 문제. 오른손에 들어야 하는 검의 길이는 고정이기 때문에, set에 모든 A를 저장해 중복을 제거한 뒤 오름차순 정렬해 저장했다. 이 검들은 왼손에는 사용해도 되고 하지 않아도 되지만, 반드시 챙겨가야하는 검들이다. 왼손에 들어야 하는 검의 길이는 [B,C] 형태의 구간을 띄기 때문에, 모든 적의 [A, B, C]를 B 기준으로 오름차순 정렬한 뒤 C 기준으로 내림차순 정렬했다. 이렇게 정렬한 이유는, C가 같은 모든 적에 대해서 그 중 가장 B가 큰 적의 [B, C] 구간에 현재 왼손에 들 검이 존재한다면 C가 같은 모든 적에 대해 왼손에 드는 검을 만족시킬 수 있기 때문이다. 그 다음에는 위 set에 저장해둔, 반드시 챙겨가야하는 검들을 오름차순으로 확인하며 현재 보고 있는 검이 현재 구간에 .. 2023. 1. 31.
백준(BOJ) 11062 카드 게임(Python) DP 문제. 결국 끝까지 가서 상태를 봐야하기 때문에 그리디하게는 풀 수 없고, 백트래킹을 하자니 n이 너무 커서 DP를 생각했다. i번째부터 j번째까지의 카드를 뽑은 상태에서 근우가 가질 수 있는 최선의 점수를 저장하는 배열을 DP로 생성하자. DP[0][n-1]이 0부터 n-1번째까지 카드를 근우가 먼저 뽑은 경우가 되어야 하므로, DP[0][n-2]는 0부터 n-2번째까지 카드를 명우가 먼저 뽑은 경우가 될 것이다. 그렇게 순서를 결정해나가면 처음에 카드를 뽑는 것은 n이 홀수일 때에는 근우가 먼저, 짝수일 때는 명우가 먼저인 것을 알 수 있다. 그럼 이제 DP를 채우는 점화식을 생각해보자. DP[i][j]는 근우가 카드를 뽑을 차례인 경우와 명우가 카드를 뽑을 차례인 경우로 나눠 생각해야 한다. .. 2023. 1. 31.
백준(BOJ) 13334 철로(Python) 스위핑 문제. 구간의 길이가 d 이하인 구간에 대해, 끝값을 기준으로 구간을 선택해줬다. 끝값을 기준으로 구간을 선택하게 되면 현재 선택한 끝값을 변화시킬 때마다 해당 범위에 속할 수 없는 초깃값이 나오는데, 이 초깃값을 갖는 구간의 개수를 미리 세어두면 끝값이 변화할 때마다 해당 범위에 속할 수 없게 되는 초깃값을 갖는 구간의 개수만 빼주며 계속 구간을 선택해나가면 된다. 우선 문제를 더 쉽게 풀기 위해 입력받은 h와 o에 대해, 더 작은 값을 h, 더 큰 값을 o로 설정했다. 두 값은 서로 바뀌어도 상관이 없기 때문이다. 그 후에는 h를 기준으로 [h,o] 구간의 길이가 d 이하인 것의 개수를 세어 딕셔너리에 저장했다. [h,o]로 구성된 리스트를 o를 기준으로 오름차순 정렬하고, 각 구간에 대해 o.. 2023. 1. 29.
백준(BOJ) 13418 학교 탐방하기(Python) MST 문제. 최대 스패닝 트리와 최소 스패닝 트리를 각각 구한 다음, 각각의 코스트의 제곱의 차를 출력하면 된다. 코드는 다음과 같다. # -*- 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 permutations import copy """ #input=sys.. 2023. 1. 29.
백준(BOJ) 2195 문자열 복사(Python) 그리디 문제. P[s:len(P)]부터 P[s:s+1]까지 끝값을 변화시키며 S에 들어있는지 확인하는데, 들어있다면 현재 끝값을 s로 수정하면서 P의 끝까지 탐색한다. 코드는 다음과 같다. # -*- 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 permutatio.. 2023. 1. 17.
백준(BOJ) 24524 아름다운 문자열(Python) 그리디 문제. 문제에서 요구하는 조건을 만족하기 위해서는 각각의 T를 골라내기 위해서는 T의 첫 번째 문자를 찾고, 그 뒤에서 두 번째 문자를 찾고, 이 과정을 마지막 문자까지 반복해야 한다. 그러기 위해서 먼저 T에 들어있는 문자의 인덱스를 해싱으로 각각 큐에 모아준다. 그 후 T에 있는 문자의 인덱스 중 가장 먼저인 인덱스를 기록해둔다. 그리고 그다음 문자의 인덱스 중에서 기록된 인덱스보다 크면서 제일 작은 인덱스로 기록된 인덱스를 변경한다. 이때 이미 체크한 인덱스는 모두 pop해준다. 이 과정을 반복해나가고, 만약 T의 문자들 중 하나라도 더 이상 큐에 인덱스가 남아있지 않으면 반복문을 종료한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from coll.. 2023. 1. 14.

티스토리툴바