시간 제한메모리 제한1초1024MB문제코코는 초콜릿 공장을 운영하고 있다. 이 공장의 기계는 초콜릿을 3 * N 크기(가로 N, 세로 3)의 직사각형 덩어리로 생산한다. 코코는 이 덩어리를 floor(3N/2)개의 1 * 2 또는 2 * 1 크기의 초콜릿으로 나누어 판매하려고 한다. 어째서인지 N이 항상 홀수라서, 코코는 1 * 1 조각을 하나 골라서 잘라 먹고 남은 부분을 나누어 팔기로 했다. N의 값과 코코가 먹은 조각의 위치(R행 C열)가 주어졌을 때, 남은 초콜릿 덩어리를 나누는 방법의 수를 계산해보자. 입력첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스마다 N, R, C의 값이 한 줄에 주어진다.1 ≤ T ≤ 1e51 ≤ N ≤ 1e5, N은 홀수1≤ R ≤ 3, 1 ≤ C ≤..

1. 최대 유량(Network Flow) 문제최대 유량 문제는 유량이 시작되는 소스(source)와 유량이 도착하는 싱크(sink)가 존재하는 그래프에서 최대로 생성될 수 있는 유량을 찾는 문제입니다. 그래프의 간선들을 타고 유량이 흐르는데 보통 방향 그래프가 다뤄지는 경우가 많으나 방향이 없는 그래프가 주어지기도 합니다. 각 간선들은 흐를 수 있는 유량의 제한인 용량(capacity)이 있습니다. 이 문제를 해결할 수 있는 방법을 처음 제안한 두 사람의 이름을 딴 포드-풀커슨 알고리즘이 있습니다. 이 알고리즘은 방법론에 대한 내용이고 에드몬드-카프 알고리즘에서 O(VE^2)의 BFS를 통한 유량의 증가 경로 탐색 방법이 제시되었습니다. 이후 레벨 그래프를 활용해 O(V^2E)로 개선한 디닉(디니츠) 알..

1. 세포 자동자(Cellular Automata)세포 자동자(CA)란, 유한하게 정의된 상태를 가질 수 있는 셀을 규칙적으로 배치하여 서로 관련있는 셀들이 영향을 주고 받으며 변화하는 모형을 말합니다. 뭐라고 복잡한데 이런 문제가 있어요.백준 7569번 : 토마토"익은" 상태의 토마토가 인접한 "익지 않은" 상태의 토마토를 익게 하는 규칙입니다. "토마토가 없는" 상태의 칸은 영향을 받지 않습니다. 이 문제는 3차원으로 나열된 각 칸이 셀이 되고 토마토가 익었거나 익지 않았거나 없는 3가지 상태를 갖는 세포 자동자라고 볼 수 있습니다. 2. 생명 게임(Game of Life)존 콘웨이가 만든 게임입니다. 이 게임은 초기 상태만 정해주면 그 뒤는 규칙에 따라 알아서 흘러가는 감상 게임이에요. 존 콘웨이는..

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에서 출발해..