[기하] 두 직사각형의 겹치는 영역 확인하기
·
PS/Algorithm
직사각형의 위치를 다음과 같이 두 점의 좌표로 표현하자.두 직사각형 (x1, y1), (x2, y2)와 (x3, y3), (x4, y4)가 있다.(x1 두 직사각형이 겹치는 영역은 다음과 같이 표현할 수 있다. [cpp]int area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0); [python]area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)
AtCoder Beginner Contest 361 F - x = a^b
·
PS/AtCoder
ABC361의 모든 문제 중 가장 짧고 가장 이해하기 쉬운 문제였으나 간단한 설명과 달리 꽤나 치밀한 아이디어가 필요했고 그걸 떠올리는 과정이 재밌어서 정리를 남겨본다.시간 제한메모리 제한2초1024MB문제1이상 N이하의 정수 x에 대하여 어떤 정수 a와 2이상의 정수 b로 x = ab로 표현 가능한 것은 얼마나 있는가? 입력입력은 아래 형식의 표준입력으로 주어진다.N 조건입력은 전부 정수이다.1 ≤ N ≤1018출력답을 정수로 출력하시오. 입력예199 출력예112문제의 조건을 만족하는 정수는 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81으로 12개다. 입력예21000000000000000000 출력예21001003332 풀이조건에 맞는 정수인 a의 b거듭제곱 꼴로 나타내어..
모듈러 연산의 역원(분수의 모듈러 연산)
·
기타
1. 모듈러 기본 연산모듈러 연산은 나머지를 구한다. 파이썬에서는 산술 연산자 %와 같다. 10 mod 3 = 10 % 3 = 1. 두 수 a, b에 대해 어떤 수로 모듈러 연산을 했을 때 결과가 같다면 a, b는 모듈러 합동이라고 한다. 합동 기호를 똑같이 사용하고 예를 들어 이런 식으로 표기한다.13 mod 4 = 1 (13을 4로 나눈 나머지는 1이고) 9 mod 4 = 1 (9를 4로 나눈 나머지도 1이다.) 13 ≡ 9 mod 4 ()보통 0 이상의 정수에만 모듈러를 사용하는 경우가 많다. 실제로 나머지가 있는 나눗셈은 초등학교 수준의 수학에서만 다루고 있다. 하지만 괴물같은 수학자들이 이런 연산을 0 이상의 정수에만 사용하게 냅둘리가 있나. 모듈러는 음수에도 적용할 수 있다. 음수로 확장된 모..
2642 전개도 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초128MB문제아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자. 전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다. 입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오. 입력입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나타낸다. 출력입력된 전개도를 정육면체로 접을 수 있으면, 정육면체에서 1번으로 표시된 면의 맞은 편 면의 번호를 출력하고, 정육면체로 접을 ..
최대유량 문제에서 정점 분할
·
PS/Algorithm
1. 정점이 용량을 갖는 유량 그래프최대유량 문제에서는 간선으로 용량 정보가 주어진다. 근데 만약 정점에 용량이 있다면? 음의 유량 처리 과정에 문제가 생긴다. 포드 풀커슨의 방법에서 가장 핵심적인 아이디어는 음의 유량을 만들어 기존 유량을 우회시키는 테크닉이다.정점 중심으로 생각해보면 정점 3은 나가는 방향의 간선 용량의 총합인 3의 용량을 갖는다고 할 수 있다. 1→3의 유량 2를 우회시키면 s-2-3-5-t에 2의 유량을 흘려보낼 수 있다. 여기서 유량 우회가 가능한 이유는 유량을 간선 정보로 관리하고 있기 때문이다. u-v 간선 용량을 capa[u][v], u-v 간선의 현재 유량을 flow[u][v] 라고 표현하면 그래프 자체에서 u와 v의 순서로 간선의 방향 정보를 모두 관리하고 있는 셈이다...
9576 책 나눠주기 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한2초256MB문제백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다. 조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다. 백준이가 책을 줄 수 있는 최대 학생 수를 구하시오. 입력첫째 줄에 테스트 케이스..
14750 Jerry and Tom (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초512MB문제https://www.acmicpc.net/problem/14750풀이다양한 알고리즘이 혼합된 문제다. 하지만 기본 개념 적용만 잘하면 까다로운 부분은 없어서 어렵지 않게 해결 할 수 있는 문제!..(맞나?) 문제에서 요구하는 것은 쥐구멍에 들어갈 수 있는 최대 쥐의 마릿 수다. 쥐는 쥐구멍까지 이어지는 일직선 상에 다른 벽과의 어떤 접점도 없어야만 해당 쥐구멍에 들어갈 수 있고, 각 쥐구멍에는 도망갈 수 있는 쥐의 수 제한이 있다. 우선은 쥐가 어떤 쥐구멍으로 도망갈 수 있는지 확인해야 한다.  1. 선분 교차 판정으로 쥐와 쥐구멍의 연결 여부 확인쥐의 위치를 m, 쥐구멍의 위치를 h, 벽의 양 끝 점을 a, b라고 하면 아래 그림과 같은 상황에서 ccw 값을 얻을 ..
와와와 솔브닥 1000솔브
·
기타
와와와우 예아아아
아 진짜 언제쯤 대회 전참 가능한거냐
·
기타
A 패널티 16먹은 것도 빡치지만 일 때문에 제대로 참여 못하고 맨날 패널티 퍽퍽먹는거 너무 싫다D풀고 E푸는데 10분 밖에 안걸렸는데F도 7분만에 코드 다 짰는데 다 짜고 제출 누르니까 404 뜨네 와아ㅏ아아가악아가각대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!! 대학생 때 할껄...1!!
13161 분단의 슬픔 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초512MB문제UCPC에는 N명의 사람이 있다. 먼 옛날 쇼킹핫치킨에 대한 논쟁에서 시작된 이념의 대립으로 UCPC에는 kriii를 따르는 쇼킹핫진보 진영 A와, august14를 따르는 쇼킹핫보수 진영 B의 두 진영이 존재한다. 모든 사람은 둘 중 한 진영에 소속되어 있으며, 두 진영에 동시에 들어가는 것은 불가능하다. i번 사람과 j번 사람에 대해 서로 다른 진영에 들어가게 될 경우 슬픈 정도 w[i, j]가 주어진다. 일부 사람들은 쇼킹핫에 관한 자신의 철학이 강해 무조건 A진영에 들어가는 사람도 있고, 무조건 B진영에 들어가는 사람도 있다. 물론 치킨은 무엇이든 옳으므로 두 진영 어디에 가든 상관없는 사람도 있다. N명의 사람들이 적절히 두 진영에 나누어 들어갈 때, 슬픔 정..
최대 유량(Network Flow), 디닉(Dinic's) 알고리즘
·
PS/Algorithm
지난 글에 이어서 더 빠른 최대 유량 알고리즘인 디닉 알고리즘.에드몬즈-카프는 bfs를 활용하며 O(VE2) 안에 문제를 해결할 수 있다. 간선에 대한 지수시간이기 때문에 정점의 수와 무관하게 간선이 여러 개라면 bfs에서 너무 많은 시간을 소모하게 된다. 하지만 디닉은 정점에 대한 지수시간 O(V2E) 안에 문제를 해결한다.디닉 알고리즘의 순서는 이렇다.유량 그래프 = G, source = s, sink = t1. G의 레벨그래프 L을 만든다.  a. s로부터 t까지의 bfs로 깊이는 각 정점의 레벨이 된다.  b. t의 레벨이 정의되지 않으면 모든 작업을 멈춘다.2. L에서 다음 작업을 반복한다.  a. dfs로 s→t의 증가경로를 찾는다.  b. 증가경로의 최소 컷을 찾아 경로에 유량을 생성한다.3..
최대 유량(Network Flow), 에드몬즈-카프(Edmonds-Karp) 알고리즘
·
PS/Algorithm
1. 최대 유량 문제정점 간에 흐를 수 있는 양이 있을 때 그 최대치를 간선으로 표현하면 하나의 방향 그래프가 나온다. 두 정점 사이에 흐를 수 있는 최대 양을 용량(capacity), 두 정점 사이에 흐르고 있는 양을 유량(flow), 현재 남아있는 용량을 잔여용량(residual)이라고 한다. 예를 들어 파주에서 안양에 이르는 수도권 서부의 도로 교통용량을 대충 다음과 같이 표현할 수 있다.(실제로 이런 상황에다가 써먹지는 않는 듯 하다.)그렇다면 이 그래프 외의 다른 연결을 전부 무시하고 모든 도로가 전부 비어있다고 가정했을 때 파주에서 안양까지 이어지는 도로 교통용량의 최대치는 얼마일까?자유로에서 서부간선도로를 타면 파주-일산-고양-서울-안양으로 이어진다. 이 경로에 따르면 일산~고양 구간이 용량..
전라남도교육지원청
맞았습니다!!
상단으로

티스토리툴바