좌표 압축 좌표 압축은 어떤 특정 알고리즘이라고 소개하기 보다는 기법이라고 보는게 맞는 것 같다. 정렬을 이용해서 떨어진 좌표의 범위를 줄이는데 쓰이고 세그 트리에서 자주 쓰인다고 한다. 아직 세그트리를 공부하지 않아서 먼저 보인 좌표 압축을 한 번 정리하고 가려고 한다. 백준 18870번 좌표 압축의 예시로 보면 2 4 -10 4 -9를 크기 순...

Clock Tree Clock Tree 문제 (GPT 번역) Farmer John의 새 헛간은 특이한 구조다. 방은 총 N개(2≤N≤2500)이고 1부터 N까지 번호가 매겨져 있다. 복도는 N−1개이며, 어떤 방에서든 복도를 따라 다른 모든 방으로 이동할 수 있다. 각 방에는 1~12가 적힌 원형 시계가 하나씩 있고 시계에는 시침은 항상 정수 눈금...

하이퍼 토마토 하이퍼 토마토 문제 입력 풀이 구데기 컵 문제에서 몇 안되는 난이도가 매겨진 문제이다. 토마토라는 백준 기본 bfs 문제를 11차원으로 확장한 문제이고, 인덱스를 관리하는게 문제다. n차원 배열도 컴퓨터 내부적으로 보면 1차원 배열과 똑같다는 것을 떠올려서 풀이를 했고 11개의 변수에 대해 앞에서부터 곱하면 그것이 차원을 나...

Dividing the Gold Dividing the Gold 문제 (GPT 번역) Bessie와 Canmuu가 금화 N개가 든 자루를 발견했고, 이걸 가능한 한 공평하게 둘로 나누려 합니다. i번째 동전의 가치는 vi이며, 각 값은 1 이상 2000 이하입니다. 두 소가 더미를 최대한 비슷한 가치가 되도록 나누고 싶지만, 항상 정확히 같게 나눌...

Fix Wiring Fix Wiring 문제 (GPT 번역) 당신은 우주선 ‘더 스켈드(The Skeld)’에서 다른 승무원들과 함께 있습니다. 중앙 전력 시스템을 점검하던 중, 핵심 배선 설치의 한 부분이 훼손된 것을 발견했습니다. 엔진 고장을 막으려면 설치를 신속히 복구해야 합니다. 이 설치는 N개의 노드와 M개의 전선으로 이루어져 있으며, ...

알렉산드리아의 디오판토스 알렉산드리아의 디오판토스 문제 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, n이 주어진다. (1 ≤ n ≤ 109) 출력 각각의 테스트 케이스마다 “Scenario #i:”를 출력하고, 주어진 n에 대한 방정식의 해의 개수를 출력한다. 각 테스트 케이스 사이에는 빈 ...

동전 문제 동전 문제 문제 구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 … 즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다. 구사과국에 살고 있는 구사과...

Sort(2) 알고리즘 문제를 풀 때 사용하는 내장 sort 함수의 시간 복잡도는 O(NlogN)이다. 어떤 것이 있고, 어떻게 응용되어 사용되는지 알아보자. O(NlogN)인 정렬 병합 정렬 분할 정복을 이용한 정렬 방법으로 원소가 1개 또는 0개 남을 때까지 둘로 쪼갠 다음 쪼갠 순서의 역으로 정렬해 합친다. 분할 정복으로 구현하게 되고,...

Sort 정렬은 데이터들이 있을 때 이를 정해진 순서대로 나열하는 문제이다. 컴퓨터 분야에서 다양한 데이터, 문제에는 데이터의 정렬이 필요한 경우가 아주 많은데 이를 효율적으로 해결하기 위한 알고리즘이다. 이제는 C++ STL이나 파이썬 내장 함수를 비롯해서 언어 대부분에 sort 기능이 구현이 되어있기 때문에 문제 풀 때 정렬을 구현하는 일은 거...

stack, queue, deque 사진 출처 : https://www.programiz.com/dsa 스택과 큐, 그리고 이를 확장한 덱은 가장 기본적인 자료구조로 널리 사용된다. 자료구조 수업에서 보통 가장 먼저 배우는 것이기도 하고. 스택 (stack) 스택이란 먼저 입력한 데이터가 가장 아래에 위치하고, 최근에 입력한 데이터가 가장 위...