(python3) 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 케이스 분리 특별한 알고리즘은 없었고, 모든 경우의 수를 케이스 분리해서 해결했습니다. 구현에만 집중해서 중첩이 너무 많습니다. 그닥 매력적인 풀이는 아닌 것 같네요.. d1, d2, x, y 의 조건을 문제에서 줬기 때문에 거기에 맞춰서 작성했고, 문제에서는 x,y 를 1부터 시작하는 인덱스로 제시해서 그 부분만 0부터 시작하는 인덱스로 바꿔서 적용해줬습니다. 코드 def solution(input) : # 입력 받기 N = int(input().s..
(python3) 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 예외 처리 문제에 몇가지 예외사항이 주어져 있기 때문에 꼼꼼하게 처리해주면 문제 없이 해결할 수 있습니다. 코드 def solution(input) : N,TS,P = list(map(int,input().split())) if N == 0 : # 한줄만 입력되는 경우 print(1) return scores = list(map(int, input().split())) # 두번째줄 입력 받기 score_board =..
(python3) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 아이디어 : 최빈값 구하기, key 파라미터로 커스텀한 기준으로 sort 하기 가장 직관적인 풀이로 접근했습니다. 평균값, 범위는 max, min, len 으로 쉽게 해결이 가능하고, median 도 sort 해서 가운데값을 찾아주면 됩니다. 최빈값이 문젠데, 최빈값은 여러개일 경우에 두번째로 작은 값을 찾아야하는 커스텀한 기준이 있으므로 이걸 잘 반영해줘야합니다. 제일 쉬운 방법은 각 수와 카운트값을 저장해서 카운트값 기준 내림차순, 수 기준 오름차순으로 ..
(python3) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 가장 직관적으로 생각나는 '모든 부분 수열 탐색' 시에는 시간 초과가 납니다. 연산 횟수가 "1~N 까지의 합" 으로 처리될 수 있으니까 O(N^2) 으로 100,000 * 100,000 이면 0.5초 보다는 훨씬 긴 시간이 필요합니다. 좌우 포인터를 조금 더 똑똑하게 가지고 가면 일반적인 경우 K가 그리 크지 않은 O(KN) 정도까지 연산이 단축될 수 있을 것 같네요 아이디어 : 부분 수열을 효과적으로 처리하는 방법 부분수열은..
14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net (python3) 문제 해석 구현은 단순한데, 문제 해석을 직관적으로 하면 안됩니다. 작동 방식을 잘 따라가야... 주변에 1칸이라도 청소할 수 있는 곳이 있으면 일단 반시계 방향으로 90도 회전해야합니다. 바로 앞이 청소 안한 영역이더라도 직진하면 안되고, 일단 회전해야합니다. 그리고 주어지는 방향 값은 0,1,2,3 이 시계방향이고, 회전 방향은 반시계방향이니 이점도 유의해서 코딩하도록 합시다 구현 내용은 주석..
(python3) https://www.acmicpc.net/problem/15685 문제 조건을 잘 읽어봐야합니다. 드래곤 커브가 격자 밖으로 빠져나가지 않는다는 조건 하나로 문제가 간결해집니다. 그리고 네모 변이 다 그려진 칸의 개수가 아니라 4개 점이 모두 드래곤 커브에 포함되는게 조건이라 이 부분도 파악하고 있어야합니다. 헷갈릴만한 부분들인것 같습니다. 구현 디테일 다음 세대에 포함될 점들을 찾아내는게 메인 파트입니다. 저는 항상 배열의 마지막 점이 다음 세대 드래곤 커브를 만드는 기준점이 되도록 다음 세대 점을 계산할 때 뒤쪽 점부터 계산했습니다. 기준점을 기준으로 시계방향 90도 회전한 점의 좌표 계산식만 헷갈리지 않고 작성하면 될 것 같습니다. 끝! 코드 def solution(input) ..
