본문 바로가기

🔎 Algorithm21

[백준] 15686. 치킨 배달 풀이 얼핏 보면 경우의 수가 많아보이지만 결국 따져야 하는 경우의 수는 치킨집의 개수 중에 M개의 조합을 뽑는 경우다. 모든 경우에 대해 집과의 거리를 구하고 최소값을 구하는 방식으로 진행하였다. Next Permutation 방법을 통해서 조합을 생성했고 이전 최소값을 넘어서는 경우 거리 계산을 중지하고 리턴되도록 구현하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; public class Solution15686 { static class Pair { int x = 0; int y =.. 2021. 2. 19.

[개념 정리] 순열, 조합, 부분집합 이번 글에서는 모든 경우의 수를 탐색하는 완전탐색 기법에서 순열과 조합 그리고 부분집합에 대한 구현 방법을 정리해보고자 합니다. 순열 순열은 N개의 원소 중에서 R개의 원소를 통해 순서를 가진 부분집합을 만드는 경우의 수입니다. 순열은 재귀 함수를 통해 모든 경우의 수를 구할 수 있습니다. 재귀함수를 사용하게 되면 이번 순서의 원소를 사용하는지 체크하는 과정이 필요한데, 이 과정은 boolean 배열을 통해 체크하거나 비트 마스킹을 통해 구현할 수 있습니다. Boolean 배열 사용 permutationByBoolean(0); static void permutationByBoolean(int cnt) { if (cnt == N) { printPermutation(); return; } for (int i.. 2021. 2. 19.

[백준] 9251. LCS 문제 풀이 하루종일 이 문제만 붙들고 있었던 것 같다. 처음 시도했던 방법은 일차원 배열을 통해 메모이제이션을 수행하고자 했다. 하지만 일차원 배열을 사용하는 경우에는 같은 문자가 여러번 등장할 경우에 대해서 잘못된 최대값을 얻는 경우가 발생한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int[][] cache; public static void main(String[] args) thro.. 2021. 2. 10.

[백준] 11053. 가장 긴 증가하는 부분 수열 문제 풀이 처음으로 접근했던 방법은 index를 통해 메모이제이션을 수행하려고 했다. 하지만 같은 수가 존재할 경우 갱신하는 과정에서 일관된 규칙을 찾을 수 없었고 이를 커버하기 위해 index가 아닌 실제 값을 통해 메모이제이션을 수행했다. 앞에서부터 순서대로 해당 값 A를 찾고 1 ~ A-1까지의 최대 길이 + 1로 증가하는 부분 수열의 최대 길이를 저장했다. import java.util.Scanner; public class Solution11053 { static Scanner sc = new Scanner(System.in); static int[] cache = new int[1001]; public static void main(String[] args) { int N = sc.nextIn.. 2021. 2. 10.

[백준] 9663. N-Queens 문제 풀이 처음에는 완전탐색으로 접근했었지만 시간초과로 실패하였다. 그래서 경우의 수를 줄이기 위한 방법을 고민했고 모든 행/열이 아닌 어차피 한 행에는 하나의 Queen만 올 수 있다는 점을 이용해 재귀함수의 깊이를 줄일 수 있었다. import java.util.Scanner; public class NQueens { static Scanner sc = new Scanner(System.in); static int result = 0; static int N = 0; static boolean[][] check; static int[] dx = {0, 0, -1, 1, 1 ,1 , -1, -1}; static int[] dy = {-1, 1, 0 ,0, -1, 1 , 1, -1}; public sta.. 2021. 2. 5.

[백준] 2493. 탑 문제 풀이 처음에는 배열의 끝에서부터 탐색을 시작해서 자신보다 큰 값을 만날 때까지의 모든 요소들을 같이 초기화하는 방식을 생각했다. 하지만 이 경우에는 아래 방향의 화살표 모양(ex. 5 2 1 3 4) 경우를 커버하지 못해서 다른 방법을 생각해봤다. 최종적으로는 스택 두개를 사용해서 하나의 스택(A)은 입력 순서대로 들어가 있고 나머지(B)는 꺼낸 값을 저장했다. 꺼낸 값을 B 스택에 넣기 전에 B스택의 top이 더 작은 경우에는 꺼낸 값의 인덱스가 top의 결과가 된다. 인덱스를 찾는 방법에 대해서는 Map을 통해서 초기 입력시 해당 값을 key로 인덱스를 value로 저장해서 O(1)로 찾을 수 있도록 했다. Map을 통한 구현 import java.io.BufferedReader; import .. 2021. 2. 4.

이전 1 2 3 4 다음

티스토리툴바