본문 바로가기

Algorithm/SWEA

(10)
[SWEA-5656][BFS/백트래킹] [모의 SW 역량테스트] 벽돌 깨기 - Java SWEA에 있는 모의 SW 역량테스트 문제입니다. 쪼끔 번거로워 보이는데 백트래킹도 쓰고 BFS도 쓰고 재밌는 문제랍니다. import java.io.*; import java.util.*; public class Solution { static class Dir{ int y, x; Dir(int y, int x){ this.y = y; this.x = x; } } static int[] dy = {-1, 0, 1, 0}; static int[] dx = {0, 1, 0, -1}; static int N, W, H, answer = Integer.MAX_VALUE; static int[][] map; public static void main(String[] args) throws IOException ..
[SWEA-1251][MST/Prim] 하나로 - Java 문제를 딱 보면 아~~ 얘는 MST를 만들어야 하는구나~~ 하는게 딱 느껴집니다. MST를 만드는 알고리즘 중에서 Prim's 알고리즘을 사용해봤습니다. import java.io.*; import java.util.*; public class Solution { static class Node{ int to; long weight; Node(int to, long weight){ this.to = to; this.weight = weight; } } public long Prim(List graph) { boolean[] v = new boolean[graph.size()]; long[] minEdge = new long[graph.size()]; Arrays.fill(minEdge, Long.MAX_..
[SWEA-3234][백트래킹] 준환이의 양팔저울 - Java 백트래킹 문제입니다. 문제의 제한 사항에 맞게 안되는 경우는 걍 안가면 됩니다. 시간이 빡빡하게 매겨집니다. 그래서 별짓 다해봤습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Solution { int N; int ans; void dfs(int cnt, int[] w, boolean[] v, int l, int r) { if(cnt == N) { ans++; return; } f..
[SWEA-1238][BFS] Contact - Java 인접 리스트를 만들고 BFS로 퍼져나가면서 단순히 방문 여부만 체크하는 것이 아니라 언제 방문했는지를 체크해줌으로써 풀 수 있는 문제입니다. 인접 리스트를 구현하는 방법에는 크게 2차원 배열을 이용하거나 연결 리스트를 이용할 수 있는데, 이 문제는 정점의 최대 개수가 101개(1~100)이기 때문에 이번에는 오랜만에 간단히 배열을 사용해서 만들어 보아씀니다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { static int [][] graph; static int[] dy = {0, 0, 1, -1}; static int[] dx = {1, -1, 0, 0}; stat..
[SWEA-9229][DFS] 한빈이와 Spot Mart - Java 한빈이라는 친구가 과자 두 봉지를 사서 가는데 들고 갈 수 있는 최대 무게를 구하는 문제입니다. N개 중에서 반드시 두 개를 선택해야 하므로 조합(Combination)을 이용해서 풀면 됩니다. import java.util.Arrays; import java.util.Scanner; public class Solution { static int[] snacks; static int[] selected; static int answer; static int M; private static void dfs(int cnt, int s) { if(cnt == 2) { int sum = Arrays.stream(selected).sum(); if(sum > M) return; answer = answer > s..
[SWEA-1223][스택] 계산기2 - Java 입력값으로 중위 표기식이 들어오면 이를 후위 표기식으로 바꾸고 계산하는 문제입니다. 스택을 이용해서 후위 표기식으로 바꾸고 계산까지 하면 됩니다. 괄호없이 덧셈과 곱셈만 있기 때문에 상대적으로 쉬운 문제랍니당. import java.util.Scanner; import java.util.Stack; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = 10; for(int test_case = 1; test_case
[SWEA-1225][큐] 암호생성기 - Java 앞에 놈을 빼서 일련의 연산을 해준 뒤 다시 뒤에 넣는 동작을 하기 때문에 기본적인 큐 활용 문제입니다. 규칙을 잘 생각해서 코드를 짜고 언제 반복문을 나갈지 조금만 생각해보면 쉽게 풀 수 있답니당. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = 10; for(int test_case = 1; test_case
[SWEA-1218][스택] 괄호 짝짓기 - Java 기본적인 스택 활용 문제입니다. 처음에는 인풋으로 들어온 괄호문자들을 전부다 스택에 넣고 빼면서 어째저째 해볼랬는데 생각이 안나서 하나하나씩 봐주면서 넣고 빼고 했습니다. import java.util.Scanner; import java.util.Stack; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[] left = {'(', '', '}', ']'}; for(int test_case = 1; test_case