알고리즘 테크닉 - 런타임 전의 전처리 기법

1. 런타임 전의 전처리(preprocessing) 실제 문제를 해결하는 프로그램을 작성하기 전에, 해당 프로그램의 핵심을 얻기 위한 다른 프로그램을 미리 작성하여 원하는 값을 구해놓고, 문제를 해결하는 프로그램을 작성하는 기법 프로그램 안에 원하는 값을 계산하는 코드를 작성하지 않고, 미리 필요한 값을 계산해놓은 다음에 실제 프로그램에서 시간복잡도를 줄이는 기법이다. 이런 기법은 사실 알게모르게 많이 써왔다.. 최근에 이것이 핵심인?문제를 풀어서 복기해본다 (태그는 이분탐색이었지만) 2. 문제 4030번: 포켓볼 (acmicpc.net) 4030번: 포켓볼 선영이는 당구대를 상근이에게 빌렸다. 상근이는 선영이에게 공 16개가 들어갈 수 있는 4×4 크기의 트레이도 같이 주었다. 이 트레이는 그림 (a)..

• format_list_bulleted 전처리
• · 2023. 4. 3.
• textsms

특별한 이분탐색 -실수 구간에서도 이분탐색이 가능할까-

1. 문제 14609번: 구분구적법 (Large) (acmicpc.net) 14609번: 구분구적법 (Large) 첫 번째 줄에는 다항함수의 차수를 나타내는 양의 정수 K(1 ≤ K ≤ 10) 가 주어진다. 두 번째 줄에는 최고차항부터 내림차순으로 각 항의 계수를 나타내는 정수 ci (0 ≤ ci ≤ 10, 1 ≤ c1 ≤ 10) 가 www.acmicpc.net 2. 풀이 실제 적분값과 근삿값이 일치하게 만드는 epslion을 찾는다 그러면 실제 적분값을 먼저 구해야겠지 최대 10차 다항함수까지로 제한되어있고 다항함수 적분 방법도 힌트로 나와있다 그러면 $c_{0}x^{k} + c_{1}x^{k-1} + ... + c_{k}$를 적분하면 된다 그러면 $$\frac{c_{0}x^{k+1}}{k+1} + \..

• format_list_bulleted 이분 탐색
• · 2023. 4. 2.
• textsms

이분탐색 올바른 사고 연습하기 1편

1. 문제1 1072번: 게임 (acmicpc.net) 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이1 탐색범위는 x+1부터 충분히 큰 수까지.. x가 제한이 10의 9제곱인데.. 이는 입력으로 주어지는 x가 10의 9제곱이지 가능한 제한이 10의 9제곱이라는 뜻은 아니다. 그래서 대충 10의 18제곱까지 탐색하도록 범위를 잡았다 그리고 절대로 지지 않는다고 했기 때문에... x 기준으로 현재 x+k를 잡았다면... y값은 y+k로 바뀌겠지 그리고 그때 변화된 승률도 (y+k)*100//(..

• format_list_bulleted 이분 탐색
• · 2023. 4. 1.
• textsms

처음 배우는 parametric search 이해해보기

1. parametric search 이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘 최적화 문제는 예를 들면 다음과 같다. "f(x) = True가 되는 x의 최댓값을 구하세요" 이를 결정 문제로 바꾸면 다음과 같을 것이다. "어떤 x에서 f(x) = True인가?" 가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다. 모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까 하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적 그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다. x1 < x2이고, f(x2) = Tr..

• format_list_bulleted 이분 탐색
• · 2023. 3. 29.
• textsms

이분탐색 응용력 키우기 연습1 -차이가 가장 가까운 값을 찾는 방법-

1. 문제 2428번: 표절 (acmicpc.net) 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 2. 풀이 $F_{1}, F_{2}, ... , F_{n}$이 주어질때, $F_{i} = 0.9*F_{j}$인 $(F_{i}, F_{j})$의 개수를 구하는 문제 조건이 2개가 있는데.. 사실 $F_{i} = 0.9*F_{j}$을 만족하는 최대 인덱스 j를 찾는다 그러면 $F_{i}, F_{i+1}$, ..., $F_{i}, F_{j}$까지가..

• format_list_bulleted 이분 탐색
• · 2023. 3. 28.
• textsms

10진수로 바꾸지 않고 2진수, 8진수 서로 변환하기

1. 문제 1373번: 2진수 8진수 (acmicpc.net) 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 2. 2진수에서 바로 8진수로 바꾸는 알고리즘 [진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기! : 네이버 블로그 (naver.com) [진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기! 안녕하세요~~! 오늘도 여러분들께 유익한 정보를 드리러 온 나도비 입니다 !! 오늘의 주제는 2진수,8진수,1... blog.naver.com 8이 2의 세제곱이기 때문에, 원래 2진수에서 3자리씩 끊어서 각각을 10진수로 바꿔서 더해주면 그 수가 8진수가 된다. 1) 주..

• format_list_bulleted 문자열 알고리즘
• · 2023. 3. 26.
• textsms