알고리즘
-
[백준]1000. A + B (java, python)알고리즘/백준 2021. 4. 19. 14:15
📄 링크 A + B 💡 문제 분석 가장 기초 문제 입력 받고 더해서 출력합니다 ⌨️ 코드 JAVA import java.util.Scanner; public class Q1000 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); System.out.println(a + b); } } PYTHON a, b = map(int, input().split()) print(a + b)
-
[백준]17289. 오큰수 - Java알고리즘/백준 2021. 2. 19. 01:17
📄 링크 boj 17298. 오큰수 💡 문제 분석 N * N으로 모든 경우를 비교하면 시간 초과가 납니다 O(N) 방법 순서대로 스택에 숫자를 넣을 때, 스택에 숫자가 들어있다면 현재 넣을 숫자와 비교해 봅니다 만약 현재 넣을 숫자가 더 크다면, 스택에 있는 숫자들의 오큰수는 현재 넣을 숫자가 됩니다 마지막 숫자까지 스택에 넣었다면 모든 오큰수를 구한 것이 됩니다. ⌨️ 코드 public class _17298_오큰수 { static class Pair { int idx, n; Pair(int idx, int n) { this.idx = idx; this.n = n; } } public static void main(String[] args) throws IOException { BufferedReade..
-
[백준]1987. 알파벳 - Java알고리즘/백준 2021. 2. 19. 01:16
📄 링크 boj 1987. 알파벳 💡 문제 분석 모든 알파벳을 한 번씩만 지날 수 있기 때문에 , A ~ Z까지 26개의 알파벳을 체크하기 위해 불린 배열을 만듭니다 시작지점부터 dfs를 돌며 현재 칸에서 갈 수 있는 4방향 중 가장 큰 값이 답입니다 bfs를 사용하게 된다면 모든 경로를 탐색하지 않아서 실패하게 됩니다 ⌨️ 코드 public class _1987_알파벳 { static int r, c; static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; static char[][] s; static boolean[] chk; public static void main(String[] args) { Scanner sc = new Scanner(System.in)..
-
[백준]17135. 캐슬 디펜스 - Java알고리즘/백준 2021. 2. 19. 01:14
📄 링크 캐슬 디펜스 💡 문제 분석 M열 중에 궁수를 배치할 3열을 뽑습니다. (조합) 게임을 할 때마다 원래 배열을 유지해야 하기 때문에 미리 복사를 하고 시작합니다 가장 아래 행부터 한 칸씩 위로 올라가며 궁수 위치 한 칸 위에서 BFS로 제거할 적을 선택합니다 bfs 거리를 늘려가며 사정거리보다 커지면 종료시킵니다 왼쪽 적을 우선적으로 선택하기 때문에, 방향 배열의 순서가 중요합니다 동시에 같은 적을 쏠 수 있기 때문에 미리 체크를 해놓고 한꺼번에 제거했습니다 가장 많은 적을 없앤 경우를 출력합니다 ⌨️ 코드 public class _17135_캐슬디펜스 { static int N, M, D, ret = 0; static int[] pick, dy = {0, -1, 0}, dx = {-1, 0, 1..
-
[백준]9663. N-Queen - Java알고리즘/백준 2021. 2. 17. 23:55
📄 링크 N-Queen 💡 문제 분석 N * N 크기의 체스판 위에 N개의 퀸을 놓아야 하는 문제입니다 1행부터 N행까지 내려가며 행마다 하나의 퀸을 놓는 방식으로 하기로 했습니다 여기서 어떤 열에 퀸을 놓을 지 정할 때 이미 놓은 퀸들과 왼쪽 대각선, 오른쪽 대각선, 세로가 겹치면 안됩니다. (1, N - 1)에서 오른쪽 대각선 방향으로 가장 밑으로 갔을 때 2 * N - 1 까지 갈 수 있기 때문에 대각선 배열은 2 * N - 1의 크기로 할당해 주었습니다. ⌨️ 코드 public class _9663_Nqueen { static int N, ret = 0; static boolean[] diag1, diag2, col; public static void backtracking(int cnt){ if..
-
[백준]2206. 벽 부수고 이동하기 - Java알고리즘/백준 2021. 2. 17. 23:50
📄 링크 벽 부수고 이동하기 💡 문제 분석 (1, 1) 에서 (N, M)까지 최단경로를 찾는 문제입니다. 일반적인 BFS와 같지만 벽을 딱 한 번 부술 수 있다는 점이 다릅니다. 어떤 벽을 부숴야 최단 거리로 갈 수 있는지 모르기 때문에 그냥 다 부숴보기로 합니다. dist[4][2][1] = (4, 2)에 벽을 한 번 부수고 도달했을 때 최단거리입니다, dist[4][2][0]이라면 벽을 안 부수고 도달했기 때문에 한 번의 기회가 남아 있다는 것을 알 수 있습니다 bfs를 돌면서 길이 있다면 그냥 가고 없다면, 벽을 부순 적이 없다면 부수고, 부순 적이 있다면 가지 못합니다. 그리고 따로 방문처리 배열을 만들지 않고, dist 배열이 갱신된 적이 있다면 그냥 넘어가도록 합니다 ⌨️ 코드 public c..
-
[백준]12865. 평범한 배낭 - Java알고리즘/백준 2021. 2. 17. 23:50
📄 링크 평범한 배낭 💡 문제 분석 최대 K 무게를 담을 수 있는 배낭에 물품들을 담을 때, 가치를 가장 크게 할 수 있는 방법을 구하는 문제입니다. 일단 물품 수 100개 중에 몇 개인지 모를 물품을 골라 무게를 비교하는 완전탐색은 당연히 시간 초과가 날 것 같아서 메모이제이션를 사용하기로 했습니다 일단 물품들을 배열에 저장합니다. cache[idx][weight] = 배열의 idx 인덱스 이후의 물품들을 사용해서 weight 무게 내로 가질 수 있는 최대 가치입니다. idx를 하나씩 늘려가며 현재 물품을 가방에 넣을 때와, 넣지 않을 때 중 가치가 높은 것을 cache 배열에 저장합니다 0번 인덱스부터 K의 무게로 시작하는 메모이제이션 함수를 출력합니다 ⌨️ 코드 public class _12865_..
-
[백준]16639. 괄호 추가하기 3알고리즘/백준 2021. 1. 10. 23:58
[백준]16639. 괄호 추가하기 3 📄 링크 괄호 추가하기 3 💡 문제 분석 수식을 입력받고 여기에 괄호를 임의로 추가하여 최대값을 구하는 문제입니다 이 문제의 핵심은 괄호를 마음대로 넣을 수 있기 때문에 연산자의 우선순위는 아무런 의미가 없다는 것입니다. 그렇기 때문에 괄호를 넣을 수 있는 모든 방법으로 완전 탐색을 진행하고 캐시에 저장해서 해결하였습니다 하지만 이 문제에서 *연산을 할 때 음수 * 음수를 했을 때 가장 큰 수가 나올 수 있기 때문에 가장 작은 값들도 계속 저장을 하고 있어야합니다. Calc(max, max) Calc(max, min) Calc(min, max) Calc(min, min) 4가지 계산을 모두 해서 가장 큰 수는 max 캐시에, 가장 작은 수는 min 캐시에 저장합니다 ..