GSHS와 SSHS의 개수 차이를 최대 구간 합으로 계산하기
문자열에서 GSHS와 SSHS를 따로 세는 것보다, 각 시작 위치를 점수로 바꾸면 두 패턴의 개수 차이를 한 번에 다룰 수 있다. SSHS는 +1, GSHS는 -1, 나머지는 0으로 놓는 방식이다. 이 코드는 처음에 GSHS의 시작 위치를 누적하다가, 두 패턴의 차이가 가장 큰 연속 구
Shinem / Development notes
최근 기록
모든 글 보기 ↗합이 고정된 두 수의 곱 최대화: A를 앞에, C를 뒤에 반씩 배치하기
그래서 답은 N / 2개의 A 뒤에 (N + 1) / 2개의 C를 붙인 문자열이고, 쌍의 수는 그 두 값의 곱이다. 배치: 왜 A를 전부 앞에 두는가 A가 a개, C가 c개 있다고 하자. 순서쌍은 위치 i < j에 대해 S[i] = 'A', S[j] = 'C'인 경우다. A 하나와 C
순열의 사이클 분해와 첫 원소 선택 여부로 나누는 최소 비용 DP
원형으로 연결된 원소에서 이웃한 두 원소 중 적어도 하나를 골라야 한다면, 선형 DP를 그대로 적용하기 어렵다. 마지막 원소와 첫 원소도 이웃하기 때문이다. 중간까지의 선택이 올바르더라도 원을 닫는 순간 조건을 어길 수 있다. 27531.cpp의 핵심은 연결 관계를 사이클로 분리하고,
입력 순서를 유지하며 중복 숫자 제거하기
중복을 제거할 때는 어떤 숫자를 남길지만큼 어떤 순서로 남길지도 중요하다. 예를 들어 [3, 1, 3, 2, 1]에서 각 숫자가 처음 등장한 순서를 유지하려면 결과는 [3, 1, 2]가 되어야 한다. 처음에는 리스트에서 직접 중복을 확인했고, 이후 집합을 거쳐 딕셔너리 키의 삽입 순서를
[PS-Blogself 테스트] 등장 순서를 유지하며 정수 리스트 중복 제거하기
중복을 제거하면서 처음 등장한 순서를 유지하려면, 이미 본 값인지 확인하는 일과 결과의 순서를 보관하는 일을 함께 처리해야 한다. 예를 들어 [3, 1, 3, 2, 1]에서는 처음 나온 값만 남겨 [3, 1, 2]를 만들어야 한다. 결과 리스트를 직접 탐색하면 처음에는 각 값이 결과 리
(C++) Union-find 구현
개요 union-find 구현이다. * 1-based index * struct-based design 설명 vector<int> p: 각 원소의 부모 원소를 저장하는 배열로, 초깃값은 자신(p[i] = i)이다. vector<int> size: 각 원소가 부모인 집합의 크기를 저장하는