본문 바로가기

백트래킹

BaekJoon 1339 단어 수학 2019. 2. 8. Link https://www.acmicpc.net/problem/1339 소스결과 1988 KB / 1716 ms 출처 Baekjoon 언어 C++ 17 분류 수학 백트래킹 설명 단어로 된 수학 문제를 푸는 숙제를 받은 민식이를 도와주자. 각 알파벳에 대해서 0 ~ 9 사이의 숫자를 대입했을 때 합이 최대는 값을 찾아주자 백트래킹으로 풀기에는 생각보다 간당간당한 문제 처음에는 사용되는 알파벳에 9부터 역순으로 값을 대입해 보는 방법을 사용했지만 결과는 시간초과 TC조차도 상당히 오랜 시간이 걸렸다. 두번째로 선택한 방법은 사용되는 알파벳이 최대 10개이기에 10개에 맞춰 저장을 하고 각 값에 대해서 값을 지정하고 모든 값이 지정이 된다면 값을 치환해 결과를 구하는 방식으로 구했다. 두번째 방법이 되려 ..
BaekJoon 1342 행운의 문자열 2019. 2. 8. Link https://www.acmicpc.net/problem/1342 소스결과 1984 KB / 260 ms 출처 Baekjoon 언어 C++ 17 분류 백트래킹 탐색 설명 문자열 S의 문자를 재 배치 하였을 때 모든 문자가 인접한 문자와 같지 않은 문자열의 개수를 찾는 문제 문자열을 재 배치 할 때 현재 위치를 기준으로 양옆을 생각하지 않고 이전 문자가 무엇 이었는지만 기억 하면 된다. 문자열을 진짜로 재 배치 한다는 생각보다 앞자리부터 하나씩 문자를 넣어 간다는 점이면 충분하다. 백트래킹을 연습하기에는 괜찮은 문제 문제 조건에서는 문자열의 범위가 주어지지 않지만 테스트 케이스로 주어지는 문자는 알파벳 소문자에 한정되었다. 알고리즘 1. 주어진 문자열의 각 알파벳의 개수를 저장한다. 2. 0번 인..
BaekJoon 2661 좋은수열 2019. 1. 21. Link https://www.acmicpc.net/problem/2661 소스결과 1988 KB / 0 ms 출처 Baekjoon, KOI 1997 언어 C++ 17 분류 수학, 백트래킹 설명 1, 2, 3으로 이루어진 수열 중 인접한 두개의 부분 수열이 동일한 하지 않은 최솟값 수열을 출력하는 문제이다. 첫 자리를 제외하고 나머지 자리는 2번씩 검색해야하는 느낌이 드는 문제이다. 시간 제한이 1초인 점이 의심스럽다. 하지만 위 문제는 간단히 생각하면 앞자리가 1인 경우가 항상 최소가 되는 수열이다. 수열을 검사하는 부분을 최대한 간략화 시키기만 한다면 쉽게 문제가 풀린다. 알고리즘 1. 수를 입력받는다. 2. 현재 위치의 문자 값을 1 ~ 3 사이로 설정한다. 2 - 1. 0번 인덱스를 제외한 나머지..

티스토리툴바