Algorithm76 [알고리즘] 감소하는 수 (백준 1038번) 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 백트랙킹을 이용하는 브루트포스 문제이다. 나올 수 있는 최대 감소하는 수가 9876543210이다. 그렇기에 나올 수 있는 최대 감소하는 수들의 개수를 계산해보면 총 1023개가 나온다. 즉 백트랙킹으로 1023번만에 풀 수 있기 때문에 매번 모든 경우의 수를 구하여도 시간초과가 절대 나지 않기 때문에 모든 경우의 수를 구하여 정렬한 다음 list[N]을 출력 혹은, 1023보다 같거나 큰 수가 N으로 입력되면 -1을 출력하면 된다. Solutio.. 2020. 11. 11. [알고리즘] 특정한 최단 경로 (백준 1504번) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 그래프 이론 문제로 1번 노드에서 N번 노드까지의 최단 거리를 구해야 하는데 중간에 V1, V2에 해당하는 노드들을 꼭 거쳐가야 한다. Solution 우선 문제에서 유추할 수 있는 것을 찾아본다면 가중 그래프에서의 최단 경로 다익스트라, 플로이드 와샬 예상 무향 그래프 위상 정렬은 사용 불가 (사이클 o) v1, v2를 무조건 거쳐야 함 (나올 수 있는 최단 경로의 수는 2개) 1 → v1 → v2 → N 1 → v.. 2020. 11. 11. [알고리즘] 택시 (백준 1649번) 1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 2020. 11. 3. [알고리즘] 부분합 (백준 1806번) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 연속된 구간의 합이 S 이상이 되는 구간의 최소길이를 구하라는 문제다. '연속된 구간' 이라는 키워드에서 보면 알 수 있지만 무조건 투포인터 문제다. Solution min_length는 최소길이, sum은 list[before] ~ list[after] 까지의 구간 합이다. 반복문을 돌린다. sum이 S 이상 min_length를 현재 구간길이랑 비교해서 업데이트한다. before < after 이면 sum에서 list[before]를 뺸 후 b.. 2020. 10. 29. 이전 1 2 3 4 ··· 19 다음
