백트랙킹5 [알고리즘] 감소하는 수 (백준 1038번) 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 백트랙킹을 이용하는 브루트포스 문제이다. 나올 수 있는 최대 감소하는 수가 9876543210이다. 그렇기에 나올 수 있는 최대 감소하는 수들의 개수를 계산해보면 총 1023개가 나온다. 즉 백트랙킹으로 1023번만에 풀 수 있기 때문에 매번 모든 경우의 수를 구하여도 시간초과가 절대 나지 않기 때문에 모든 경우의 수를 구하여 정렬한 다음 list[N]을 출력 혹은, 1023보다 같거나 큰 수가 N으로 입력되면 -1을 출력하면 된다. Solutio.. 2020. 11. 11. [알고리즘] 단어 수학 (백준 1339번) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 나올 수 있는 알파벳 종류가 10가지이므로 백트랙킹으로 모든 순열을 구해도 된다. 순열을 구할 때 허용되는 최대 시간복잡도가 10!인데 알파벳이 딱 10가지이기 때문이다. 하지만 수학 수식을 활용해서 그리디 하게 풀면 훨씬 쉽게 풀 수 있다. Solution 'ABC', 'BCD' 라는 문자가 있다고 가정해보겠다. 이 두가지 문자를 수학 수식으로 나타내면 'ABC' : 100A + 10B + 1C 'BCD' : 100B + 10C + 1D 로 표현된다. 그.. 2020. 10. 21. [알고리즘] 2048 (Easy) (백준 12100번) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 삼성 기출 문제인데 정말 삼성스러운 문제라고 할 수 있다. 시뮬레이션 + 브루트 포스 문제다. 이전의 다른 삼성 기출 문제들과 마찬가지로 맵에서 여러 물체를 동시에 움직이는 것을 구현해야한다. Solution 1. 전역 변수 var N = 0 lateinit var map : Array var max = 0 val UP = 0 val DOWN = 1 val LEFT = 2 val RIGHT = 3 상하좌우를 나타내는 상수들과 그 외의 .. 2020. 10. 5. [알고리즘] 외판원 순회 2 (백준 10971번) 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회, 일명 TSP라고 불리는 문제다. 외판원은 모든 도시를 최소 비용으로, 단 한 번 방문한 도시는 다시 방문할 수 없다는 조건 하에 순회하게 된다. (마지막 도시에서 출발 도시로 돌아오는 경우 제외) 도시를 방문하는 순서 케이스들을 찾아야 하기에 순열을 구하는 문제다. 이 경우는 N의 크기가 10 이하이기 때문에 백트랙킹으로 모든 경우를 찾을 수 있다. Solution 백트랙킹으로 순열을 구할 때와 조합을 구.. 2020. 10. 4. 이전 1 2 다음
