본문 바로가기

알고리즘77

[알고리즘] 감소하는 수 (백준 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.
[알고리즘] 부분합 (백준 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.
[알고리즘] 내려가기 (백준 2096번) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍 문제다. 최소, 최대 값을 묻는 문제인데 이전에도 자주 풀어 본 적이 있는 유형이다. Solution 우선 max_dp와 min_dp로 나누어서 각각 최대값, 최소값을 구하는 dp 배열로 만든다. 여기서 최적화할 수 있는 방법은, 최대, 최소값을 구하기 위해서는 max_dp[i][3] 과 max_dp[i-1][3] 만 필요하면 되기 때문에 행이 2개만 있으면 된다. 그래서 max_dp, min_dp 에 필요한 원소 개수는 12개만 있으면 된다. N만큼 반복.. 2020. 10. 29.

티스토리툴바