이녀기의 자유 탐구

noj.am/1562 백준 1562번 계단 수 문제이다. 문제) '계단 수'는 인접한 숫자간의 차가 모두 1인 수를 가리킨다. 자연수 N이 주어졌을 때, N자리 계단 수 중 0~9 모든 숫자가 등장하는 계단 수의 개수를 출력하세요. 풀이) 처음엔 N 이하인 모든 계단수의 개수를 계산하는 줄 알고 백트래킹을 생각했다. 그런데 문제를 다시 읽어보니 0~9 모든 숫자가 들어가야한다는 조건이 있어서 함수 인자로 used라는 set을 추가했다. 그럼에도 TLE(시간초과)가 나서 백트래킹으로 풀기 적합하지 않은 문제란 생각이 들었다. 백트래킹으로 계산하면 0~9가 모두 들어가지 못하는 케이스를 불필요하게 많이 체크하기 때문에 비효율이 발생한다. 문제에서 집중할 부분은 크게 3가지이다. "지금까지 결정한 자리(dig..

noj.am/15651 기본적인 백트래킹 문제이다. 이전에 공부해본 알고리즘들 외에 새로운걸 접하면서 이전에 공부했던 내용을 되짚는 것이 낫다고 생각해 백트래킹을 골라 연습삼아 풀었다. C의 string이 Python에 비해 불편하기 때문에 비트마스킹을 이용하려 했다. 그러나 이 문제에서는 중복이 존재하고, 순서가 존재하기 때문에 적합한 풀이가 아니란 생각이 들었다. 순서가 존재하는 것은 int[7]을 만들고 배열의 합을 갖고 계산하여 중복없이 풀어낼 수 있으나, 중복이 존재하기 때문에 더하는 아이디어가 적합하지 않다고 생각했다. 그럼에도 문자열을 이용하고 싶진 않았다. Python이라면 문자열을 이용해도 되고 배열을 이용해도 되지만, C로 문자열 없이 어떤 것을 만들 수 있을까 생각하다가 10진법으로 ..

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그려보면서 일반화했는데, 틀렸다고 나와서 예외를 찾느라 시간을 소모했다. integer 범위를 넘어가서 문제가 생긴걸 확인하곤 고쳐서 금방 풀었다. 문제) 나선 모양으로 놓인 삼각형의 변의 길이를 구하여라. 놓인 삼각형 중 가장 긴 변에 그 변의 길이를 한 변의 길이로 하는 삼각형을 놓는다. (1

www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 오랜만에 PS를 했다. DP 문제로 하나 풀려했는데, 정답률에 맞게 난이도가 쉬웠다. 문제) 0번째, 1번째 피보나치 수를 0, 1로 정의한다. 20 이하의 자연수 n을 입력했을 때, n번째 피보나치 수를 출력하시오. 풀이) 간단한 dp문제. 1차원 배열로 DP 테이블을 정의하고, 메모이제이션을 이용한 다음 입력받은 n을 인덱싱해서 출력하면 된다. C 코드) #includ..