본문 바로가기

🔎 Algorithm/💻 문제 풀이16

[백준] 1987. 알파벳 풀이 모든 경우의 수를 DFS로 탐색하며 이전에 방문한 알파벳인 경우 가지치기를 진행하엿다. 이 때 이전 방문 노드를 확인하는 방법으로 초기에는 ArrayList를 사용했지만 시간초과가 발생하였고 이에 대한 이유가 ArrayList의 remove 과정에서 O(N)의 시간복잡도가 발생했기 때문이라고 판단하였다. 그래서 이전 방문 알파벳을 유지하는 방식을 StringBuilder를 사용하였고 마지막 인덱스를 삭제함으로써 시간 초과를 해결하였다. 하지만 이 방법도 너무 느려서 이를 확인하는 방법으로 비트마스킹을 사용하였고 모든 경우에 distance를 비교하는 것이 아니라 유망하지 않은 경우에만 distance를 비교하도록 개선하였다. 비트마스킹으로는 현재 알파벳 - 'A'를 해줌으로써 포함 여부를 확인하였다.. 2021. 2. 19.

[백준] 3109. 빵집 풀이 DFS를 통해 탐색을 진행할 때 최대값을 찾는 경우는 대부분 모든 경우의 수를 확인해야 하기 때문에 유망하지 않은 경우 가지치기하는 백트래킹 방법을 사용할 수 없다. 하지만 이 문제는 시작 점은 가장 위에서부터 연결할 수 있는 경우에는 연결하는 경우가 최선의 방법이 되는 그리디한 접근 방식을 사용하였고 이를 통해 유망하지 않은 경우 탐색을 종료하는 경우 되돌아가는 백트래킹 방식을 사용하였다. 첫번쨰 열의 1번쨰 행부터 탐색을 진행하고, 만약 C번째 행에 도착했다면 이번 시작 위치에서의 탐색을 종료한다. 다음 위치도 동일하게 진행하는데 만약 실패한다고 하더라도 방문한 위치에 대한 체크를 되돌리지 않는다. 왜냐하면 해당 위치에서 파이프를 완성하지 못했다고 하더라도 뒤 선택지에서 해당 방향은 동일하게 실.. 2021. 2. 19.

[백준] 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.

[백준] 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.

이전 1 2 3 다음

티스토리툴바