본문 바로가기
반응형

backtracking3

[C/C++] 백준 #2210 숫자판 점프(집합, 백트래킹) #2210은 실버 문제로 난이도는 높지 않습니다. 백트래킹 알고리즘을 이용해서 모든 경우의 수를 찾아내었고, 집합을 이용해서 중복을 제거해서 풀었습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 기본적으로 2차원 배열에서 백트래킹은 경계조건하고 상하좌우 움직임 등만 잘 처리하면 큰 무리가 없습니다. 집합 자료구조는 C++에서 제공하는 것이 두가지인데, 일반 집합 자료구조는 se.. 2023. 4. 17.
#1342 행운의 문자열(Back tracking) 이번 문제는 주어진 문자열에 대해서 인접하는 문자가 같은 경우가 없도록 배치할 수 있는 경우의 수를 출력하는 것입니다. 예를 들어서 aabb 란 문자열이 주어진다면, 서로 인접한 문자가 같지 않게 배치될려면, abab baba 두가지 경우가 가능하겠죠. 그러면 2를 출력하면 됩니다. 난이도는 Gold III인데, 딱히 어려운 문제라는 생각은 안 들었습니다. 제 경우에는 빈도를 계산해서, 그 빈도를 이용해서 백트래킹 기법을 이용해서 모든 경우를 계산했습니다. 동적 프로그래밍으로 중복을 줄여서 계산할 수도 있을 것 같기는 했지만, 그건 포기했습니다. 문자열 길이가 10밖에 안 되니까 어찌어찌 가능할 것 같기는 하지만요. 문자가 소문자로만 주어지는지 몰라서 처음에 빈도로 계산 안 하고, 정렬을 통해서 해결했었.. 2020. 1. 26.
43. 프로젝트 오일러 #43 : 부분 문자열 나누어 떨어지기 이번 문제도 간단한 문제입니다. (난이도 5%) 문제 자체는 팬디지털(0~9까지의 숫자를 한번씩만 쓴 숫자)의 부분 문자열이 특정 소수로 나누어지는 가를 판별하면 됩니다. 가장 손쉽게 구현할 수 있는 방법은 백트랙킹(back tracking) 방법을 사용합니다. 속도를 조금이라도 빠르게 하기 위해서 숫자를 만들 때, 세개의 숫자를 쓰는 것이 아니라, 기존의 값에 10을 곱한 후 새로운 값을 더하는 방식으로 구현했습니다. (사실 그다지 이것에 의해서 속도 차이가 발생하지는 않을겁니다.) 간단한 형태의 자기호출 함수를 사용해서 만들었습니다. 소스에 대한 설명은 굳이 필요하지는 않을 듯 하네요. #include #include uint64_t SumPD(uint64_t n, int mask, int t); i.. 2016. 5. 25.
728x90