알고리즘
-
[백준] 14502. 연구소알고리즘/백준 2021. 4. 5. 01:56
문제 출처 https://www.acmicpc.net/problem/14502 문제 설명 2차원 좌표계에 벽과 바이러스가 있다. 바이러스는 확산되지만 벽은 통과할 수 없다. 3개의 벽을 더 세워서 바이러스를 최대한 억제해라. 문제 풀이 지도가 최대 8x8로 아담하다. 3개의 벽을 세울 수 있는 모든 경우의 수를 도전해봐도 충분할 것이다. 3개의 벽을 세웠다면 바이러스를 확산시키고 안전 구역을 센다. 안전 구역의 최댓값을 출력한다. 왜 모든 경우의 수를 도전해봐도 충분한가? 최악의 경우 8x8에 3개의 벽을 세울 수 있는 경우의 수는 64C3 = 41,664 이고 8x8의 지도를 41,664번 순회한다면 2,666,496회의 연산이 필요하다. 이런 식의 어림짐작으로 1억을 넘지않는다면 백준의 1초를 통과할..
-
[백준] 4963. 섬의 개수알고리즘/백준 2021. 4. 4. 23:02
문제 출처 https://www.acmicpc.net/problem/4963 문제 설명 바다와 땅이 있다. 인접한 땅들은 한 개의 섬이다. 섬의 개수를 세어라. 문제 풀이 완전 탐색으로 땅을 찾는다. 땅을 찾으면 인접한 모든 땅을 너비 우선 탐색으로 방문 표시한다. 땅을 찾은 횟수가 섬의 개수가 된다. 코드 코드 해설 public static void main(String[] args) throws IOException { readInput(); while (!(R == 0 && C == 0)) { int answer = getIslandCount(); System.out.println(answer); readInput(); } } 항상 메인문은 심플하게. 1. 입력을 받는다. 2. 계산한다. 3. 출력..
-
[백준] 7562. 나이트의 이동알고리즘/백준 2021. 3. 31. 01:55
문제 출처 https://www.acmicpc.net/problem/7562 문제 설명 나이트는 체스 말의 나이트처럼 움직인다. 2차원 좌표계에서 탐색하는 문제다. 문제 풀이 bfs로 해결한다. 코드 코드 해설 public static void main(String[] args) { readInput(); for (int tc = 0; tc < testCase; tc++) { int answer = bfs(tc); System.out.println(answer); } } readInput()에서 모든 입력을 받는다. 테스트케이스만큼 bfs를 연산하고 결과를 출력한다. Queue queue = new LinkedList(); queue.offer(knight[tc]); while (!queue.isEmpt..
-
[백준] 1657. 숨바꼭질알고리즘/백준 2021. 3. 30. 22:59
문제 출처 www.acmicpc.net/problem/1697 문제 설명 1차원 좌표계에서 경로를 탐색하는 문제다. 문제 풀이 bfs로 풀었다. 현재 있는 점에서 갈 수 있는 모든 방향을 큐에 넣는다. 큐에 목적지가 있다면 결과를 출력하고 종료한다. 코드 코드 해설 public static void main(String[] args) { readInput(); int answer = bfs(); System.out.println(answer); } 메인은 항상 직관적으로 구성한다. 1. 입력을 받는다. 2. 연산한다. 3. 결과를 출력한다. public static int move(int x, int method) { switch(method) { case 0: return x - 1; case 1: r..
-
[릿코드] 1806. Minimum Number of Operations to Reinitialize a Permutation알고리즘/leetcode 2021. 3. 28. 18:13
문제 출처 https://leetcode.com/contest/weekly-contest-234/problems/minimum-number-of-operations-to-reinitialize-a-permutation/ 문제 설명 짝수인 양의 정수 n이 주어진다. 크기가 n인 수열 perm은 perm[i] == i이라고 초기화한다. (단, 0-indexed. i는 0부터) 수열 perm에 대해 연산을 1회 실행하면 새로운 수열 arr은 각 i에 대해 다음과 같이 정의한다. i % 2 == 0라면, arr[i] = perm[i / 2]이다. i % 2 == 1라면, arr[i] = perm[n / 2 + (i - 1) / 2]이다. 처음의 perm에서 연산을 몇번 해야 다시 처음의 perm으로 돌아오는 지..
-
[릿코드] 1805. Number of Different Integers in a String알고리즘/leetcode 2021. 3. 28. 14:33
문제 출처 https://leetcode.com/contest/weekly-contest-234/problems/number-of-different-integers-in-a-string/ 문제 설명 문자열이 하나 주어진다. 문자열 안에 있는 정수의 갯수를 구하여라. 중복되는 정수는 하나로 세어라. 문제 풀이 정규표현식으로 정수처럼 보이는 모든 부분 문자열을 구한다. 부분 문자열을 정수 형태로 변환하고 Set에 담는다. Set의 크기를 구한다. 코드 코드 해설 Pattern pattern = Pattern.compile("[0-9]+"); 정규표현식을 위한 클래스이다. 정수의 패턴은 "[0-9]+"라고 할 수 있다. Matcher matcher = pattern.matcher(word); Matcher는 ..