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//(..
1. parametric search 이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘 최적화 문제는 예를 들면 다음과 같다. "f(x) = True가 되는 x의 최댓값을 구하세요" 이를 결정 문제로 바꾸면 다음과 같을 것이다. "어떤 x에서 f(x) = True인가?" 가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다. 모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까 하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적 그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다. x1 < x2이고, f(x2) = Tr..
1. 이분 탐색(binary search) False 구간, True 구간 2개의 partition으로 분할된 구간에서, 분할 경계의 위치를 O(logN)에 찾는 알고리즘이다. STL로 구현된 lower_bound와 upper_bound는 가장 유명한 이분 탐색 함수중 하나이다. 정렬된 배열에서 x의 lower bound는 정렬 상태를 유지한 채 x를 삽입할 수 있는 첫번째 위치이고 upper_bound는 마지막 위치이다. 위 그림에서 lower_bound(20)은 20을 넣을 수 있는 첫번째 위치로, 1번에 넣을 수 있다.. upper_bound(20)은 20을 넣을 수 있는 마지막 위치로, 4번에 넣을 수 있다..(원래 4번은 5번으로 이동하겠지) 이분 탐색적 설명으로는, lower_bound는 x보..
1. 문제 배열에 다음과 같은 연산을 할 수 있습니다. 배열에 정수 x (x ≠ 0) 를 넣습니다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거합니다. ( 절댓값이 가장 작은 값이 여러개일 때는, 그 중 가장 작은 수를 출력하고, 그 값을 배열에서 제거합니다. ) 비어있는 배열에서 시작하여 입력된 연산을 실행하는 프로그램을 작성해보세요. 2. 풀이 자바하면 클래스 어렵게 생각하지 말고 필요하다면 클래스를 구현해서 사용하라 절댓값을 만드는 클래스를 구현해야하는데, 문제는 절댓값을 기준으로 오름차순 정렬을 할 수 있어야하고 중요한건 절댓값만 저장하는게 아니라 원본도 저장해야한다. 그래야 우선순위 큐에서 출력할때 원본값을 출력할 수 있으니까 import java.util.Scanner;..
1. 문제 1300번: K번째 수 (acmicpc.net) 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 2. 풀이 k 제한이 커서 그런지 이전에 배운 우선순위 큐 방법으로 풀면 시간초과로 통과를 못한다 import heapq from sys import stdin n = int(stdin.readline()) k = int(stdin.readline()) q = [] for i in range(1,n+1): heapq.heappush(q,(i*1,i,1)) for _ in r..
1. 문제 n개의 숫자로 이루어진 수열과 m개의 숫자로 이루어진 수열이 주어졌을 때, 각 수열에서 정확히 원소를 하나씩만 뽑아 나올 수 있는 모든 쌍들을 모두 구하고, 그 값들을 오름차순이 되도록 나열했을 때의 k번째 쌍의 두 수의 합을 구하는 프로그램을 작성해보세요. n,m은 1이상 10만 이하의 자연수 k는 1이상 min(nm, 10만)이하 2. 풀이 가장 쉽게 생각할 수 있는 방법은 mn개의 모든 조합을 만든 다음에 우선순위 큐에 모두 집어 넣고, k번째 빠지는 수를 출력하면 된다 근데 뭐 당연히 시간초과 + 메모리 초과임 m과 n이 10만인데 시간복잡도가 얼마냐 이거 O(M + N + MNlogMN + KlogMN)인가..? 아무튼 O(MN)으로 생각하는 순간 10만*10만 = 100억으로 오바다..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
