본문 바로가기

Algorithm

백준 14502 연구소 Java 2019. 6. 18. 완전 탐색 문제인 연구소이다. 1번은 벽이고 2번은 바이러스이고 0번은 아무것도 아니다. 2번 바이러스는 상하좌우가 0번인 경우에만 계속해서 옮겨간다. 1번인 벽을 3개 더 삽입해서 얻을 수 있는 안전 영역(0의 개수)을 출력하면 되는 문제이다. 1을 3개 삽입하는 것은 백트래킹으로 모든 경우를 해보면 되고 바이러스가 퍼지는 것은 BFS로 구현한다. 바이러스가 다 퍼졌다면 0의 개수를 세서 가장 0의 개수가 많이 나올 때를 출력하면 된다. 정리하자면 1. 1이 들어갈 수 있는 모든 경우를 백트래킹으로 해본다. 2. 1이 3번 삽입 됐을 때 바이러스를 BFS로 퍼트려본다. 3. 0의 개수를 세서 최대값을 출력한다. 주의할 점은 바이러스를 퍼트릴 때 입력받은 a배열에 퍼트릴 경우 다음에 오는 경우들을 체크할..
백준 2580 스도쿠 Java 2019. 6. 17. N-Queen과 함께 백트래킹하면 떠오르는 문제라는 스도쿠 문제이다. 스도쿠는 다들 아는 것 처럼 하나의 행에서 1~9, 하나의 열에서 1~9, 3*3 사이즈의 행렬에서 1~9가 있어야 한다. 처음에는 유튜브의 영상을 참고하며 무난하게 백트래킹의 정석대로 문제를 풀었었다. 스도쿠의 규칙을 어기는지 검사하는 check 메소드를 하나 만들어 0을 만났을 때 1부터 9까지 숫자를 넣어보며 check가 true일 때 다음 단계를 진행했다. 0을 만날때 마다 1~9까지 가능한 수를 삽입하고 다시 검사하기 때문에 시간 초과가 나왔다. check 메소드를 보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static boolean check(int..
백준 2437 저울 Java 2019. 6. 14. 한 개의 저울이 있고 N개의 저울 추가 있을 때 N개의 저울추를 사용해서 측정할 수 없는 무게의 최솟값을 출력하는 저울 문제이다. 이분 탐색으로 풀면 될 것 같다고 생각했지만 그리디 알고리즘으로 분류된 만큼 다른 해법이 있을 거라 생각했다. 그리고 어떤 무게에 대해 측정할 수 있는지 없는지를 체크하는 메소드를 어떻게 짤까 고민을 많이 했다. 근데 생각해보면 그리디 알고리즘 문제에서는 대부분 그런 복잡한 과정 없이 생각지도 못한 방법으로 간단히 문제가 풀린다. 이 문제 역시 그런 문제였다. 해법은 간단하다. 입력받은 N개의 저울추를 오름차순으로 정렬한 뒤 저울이 측정할 수 있는 무게의 최솟값인 1부터 저울추 i번 부터 N번까지를 비교하면 된다. 최솟값인 1이 저울추 i번으로 측정 할 수 있다면 최솟값에 저..
백준 1138 한 줄로 서기 Java 2019. 6. 13. 그리디 문제에서 만난 한 줄로 서기 문제이다. N제한이 10인 걸보고 백트래킹이나, 순열로 완전 탐색을 할까 고민했지만 그리디적인 해법으로 풀어보려고 노력했다. 문제를 간단히 설명하면 N명의 사람이 있을 때 앞에 자기보다 키 큰 사람이 몇 명 있는지 키가 1인 사람부터 N인 사람까지 주어진다. 꽤 오랜 시간 고민했지만 해답은 무척 간단했다. 키가 큰 순으로 생각하면 된다. 4 2 1 1 0으로 주어졌을 때 키가 큰 순으로 입력받은 키 대로 ArrayList에 삽입해주면 된다. 키가 4인 사람 -> 0 0번째에 삽입 -> [4] 키가 3인 사람 -> 1 1번째에 삽입 -> [4, 3] 키가 2인 사람 1 1번째에 삽입 -> [4, 2, 3] 키가 1인 사람 2 2번째에 삽입 -> [4, 2, 1, 3] 생..
백준 9663 N-Queen Java 2019. 6. 13. 백트래킹 문제에 대명사라고 할 수 있는 N-Queen 문제이다. 나는 백트래킹이 아직 어렵기 때문에 여러 가지 버전의 풀잇법을 봤었는데 이해하기 어려운 버전이 태반이였다. 어차피 어려운 거 가장 빠른 걸로 완벽히 이해해보자 하고 내가 본 것들 중에 가장 빠른 것을 테스트해본 결과 백준 님의 풀이가 가장 빨랐다. 그래서 백준님의 풀잇법으로 정리해보려고 한다. 문제 설명을 간단히 하자면 입력받은 N*N의 체스판에서 N개의 퀸이 서로 공격하지 않게 놓을 수 있는 경우의 수를 출력하는 문제이다. 다 알겠지만 체스에서 퀸은 위의 그림처럼 상하좌우, 양쪽 대각선까지 공격할 수 있는 역할이다. 그림에서도 알 수 있듯이 N이 3인 경우까지는 절대 N개의 퀸을 서로 공격하지 않게 놓을 수 없다. 그렇다면 N이 4인 경우..
백준 2529 부등호 Java 2019. 6. 13. 그리디에서 발견한 문제이지만 그리디로 해법을 찾지 못하고 검색을 해보니 많은 분들이 백트래킹을 통해 풀었길래 백트래킹으로 풀어본 문제이다. 문제는 부등호의 길이 n과 n개의 부등호가 주어지면 그 부등호를 만족하는 정수 n+1개 중에 최솟값과 최댓값을 출력하면 되는 문제이다. 아직 백트래킹이 어렵게 느껴진다. 되돌려서 되추적 하는 것이 핵심이라는 것만 알고 있다. 이 문제에서도 똑같이 적용했다. 백트래킹을 통해 길이가 n+1인 가능한 경우를 모두 재귀 호출로 만들어보고 그 문자열이 부등호를 만족하는지 체크해서 ArrayList에 넣었다. 그 후 첫 번째 값과 마지막 값을 출력하는 방식으로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
백준 2352 반도체 설계 Java 2019. 6. 11. 그리디 문제를 풀다가 만난 반도체 설계 문제인데 그리디적으로 풀려고 노력하다 실패하고 인터넷을 찾아봐도 그리디 알고리즘으로 푼 자료를 찾지 못해서 LIS(가장 긴 증가하는 부분 수열) 알고리즘으로 풀고 정리하려 한다. 하지만 저번에 정리했던 LIS알고리즘으로는 이 문제를 풀 수가 없다. https://dundung.tistory.com/18?category=744408 백준 11053 가장 긴 증가하는 부분 수열 Java 굉장히 유명한 문제라고 한다. 정답률은 37퍼센트 이다. 다이나믹으로 안풀어도 될 것 같아서 시도했다가 수 많은 반례에 짓밟혔던 문제이다. 최대값이 꼭 배열의 마지막에 있는 것이 아닌 10 50 10 20 30 40 이.. dundung.tistory.com 이 알고리즘은 시간 복잡도가..
백준 1759 암호 만들기 Java 2019. 6. 11. 재귀 호출을 통한 완전 탐색으로 해결할 문제인 암호 만들기 문제이다. 암호의 길이 n이 주어지고 c개의 알파벳이 주어진다. 이 c개의 알파벳으로 길이가 n이면서 최소 한 개의 모음과 두 개의 자음을 포함한 암호를 만들면 된다. 우선 문제의 조건대로 알파벳들을 String 배열에 넣고 정렬을 한다. 그리고 재귀 호출을 통해 모든 경우를 탐색해볼 메소드를 작성한다. 필요한 파라미터 변수들은 암호의 길이 -> int n 알파벳 배열 -> String [] alpha 암호 -> String password 인덱스 -> int i 암호를 만들 때 모든 알파벳을 다 써보기 위해서는 두 가지 경우를 메소드에 적어주면 된다. 인덱스 i의 알파벳을 사용하는 경우, 사용하지 않는 경우 이 두 가지의 경우를 모두 재귀 호출..

티스토리툴바