Algorithm
-
[SWEA] 올해의 조련사Algorithm/SWEA 2020. 2. 18. 22:58
[5672] 올해의 조련사 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRgX36gSIDFAUo 앵무새들의 첫 글자가 순서대로 주어진다. 새로운 줄 세우기 방법으로 다시 앵무새들을 줄 세웠을 때 얻을 수 있는 가장 빠른 문자열을 알아내자. 새로운 줄 세우기 방법은 다음과 같다. 기존의 줄을 세운 다음 가장 앞 or 뒤에 있는 앵무새를 새로운 줄의 마지막에 새우는 것을 반복하는 방식 Solution 기존의 줄에서 앞 문자와 뒤 문자의 사전 순서를 비교하여 새로운 줄의 끝에 순서대로 넣는다. 사전식 순서가 같은 경우 while() 문을 반복하여 다음에 나오는 문자가 더 작은 앵무새의 이름을 넣는다. 소스코드 1..
-
[SWEA] 수영장Algorithm/SWEA 2020. 2. 15. 15:18
[1952] 수영장 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 김프로는 지출이 너무 많아 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 있다. 이용권 종류 1. 1일 이용권 : 1일 이용가능 2. 1달 이용권 : 1달 이용 가능 3. 3달 이용권 : 3달 동안 이용 가능 4. 1년 이용 가능 이용 계획에 따라 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 비용을 출력하는 문제 Solution permutation()을 사용하는 문제로 알고 풀었는데 풀이 방법이 떠오르지 않아 dp로 풀었다. 평소에 dp 문제 어려워했었는..
-
[BOJ] 캐슬디펜스Algorithm/BOJ 2020. 2. 13. 15:06
[17135] 캐슬디펜스 https://www.acmicpc.net/problem/17135 게임이 진행되는 곳은 크기가 NXM인 격자판이다. 각 칸에 포함된 적의 수는 최대 하나이며, N+1행의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 성이 있는 칸(N+1)에 궁수 3명을 배치하려고 한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적은 아래로 한 칸 이동하며 성이 있는 칸으로 내려간 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 입력 : N(행) M(열) D(거리 제한), NxM(격자판의 상태) 출력 : 궁수의 공격으로 제거할 수 있는 적의 최대 수 Solution permutat..
-
[BOJ] 배열 돌리기 3Algorithm/BOJ 2020. 2. 11. 21:06
[16935] 배열 돌리기 3 https://www.acmicpc.net/problem/16935 d크기가 N x M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1. 상하 반전 2. 좌우 반전 3. 오른쪽으로 90도 회전 4. 왼쪽으로 90도 회전 5, 6. 배열을 크기가 N/2 x M/2인 4개의 부분 배열로 나누어 시계방향, 반시계방향으로 이동 Solution 문제 조건에 맞추어 구현하였다. 하면서 너무너무너무 풀기 싫었다. 소스코드 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..
-
[BOJ] 배열 돌리기 1Algorithm/BOJ 2020. 2. 10. 22:39
[16926] 배열 돌리기 1 https://www.acmicpc.net/problem/16926 배열의 크기(N,M), 회전의 수(R), 배열 정보가 주어졌을 때 배열을 반시계 방형으로 R번 회전시킨 결과를 구하는 문제 Solution 코테에서 자주 나오는 유형이니 외워두자. 시간 안습 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import java.util.Scanner; public class Main { static int n, m, r; static int[] dx = { 0, 1, 0, -1 }; static int[] dy = { 1..
-
[BOJ] 게리멘더링Algorithm/BOJ 2020. 2. 10. 00:53
[17471] 게리멘더링 https://www.acmicpc.net/problem/17471 백준시는 N개의 구로 나누어져 있고, 1번부터 N번까지 번호가 매겨져 있다. 문제 조건 1. 구역을 두 개의 선거구로 나워야 하고, 선거구는 구역을 적어도 하나 포함해야 한다. 2. 한 선거구에 포함되어 있는 구역은 모두 연결되어야 한다. 공평하게 선거구를 나누기 위해 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 위 조건을 만족하는 인구 차이의 최솟값을 구하는 문제 Solution permutation()을 사용한 DFS 풀이 방법 permutation()으로 두 개의 선거구를 나누었고, DFS를 사용해 선거구역의 연결 여부를 확인하였다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
-
[BOJ] 캠프 준비Algorithm/BOJ 2020. 2. 8. 23:15
[16938] 캠프 준비 https://www.acmicpc.net/problem/16938 캠프에 사용할 문제를 고르는 방법의 수를 구하는 문제 N : 가지고 있는 문제 수 L : 문제 난이도 하한 R : 문제 난이도 상한 X : 가장 쉬운 문제와 가장 어려운 문제 난이도 차이 1. 문제는 두 문제 이상 2. 뽑은 문제의 난이도는 L 이상 R 이하 3. 가장 쉬운 문제와 가장 어려운 문제의 난이도 차이는 X와 같거나 커야한다. Solution permutation 활용 문제 문제는 두 문제 이상이어야 하기 때문에 2 ~ N까지 size를 바꿔가면서 permutation() 함수를 돌렸다. 뽑은 문제를 temp 리스트에 담아 문제의 조건에 부합하면 count++를 해주었다. 소스코드 import java..
-
[BOJ] 연구소 2Algorithm/BOJ 2020. 2. 8. 21:51
[17141] 연구소2 https://www.acmicpc.net/problem/17141 바이러스를 놓을 수 있는 칸(arr[i][j] = 2)에 주어진 M개의 바이러를 놓았을 때 모든 빈 칸(arr[i][j] = 0)에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다. Solution permutation()을 사용한 BFS 문제 바이러스를 놓을 수 있는 칸의 좌표를 리스트에 모두 담고, permutation() 함수를 돌려 M개의 좌표를 뽑은 후에 BFS로 바이러스를 퍼뜨린다. 소스코드 import java.util.ArrayList; import ..