Joonas' Note

문제 소인수가 2 또는 3 또는 5로만 이루어진 수를 "못생긴 수"라고 했을 때, N번째 못생긴 수를 출력하는 문제이다. New Zealand 1990 Division I에 등장했던 문제로, 여러 저지에서 풀어볼 수 있다. UVa 136 - Ugly Numbers POJ 1338 - Ugly Numbers 정올 1318 - 못생긴 수 풀이 빨간색을 현재까지 살펴본 수, 파란색을 앞으로 살펴볼 수라고 했을 때 그림을 위와 같다. 파란색으로 색칠된 수 중에서 가장 작은 수부터 순서대로 살피면, 그 순서대로 N번째 못생긴 수가 결정된다. 이는 다익스트라 알고리즘에서 그림이 어떻게 그려지는 지를 떠올리면 이해가 쉽다. 수의 중복을 제거하기 위해서 이전에 5를 곱해서 만들어진 수에는 2나 3을 곱하지 않았다. 2..

Palindromic tree 영문 글 - http://adilet.org/blog/palindromic-tree/ 두 문자열 S, P의 공통 부분 문자열이면서, 팰린드롬인 문자열의 개수를 구하는 자료구조이다. 관련 문제로는:2014-2015 ACM-ICPC, Asia Xian Regional - Problem G. The Problem to Slow Down You가 있다. Mikhail Rubinchik라는 유저가 고안한 자료구조라고 한다.삼성 소멤에서 shjgkwo님이 정리해준 한국어 문서도 있다. (https://www.secmem.org/blog/2019/05/17/Palindromic-Tree/)

이진 트리 중에서도 힙.힙 중에서도 최소힙을 구현한 코드C++에서 대소비교에 기본값인 less than(

링크: https://www.acmicpc.net/problem/2517문제최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다."왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다...

세그먼트 트리는 임의의 위치의 값들이 계속 변화하고, 특정 구간에 대한 연산(어떤 구간의 합, 어떤 구간 중 최소값 등)을 빠르게 구할 때 용이한 자료구조이다.한국어로는 구간 합 트리?라고도 하는 것 같다. 이 글을 적는 이유는 세그먼트 트리 자체를 다루기 위한 것은 아니고, 크기를 2배로 잡는 대신에 비재귀 형태로 간단하게 작성할 수 있는 코드를 소개하려고 한다.처음 접한 건 2016년 쯤 코드포스에서 읽었다. 워낙 간단하고 명료해서 아직까지 외우고 있다.링크: http://codeforces.com/blog/entry/18051대회에서도 자주 사용했는데, 블로그 포스팅은 한 적이 없어서 나중을 위해 다시 적어둔다. 자세한 설명은 원문 링크에 자세히 나와있으므로 생략한다.사용할 때 주의할 점은, que..

링크: https://www.acmicpc.net/problem/17140 문제 R 연산을 기준으로 구현하고, C 연산은 행/열만 바꿔서 똑같이 진행하면 된다. 한 행을 읽고 map과 같은 적당한 자료구조에 (수, 등장한 횟수)의 형태로 저장한다. 삽입과 조회, 수정 모두 \(O(logN)\) 만큼 걸린다. 정렬 기준은 1. 등장한 횟수가 적은 순, 2. 수의 크기가 작은 순이다. 정렬을 위해 map에 저장된 내용을 추출한다. 반복자 등으로 자료구조를 순회하면서 (수, 등장한 횟수)를 배열로 바꿔 정렬하고, 정렬된 순서로 새로운 행에 덮어씌운다. 바로 덮어씌워도 상관없으나, 이전 행보다 길이가 짧아지는 경우에 주의해야한다. (ex. [3, 1, 1, 1, 1, 1] → [3, 1, 1, 5, 0, 0] ..