본문 바로가기
반응형

PS 문제 풀이/SWEA75

[SWEA] 3820 롤러코스터 출처: [SWEA] SW 문제해결 심화 - 증명의 중요성 Input 3 3 3 1 2 2 1 4 5 2 6 1 6 6 3 10 4 7 6 4 1 1 3 2 2 1 2 4 Output #1 14 #2 1242 #3 27 N개의 레일이 존재하며, 각 레일에는 두 개의 자연수 a, b가 주어져 있다. [레일의 속도 변화]: (진입 전) v → (진입 후) av + b ※ 롤러코스터가 출발할 때 차량의 속도 = 1 모든 레일을 지났을 때 차량의 속도를 최소한으로 하고자 합니다. N개의 레일을 적절히 배치하여 최종 속력을 구하시오. - Test Case 개수 T / 레일의 개수 N - (N줄에 거쳐) 레일에 적힌 수 a, b가 주어집니다. N개의 레일을 배열하는 방법은 O(N!) 배치된 레일을 순회하며 최종속력을.. 2021. 3. 1.
[SWEA] 3814 평등주의 출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다.. 2021. 3. 1.
[SWEA] 4062 Largest Empty Square 출처: [SWEA] SW 문제해결 심화 - 동적 계획법 Input 1 4 0100 1001 1000 0101 Output #1 2 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com 『0』과 『1』로 구성된 N×N행렬이 존재합니다. 『0』으로 된 가장 큰 정사각형의 한 변의 길이를 구하시오 - Test Cast 개수 T / 행렬의 크기 N - 행렬 정보가 공백없이 주어집니다. 자세한 풀이는 [BOJ] .. 2021. 3. 1.
[SWEA] 4070 타일링 출처: [SWEA] SW 문제해결 심화 - 동적 계획법 Input 5 1 10 100 200 201 Output #1 1 #2 683 #3 845100400152152934331135470251 #4 1071292029505993517027974728227441735014801995855195223534251 #5 2142584059011987034055949456454883470029603991710390447068501 Dynamic Programming (DP) 이용. - 자세한 풀이는 [BOJ] 1793 타일링 [BOJ] 백준 1793 타일링 출처: https://www.acmicpc.net/problem/1793 Input 2 8 12 100 200 Output 3 171 2731 8451004.. 2021. 3. 1.
[SWEA] 4005 비밀 출처: [SWEA] SW 문제해결 심화 - 그래프 Input 1 10 6 6 3 1 5 7 6 10 5 10 8 3 5 2 4 6 10 3 1 5 10 5 7 9 8 5 6 10 2 3 4 7 5 2 1 3 7 10 9 Output #1 2 2 4 0 2 1 3 1 1 5 10 - Test Case 개수 T / 정점의 개수 N / 간선 정보 개수 M - M 줄에 거쳐 첫번째로는 간선의 개수 그 다음으로 연결되는 정점이 차례대로 주어집니다. (방향 그래프) ex) 6 3 1 5 7 6 10 ← (1 ≤ Mi ≤ N) ▶ 6개 간선 정보: [3] → [1], [1] → [5], [5] → [7], [7] → [6], [6] → [10] 구현 M줄에 거쳐 주어지는 간선 정보들은, 일부분이거나 중복될 수 있기에.. 2021. 3. 1.
[SWEA] 1868 파핑파핑 지뢰찾기 출처: SWEA Input 2 3 ..* ..* **. 5 ..*.. ..*.. .*..* .*... .*... Output #1 2 #2 8 문제에서는 최소 Click 횟수를 구하는 문제입니다. 최대한 연쇄폭파를 많이시켜서 Click 횟수를 최소화 시켜야 합니다. 주어진 Sample Case를 분석하면 『 』표시된 지역에서 '0'으로 표시된 곳 중 하나만 click하면 우측이미지랑 동일한 결과를 얻을 수 있다. 하지만 '1', '2'로 일어난 곳을 처음 Click했다면 연쇄폭발은 일어나지 않기에 최소 클릭 횟수를 만족 못합니다. ① 최소 클릭을 위해서 주위에 지뢰가 없는 지점을 연쇄 폭발 시킵니다. ② 과정 ①이 모두 끝나면 남은 지점(지뢰는 없지만 주변에는 지뢰가 있는)을 Count 합니다. (②에서.. 2021. 3. 1.
[SWEA] 1249 보급로 출처: SWEA Input 2 4 0100 1110 1011 1010 6 011001 010100 010011 101001 010101 111010 Output #1 2 #2 2 BFS 처리할 때, 재방문 여부를 어떻게 할지 고민할 수 있는 문제입니다. 작업시간만 최소비용이라면 실제 거리는 어떻든 상관 없습니다. 여기서 단순히 BFS의 방문표시하여 재방문하지 않으면 최선의 경로가 탐색되지 않습니다. 단순히 방문여부를 확인하는 것이 아니라 해당 지점을 복구 시간이 덜 걸린 경로인지 확인해야 합니다. ①경로로 이미 방문한 곳도 ②경로에서는 작업시간이 덜 걸렸기에 해당 지점에서 재방문 해줘야 합니다. * 일반적인 BFS에서는 boolean visited[][]로 방문여부를 확인하였다면 이 문제는 int dis.. 2021. 3. 1.
[SWEA] 8382 방향 전환 출처: SWEA Input 3 0 0 1 0 -1 -1 0 0 0 0 0 2 Output #1 1 #2 2 #3 4 ①에서 ②로 갈 때, 『가로 이동』과 『세로 이동』 최소 횟수를 출력하는 문제이다. 『가로 이동』은 좌우 이동 / 『세로 이동』은 상하 이동을 의미한다. 이동할 때는 『가로 이동』과 『세로 이동』 순차적으로 이루어진다. (처음 출발은 임의로 지정 가능) Brute Force 이용도 가능하지만 규칙을 이용하여 처리. 위와 같이 ②에 도달하기 위해서는 『가로 이동』 3번만 하면 되지만 규칙상 세로 이동을 중간에 2번(↑ ↓) 하면 된다. ① 좌표 (x1, y1) / ②의 좌표 (x2, y2) 최소 필요한 세로이동 |x2 - x1| → 'rowMove' 최소 필요한 가로이동 |y2 - y1| →.. 2021. 3. 1.
[SWEA] 1974 스도쿠 검증 출처: SWEA Input 10 7 3 6 4 2 9 5 8 1 5 8 9 1 6 7 3 2 4 2 1 4 5 8 3 6 9 7 8 4 7 9 3 6 1 5 2 1 5 3 8 4 2 9 7 6 9 6 2 7 5 1 8 4 3 4 2 1 3 9 8 7 6 5 3 9 5 6 7 4 2 1 8 6 7 8 2 1 5 4 3 9 Output #1 1 스도쿠 검증하는 문제이다. 9x9판에서 아래 구간을 for문으로 차례대로 검사. 각 구간별로 1~9까지 숫자가 중복없이 있는지 확인. import java.util.Scanner; public class Solution { static int tc; static int[][] arr; static boolean[] target; public static void ma.. 2021. 3. 1.
[SWEA] 1954 달팽이 출처: SWEA Input 2 3 4 Output #1 1 2 3 8 9 4 7 6 5 #2 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 N이 주어졌을 때, 방향이 바뀌는 시점과 채워지는 값에 유의하며 구현 - 방향이 바뀌는 시점: 벽면이거나, 이미 숫자가 채워진 경우 - 채워지는 값: 1~N*N import java.util.Scanner; public class Solution { // 달팽이 모양을 그릴 수 있도록 우,하,좌,상 static public int[] dx = {0, 1, 0, -1}; static public int[] dy = {1, 0, -1, 0}; static public int N; public static void main(String[] args).. 2021. 3. 1.
반응형

티스토리툴바