본문 바로가기

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.
[C/C++] 프로젝트 오일러 #43 : 부분 문자열 나누어 떨어지기 Project Euler #43 - Sub-string Divisibility 문제는 특정한 성질을 만족하는 팬디지털(pandigital) 숫자를 찾고, 그들의 합을 구하는 문제입니다.  이번 문제도 간단한 문제입니다. (난이도 5%) 문제 설명 0부터 9까지의 숫자를 각각 한 번씩만 사용하여 만들 수 있는 10자리 숫자를 09 팬디지털 숫자라고 합니다. 예를 들어, 1406357289는 10자리 0~9 팬디지털 숫자입니다.이 문제에서는 단순히 팬디지털 숫자를 생성하는 것이 아니라, 특정한 부분 문자열(sub-string) 이 특정한 소수(prime number)로 나누어지는지를 검사해야 합니다. 구체적으로, 10자리 팬디지털 숫자에서 아래 조건을 만족하는 숫자를 찾아야 합니다. 조건 - 부분 문자열이 .. 2016. 5. 25.

티스토리툴바