https://www.acmicpc.net/problem/32721 시간 제한메모리 제한1초1024MB문제건덕이가 설립한 오리 왕국은 1부터 N까지 N개의 도시로 이루어져 있다. 각 도시는 다른 도시로 향하는 일방통행 도로를 단 한 개만 가지고 있다. 왕국을 다스리던 건덕이는 어떤 도시에서 도로를 이용해 도달할 수 없는 도시가 있음을 알아챘다. 건덕이는 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 도로를 최소한으로 수정하기로 했다. 건덕이는 도로를 아래와 같은 방법으로 수정한다. 도시 A에서 출발하는 도로의 목적지를 수정한다. (1 ≤ A ≤ N ) 건덕이를 위해 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 만드는 도로의 최소 수정 횟수를 구해주자! 입력첫째 줄에 도시의 개수 N..

import sysinput = sys.stdin.readlinet = [(-1, 0), (1, 0), (0, -1), (0, 1)]d = [(-2, 0), (2, 0), (0, -2), (0, 2)]def bin_check(): ret = 0 t = 1 for j in range(3, 6): if grid[0][j]: ret |= t t 여기에 찾았던 기록들 set으로 관리해주면 되는데 그 부분 커밋 안해서 사라짐

1. SCC문제1) SCC 구성하기백준 2150번 Strongly Connected Component백준 11097번 도시 계획 : 최소 간선으로 scc를 만족하는 그래프 만들기백준 25488번 토큰 : [★★★] scc별 빨간 카드, 파란 카드에 적힌 숫자의 수 비교하기백준 1506번 경찰서 : [★★] scc마다 최소 비용만 찾아서 다 더하기 2) a에서 b까지 가장 많은 정점을 방문하는 경로백준 1471번 사탕 돌리기 : [★★★] 모든 정점의 진출차수가 1인 그래프백준 19649번 미담 전하기 : 직접 전파자를 포함하지 않아야 하는 조건 처리가 까다로움백준 2152번 여행 계획 세우기 : [★★★] 같은 컴포넌트의 요소들은 크기만 알면 방문한 셈 칠 수 있음백준 4013번 ATM : [★★★★★]..

이걸 그리면 좀 기억하는데 도움이 될까 싶었는데도움은 별로 안 된 것 같고요...

시간 제한메모리 제한10초 / 3128MB / 128MB문제https://www.acmicpc.net/problem/2782로맨틱왕: 최대 16개의 선물나무를 선택하거나, 선택하지 않을 수 있으며 선물나무를 선택할 때마다 왕이 1칸을 이동하는데 소모되는 시간이 1씩 증가한다. 왕은 처음에 1칸 당 1시간의 속도로 이동할 수 있다. 왕이 왕비가 있는 곳까지 제한 시간 내에 가져갈 수 있는 최대 선물의 수를 구하는 문제. 선물나무의 위치에 도착했다고 반드시 선물을 가져가는 건 아니고 선물나무마다 선물을 1개 까지 가져갈 수 있다. https://www.acmicpc.net/problem/8138Tourist Attractions: 1~n까지의 지점을 두고 연결 그래프의 형태로 그려진 관광지에서 1에서 출발해..

1. 외판원 순회 문제(TSP)외판원 순회 문제는 그래프 탐색 문제입니다. N개의 정점이 있을 때, 이 정점들을 중복하지 않고 모두 방문할 수 있는 최적의 방법을 찾는 것이 문제의 목적입니다. 즉, 가장 효율적인 해밀턴 회로를 찾는 문제라고 설명할 수 있습니다. 이 문제는 쿠팡맨들을 비롯한 택배 기사님들의 숙원이기도 합니다. 정해진 지점들을 중복하지 않고 한 번에 가장 빠르게 돌 수 있는 방법을 알 수 있다면 퇴근을 빨리 할 수 있을 거예요. 2. NP-hard하지만 택배 기사는 근무 강도가 높은 직종입니다. 그 이유는 바로 외판원 순회 문제가 다항시간 내에 해결할 수 있는 문제가 아니기 때문입니다. 아직까지 이 문제를 다항시간 내에 해결할 수 있는 알고리즘은 확인되지 않았고, 이 문제를 다항시간 내에 ..

시간 제한메모리 제한1초256MB문제고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’ 현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하지만, 태양이는 나머지 4명을 모두 이기는 방법..

https://www.acmicpc.net/problem/6498시간 제한메모리 제한1초128MB문제엘리어스 감마 코드는 양의 정수로 이루어진 수열을 인코딩 하는데 사용하는 코드이다. 이 문제에서는 0도 인코딩할 수 있게 변형한 코드를 사용한다. 정수 n을 인코딩하는 과정은 다음과 같다.1. n의 비트의 개수를 k라고 한다. 2. 0을 k-1개 쓰고, 그 뒤에 1을 쓴다. 3. 그 다음 n을 이진수로 쓴다.0부터 8까지 숫자를 인코딩한 결과는 아래와 같다.숫자이진수비트의 수Prefix코드0011101111112102010110311201011141003001001100510130010011016110300100111071113001001111810004000100011000 정수 수열을 인코딩하려면, 수..