Algorithm
-
[SWEA] 초콜릿과 건포도Algorithm/SWEA 2020. 4. 15. 18:50
[9282] 초콜릿과 건포도 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j-qfacIEDFAUY 가로 M, 세로 N 크기의 초콜릿이 있다. i행 j열 격자에는 A(ij)개의 건포도가 들어있으며, 자르기 전 초콜릿에 들어 있는 전체 건포도 t개가 들어있을 경우 이를 자르는 행위의 비용을 t라고 한다. 초콜릿을 자르는 행위를 반복하여 N*M개의 조각으로 자르려고 할 때 최소비용을 구하는 문제 Solution 건포도의 누적합을 미리 구한 뒤 가로자르기, 세로자르기 방법으로 자른 비용의 최솟값을 dp 배열에 저장하는 방법 자르는 행위에 대한 비용이 어떤 조각으로 자르냐에 따라 달라지기 때문에 최소 비용을 dp 배..
-
누적합(Cumulative sum) 2Algorithm/이론 2020. 4. 14. 21:48
2차원 누적합 누적합의 개념을 2차원으로 확장시킬 수 있다. 1차원 배열(arr)은 2차원으로 확장되고, 누적합 수열도 2차원 배열(sumArr) 형태로 확장된다. 직사각형 형태의 배열에 포함되는 직사각형 구간의 모든 원소의 합을 빠르게 구할 수 있다. 2차원 누적합 수열 만들기 a(i, j)에서 가로 방향으로 누적합을 계산해서 s(i, j) 수열이 되고, 계산한 결과를 세로 방향으로 누적합을 구해서 최종적인 S(i, j) 수열이 된다. 2차원 구간합 계산하기 S(i, j)는 위에서 설명한 방법대로 a(i, j) 배열의 누적합을 계산한 배열이다. 초록색으로 표시된 작은 사각형의 구간합을 구하기 위해서는 S(3, 3)에서 시작한다. S(3, 3) 값에서 S(1, 3) 값과 S(3, 1) 값을 뺀 뒤에 S(..
-
누적합(Cumulative sum)Algorithm/이론 2020. 4. 14. 17:12
누적합의 필요성 알고리즘 문제에서 배열의 부분합을 빠르게 구해야 하는 경우에 누적합을 이용하면 연속된 누적합을 O(N)만에 구할 수 있다. 누적합의 성질 1. S(n) = 배열 a의 1번째 요소 부터 n번째 요소까지의 누적합 2. S(1) = a(1) 3. S(i) = S(i-1) + a(i) 4. a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) // 누적합을 활용한 빠른 구간합 계산 1차원 누적합 누적합의 4번 성질을 이용하여 아래 문제들을 해결할 수 있다. 1. 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
-
[SWEA] 시험Algorithm/SWEA 2020. 4. 5. 17:17
[8888] 시험 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW45RuSae2gDFAQ7 시험에 참가하는 N명의 참가자에게 1부터 N까지의 번호가 붙어 있고, 그들은 T개의 문제를 통해서 경쟁한다. 각 문제는 해당 문제를 풀지 못한 참가자의 수를 점수로 가지며, 때문에 대회가 끝나고 나서야 점수가 결정된다. 참가자는 자신이 푼 문제들이 배정된 점수들의 합을 자신의 점수로 가진다. 참가자의 등수는 (자신보다 많은 점수를 획득한 참가자의 수) + (자신과 같은 점수를 획득하였지만 더 많은 문제를 푼 참가자의 수) + (자신과 같은 점수 && 같은 수의 푼 문제 && 번호가 저 작은 참가자의 수) + 1로 결정된다..
-
[SWEA] 진용이네 주차타워Algorithm/SWEA 2020. 4. 5. 14:15
[9280] 진용이네 주차타워 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j74FacD0DFAUY 진용이가 운영하는 유료 주차장의 총 수입을 계산하는 프로그램 진용이는 오늘 주차장을 이용할 m대의 차량들이 들어오고 나가는 순서를 알고 있다. 차가 주차장에 도착하면 진용이는 주차 공간이 있는지 검사한다. 비어있는 공간이 있으면 진용이는 곧바로 주차를 시키며, 주차 가능한 공간 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 빈 주차 공간이 있으면 진용이는 곧바로 주차를 시키며, 주차 가능한 공간 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만약 주차를 기다리는 차량이 여러 대라면, 입구의 대기장소..
-
Merge Sort (합병 정렬)Algorithm/이론 2020. 3. 30. 22:03
Merge Sort 분할 정복 알고리즘의 하나 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략 분할정복은 대개 재귀 호출을 이용하여 구현한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge) 하는 단계이다. Merge Sort는 크기 N인 배열을 입력으로 받아, 배열을 절반으로 두 개로 나눈 후, 각 작은 배열을 재귀적으로 정렬하고, 그 결과를 Merge한다. 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트..
-
[SWEA] 탈주범 검거Algorithm/SWEA 2020. 3. 3. 16:53
[1953] 탈주범 검거 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq Solution 터널 구조에 따라 이동할 수 있는 방향과 다음 터널과의 연결여부를 체크하면서 BFS로 풀이했다. switch문을 더 깔끔하게 풀었으면 좋았을텐데.. 소스코드 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 6..
-
[SWEA] 특이한 자석Algorithm/SWEA 2020. 2. 21. 23:56
[4013] 특이한 자석 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH 하나의 자석이 1 칸 회전될 때, 붙어 있는 자석은 서로 붙어 있는 날의 자성과 다를 경우에만 반대방향으로 1 칸 회전한다. 자석을 회전시키는 방향은 시계 방향이 1, 반시계 방향이 -1로 주어진다. 날의 자성은 N 극이 0으로, S 극이 1로 주어진다. 각 자석의 날 자성정보는 12시방향부터 시계방향으로 순서대로 주어진다. 정답은 K번 회전한 후 획득한 점수의 총 합이다. Solution LinkedList를 활용해서 시계방향, 반시계방향을 구현하였다. 먼저 왼쪽과 오른쪽의 자석이 회전하는지(자성이 다른지) 확인..