전체 글
-
[SWEA] S/W 문제해결 기본(2) - Ladder 2Algorithm/SWEA 2020. 4. 16. 17:25
[1211] Ladder 2 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh 100 X 100 크기의 2차원 배열로 주어진 사다리에 대해서, 모든 출발점을 검사하여 가장 짧은 이동거리를 반환하는 코드를 작성하라. 모든 사다리 경로에 대해 최소 거리 구하는 문제 Solution Ladder 1문제와 달리 지정된 도착점이 아닌 모든 도착점에 대해 사다리 타기를 하고 count가 최소인 출발점 return 소스코드 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 3..
-
[SWEA] S/W 문제해결 기본 (2) - Ladder 1Algorithm/SWEA 2020. 4. 16. 16:51
[1210] Ladder 1 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 100 X 100 크기의 2차원 배열로 주어진 사다에 대해서, 지정된 도착점에 대응되는 출발점 X를 반환하는 평면상에 사다리는 연속된 '1'로 표현된다. 도착 지점은 '2'로 표현된다. 어느 사다리를 고르면 X 표시에 도착하게 되는지 구해보자. Solution 목적지점에서 올라가면서 왼쪽 오른쪽 체크 & 방향 전환 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575..
-
[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대의 차량들이 들어오고 나가는 순서를 알고 있다. 차가 주차장에 도착하면 진용이는 주차 공간이 있는지 검사한다. 비어있는 공간이 있으면 진용이는 곧바로 주차를 시키며, 주차 가능한 공간 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 빈 주차 공간이 있으면 진용이는 곧바로 주차를 시키며, 주차 가능한 공간 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만약 주차를 기다리는 차량이 여러 대라면, 입구의 대기장소..
-
[Web] SPA(Single Page Application)Programming/Web 2020. 4. 2. 16:26
기존의 웹 서비스 기존의 웹 서비스는 링크(앵커 )를 클릭하면 해당 페이지로 이동하게 된다. 앵커에 명시되어있는 자원(일반적으로 html)을 서버에 요청하고 응답으로 받으 내용을 브라우저에 표현하게 된다. 이런식으로 매 페이지 마다 서버에 문서를 요청하고 응답받아서 표현한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 MAIN main sub1 sub2 MAIN This is main page. Colored by Color Scripter cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 SUB1 main sub1 sub2 SUB1 This is sub 1 page. Co..