https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 정답 코드 import sys si = sys.stdin.readline N = int(si()) graph = [] for i in range(N): tmp = list(map(int, si().split())) graph.append(tmp) # x, y 에따라 가능한 d1, d2의 조합 모두 체크 case_list = [] for d1 in range(1, N): for d2 in range(1..
분류 전체보기
문제 링크 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 코드 import heapq input = __import__('sys').stdin.readline for _ in range(int(input())): n = int(input()) visited = [False for _ in range(n)] max_heap, min_heap = [],[] for i in range(n): command = input() if command...
문제 링크 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 코드 from bisect import bisect_left input = __import__('sys').stdin.readline m,n,l = map(int,input().split()) people = sorted(list(map(int,input().split()))) cnt = 0 for _ in range(n): x,y = map(int,input().split()) if ..
https://www.acmicpc.net/problem/11179 11179번: 2진수 뒤집기 희연이는 스웨덴으로 이사하여 현재 학교를 다니고 있다. 1학년 교육과정은 중국에서 배웠고, 스웨덴과 중국 두 나라의 교육과정은 완전히 다르다. 희연이는 수학을 좋아한다. 하지만 지금은. www.acmicpc.net 문제해석 진접변환을 구현하여 2진법으로 바꾼후 그 수를 뒤집어 표현하는 문제이다. 코드 D = dict() result = list() for i in range(36): if i < 10: D[i] = str(i) else: D[i] = chr(55 + i) N = int(input()) while True: if N == 0: break x = N % 2 result.append(D[x]) N ..
https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 문제 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다. 진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다. 예를 들어, 위..
https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(12}를 써서 출력하도록 하였다.
풀이 최소 금액 K의 범위를 생각해봅시다. K는 각 날짜마다 필요한 금액보다는 크거나 같아야 합니다. 즉, K는 1부터 N * 최대 사용 금액 사이의 값일 수 있다. 이분 탐색을 이용하여 가능한 K 값을 찾습니다. 이때, 이분 탐색의 중간값(mid)을 사용하여 K를 검사한다. 주어진 N일 동안 각 날짜별로 사용할 금액을 순회하면서 현재 인출 가능한 금액(mid)로 사용할 수 있는지 확인한다. 만약 mid로 사용할 수 없는 날이 나온다면, 인출 횟수를 늘려야한다. 만약 인출 횟수가 M 이하라면, 가능한 K값 중 작은 범위에서 다시 탐색. 그렇지 않다면, K값을 더 큰 범위에서 탐색한다. 위를 반복하여 최소금액 K를 찾으면 된다. 코드 #include #include #include using namespa..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 분류 수학 브루트포스 알고리즘 조합론 백트래킹 문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 ..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net N개의 정수가 있는 집합 A, M개의 정수가 있는 집합 B 존재 -> B의 요소들이 A에 포함되는지 확인 - 이분탐색 1. 집합 N 정렬 2. 시작과 끝 지점의 인덱스 지정 3. 시작 + 끝 // 2 구하기 4. 중간 지점의 값과 해당 값 비교 -> 동일하면 찾은 것 / 값이 크면 윗부분 탐색 / 값이 작으면 아랫부분 탐색 => 반복 5. 만일, 확..
알고리즘 분류 구현 문자열 문제 동혁이는 NBA 농구 경기를 즐겨 본다. 동혁이는 골이 들어갈 때 마다 골이 들어간 시간과 팀을 적는 이상한 취미를 가지고 있다. 농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 골이 들어간 횟수 N(10: t1=t1-(48*60-(60*m+s)) print('{:0>2}:{:0>2}'.format(t1//60,t1%60)) print('{:0>2}:{:0>2}'.format(t2//60,t2%60))
문제 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 누적 합을 저장하기 위해 새로운 2차원 배열(ps)을 만들어 준다. 이중 반복문을 이용하여 누적합을 저장한다. ps[i][j] = ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + li[i-1][j-1] 입력받은 좌표에 해당하는 밝기의 합을 구한다. ps[x2][y2] - ps[x2][y1-1] - ps[x1-1][..
https://www.acmicpc.net/problem/23827 23827번: 수열 (Easy) 모든 원소가 양의 정수이고, 길이가 $N$인 수열 $A_1, A_2, ..., A_N$이 주어진다. $1 \le i < j \le N$을 만족하는 모든 정수쌍 $(i, j)$에 대해 $A_i \times A_j$의 합을 $1\, 000 \, 000 \, 007$로 나눈 나머지를 구하시 www.acmicpc.net # 문제 설명 - 모든 원소가 양의 정수이고, 길이가 N인 수열 A1, A2, ... , AN이 주어진다. 1
