https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net - 다이나믹 프로그래밍 - 알고리즘 - 1. 전체 맵의 오른쪽 아래를 기준으로 정사각형의 왼쪽 위라고 가정한다. 2. counts[][] 배열을 만들어서 그 지점을 좌측 상단으로 하는 가장 큰 정사각형이라고 정의한다. 3. counts[a][b] = min(counts[a+1][b],counts[a][b+1],counts[a+1][b+1])+1 -시간 복잡도- 맵의 총크기 : O(n) * O(n) 각 경우당 4번씩 탐색. 따라서 총 시간 복잡도 = 4 * O(n) *..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net - 그냥 구현하는 문제. 문제 조건대로 풀면 된다. -시간 복잡도- O(n) - 예외 조건 - 1. 사람이 기준치에 미치지 못하여도 감독관이 들어가야 한다. -소스 코드- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std;..

https://www.acmicpc.net/problem/6359 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고 www.acmicpc.net - dp 문제. - 알고리즘 - 입력받은 방의 수에서 가장 큰 걸 골라서 그 방수까지 dp를 수행. dp 수행 식 1 2 3 if (..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 www.acmicpc.net - 이진 탐색 문제. - 알고리즘 - 1. 숫자카드 n개와 숫자카드 m개를 배열로 입력받는다. 2. n배열을 정렬한다. 3. m만큼..

- bfs 알고리즘 -시간 복잡도- O(|V|+|E|) - 알고리즘 - 1. 처음 내가 있는 위치를 queue에 넣는다. 2. U, D을 사용해서 bfs를 돌린다. 3. 원하는 위치에 들어왔다면 종료 후 그 배열 값에 저장된 값을 출력한다. - 예외 조건 - 1. bfs를 다 돌렸는데도 G를 방문하지 못했다면 계단으로 가도록 한다. 2. node에 방문하지 않는 조건을 visited [now]가 0일 때로 했으므로 처음에 들어가는 값의 visited는 1로 넣어주고 답에서 1을 빼주어야 한다. 계속 메모리 초과가 나와서 이유를 알 수 없었는데, queue에 넣는 조건을 visited [now]가 1일 때로 지정해 놓아서 메모리 오류가 나고 있었다. 새로 알게 된 사실인데 변수 이름을 g, d, u, f,..

dfs로 푸는 문제 노드를 하나씩 돌면서, 각각의 노드가 갈 수 있는 최대 횟수를 벡터에 저장한다. 처음에는 배열로 만들었지만, 최대 크기가 10000*10000이나 되서, 연결 여부를 배열로 만들면 시간 초과가 나온다. 또, 방문 여부를 판단하는 배열을 한 번씩 돌 때마다 초기화 시켜주어야 한다. 처음에는 초기화 시켜주지 않았지만, 최대길이가 짧은 노드부터 방문하게 된다면 최대 방문 순위를 재대로 셀 수 없게 된다. 풀이 과정 1. vector 배열을 만들어, from을 index로, to를 vector 배열에 push 한다. 2. 연결된 두 쌍을 찾아, dfs를 돌린다. 그 후 진행하는 횟수를 arr배열에 저장한다. 3. 오름차순 정렬이므로, arr배열에서 max값을 찾아 그와 동일한 값을 갖는 배열..