SY DevLog

13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 처음에 각각의 A[n]에 대하여 무조건 총감독 1명은 필요하므로 cnt를 하나 증가시키고, A[n]에서 총감독이 감독하는 B명을 빼었다. -> A[n] - B 그리고 난 후, A[n] - B를 부감독이 감독할 수 있는 응시자 수인 C로 나누어서 몫을 cnt에 더하고, 만약 나머지가 존재하면 그 나머지 응시자도 감독을 해야하므로 cnt를 하나 더 증가시켰다. 그런데 결과는 '틀렸습니다.' 가 떴다. 내가 놓친..

10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 어느 한 도시에서 출발하여 모든 도시를 거친 후, 처음으로 돌아오는 문제이다. 여기서 알아야 할 사실은 어느 도시에서 출발하든 가장 적게 드는 비용은 동일하다는 것이다. 따라서 아무나 한 곳을 시작도시로 정해서 dfs를 사용하여 시작한 곳으로 돌아오면 된다. 모든 도시를 한 번씩만 방문해야하므로 visited 배열을 이용하여 방문 여부를 표시한다. 그런데 문제를 풀면서 한가지 헷갈렸던 점이 있다. 처음 시작한 도시는 이..

1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 이 문제는 이분탐색으로 모든 아이들이 다 놀이기구를 탈 수 있는 최소 시간을 구하여 풀 수 있다. 문제의 예제를 보자. 문제의 예제에서 탑승하는 아이들의 수가 22명이고, 놀이기구가 5개이며 각각의 운행시간이 1,2,3,4,5 이다. 처음 0분에 모든 놀이기구가 비어있으므로 22명 중 5명의 아이들이 각각의 놀이기구에 탑승한다. 그 다음 1분이 지난 후, 비어있는 놀이기구는 1번 놀이기구 하나뿐이다. 따라서 6번째 아이가 1..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 1912번 : 연속합 문제에서 좀 더 발전한 문제이다. 이번에는 주어진 수열에서 연속합을 구하되, 중간에 수 하나를 제거할 수가 있다. 백준 1912번 문제에서는 dp 1차원 배열을 이용하여 문제를 풀었는데, 이번에는 2차원 배열로 만들어서 풀었다. 아래는 백준 1912번 문제 풀이한 링크이다. lotuslee.tistory.com/89 [백준 1912번] 연속합 (java) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 ..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. 다이나믹 프로그래밍은 무엇보다 점화식을 세우는 것이 중요하다. 나는 int[] dp = new int[n]; 로 1차원 dp배열을 생성하였고, dp[n]의 의미는 다음과 같이하였다. dp[n] : n번째 수가 연속합의 마지막일 때, 최대가 되는 연속합 무슨 말이냐면, 입력받은 수열을 배열 arr에 저장한다고 했을 때, arr[0] + ... + arr[n] : 0번째 수부터 n번째 수까지의 연속합 arr[1] + ... + arr[n] : ..

플로이드 워셜 알고리즘 그래프에서 모든 정점들 간의 최단거리를 구하는 알고리즘 다익스트라 알고리즘 비교 다익스트라 알고리즘은 하나의 시작 정점을 정해서 다른 모든 정점까지의 최단경로를 구한다. 반면에 플로이드 워셜 알고리즘은 모든 정점을 시작 정점으로 했을 때의 최단경로를 구한다. 따라서 정점 간의 모든 최단거리를 구할 경우에는 플로이드 워셜 알고리즘을 사용한다. 다익스트라 알고리즘은 가중치가 음수인 경우에는 사용할 수 없다. 플로이드 워셜 알고리즘은 가중치가 음수라도 사용이 가능하다. 플로이드 워셜 알고리즘에 대해 먼저 간단히 설명하면 이렇다. 플로이드 워셜 알고리즘에서 시작정점(s)와 도착정점(e)간의 최단거리를 구할 때, 경유하는 정점(t)에 관한 개념이 등장한다. 경유하는 정점(t)이란, 말그대로..

10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 한바퀴 돌때마다 재귀함수를 호출하여서 arr 2차원 배열에 앉게 될 대기자의 대기번호를 차례대로 넣어준다. solve(int sr, int sc, int r, int c) (sr, sc)는 한바퀴에서 첫번째 시작하는 좌표를 의미하고, r은 세로 길이, c는 가로 길이를 의미한다. 소스코드 :

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 분할하여 같은 동작을 반복하기 때문에 재귀를 이용하여 풀 수 있다. 처음에는 1, 2, 3, 4 분면의 모든 경우의 수를 다 재귀함수 호출을 했더니 시간 초과가 나왔다. 그래서 조건문을 이용하여 (r, c)이 포함된 사각형만 선별적으로 재귀를 실행하도록 변경하였다. 2차원 배열의 정보를 가장 왼쪽 위 좌표(i, j) 와 한 변의 길이 size로 나타낼 때, 이 2차원 배열을 4등분한 각각의 사각형은 다음과 같이 표현이 가능하다. - 2사분면 : (i, j..

시분할 시스템이 생겨나면서 기존의 일괄 작업 시스템보다 프로세스의 상태가 복잡해졌다. 기존의 일괄 작업 시스템과 달리 시분할 시스템에서는 프로세스의 작업 도중에 인터럽트에 의해 CPU를 다른 프로세스에 넘겨주는 경우가 생겨났기 때문이다. 기본적으로 프로세스의 상태는 생성, 준비, 실행, 대기, 완료 (+보류) 5가지로 분류할 수 있다. 생성 상태 프로그램이 메모리에 올라가 프로세스가 되고, 운영체제에 의해 프로세스 제어 블럭(PCB)가 생성된다. 준비 상태 프로세스가 생성되면 바로 CPU에 할당되어 실행되는 것이 아니라 준비 상태에 접어든다. 이 때 PCB는 준비 큐에 들어가며 CPU에 할당될 때까지 자신의 차례를 기다린다. 준비 큐에서 어떤 프로세스가 실행 상태로 옮겨지는가는 CPU 스케줄러에 의해 관..

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 주어진 배열 전체를 가지고 부분수열의 합을 구하면 시간초과가 난다. 그러므로 이 문제를 배열을 두 개로 나누어서 투 포인터 알고리즘으로 부분수열의 합을 구해야 한다. 처음에는 부분수열이 연속해야만 하는 줄 알았는데, 문제를 다시 읽어보니 꼭 연속하지 않은 수열이어도 상관없다는 것을 깨달았다. 알고리즘 1. 먼저 배열을 두 개로 나눈다. (0 ~ N/2), (N/2 ~ N) 예를 들어, 문제 예제에서 주어진 배열이 -7 -3..