문제 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요. 제한사항 1 ≤ x ≤ y ≤ 1,000,000 1 ≤ n
PPS(Algorithm)/DFS BFS
오늘 푼 문제는 백준 1759 암호 만들기다. [백준] 1459. 암호 만들기 시도1 → 실패 아이디어 첫 시도는 단순하다. 조합으로 숫자를 뽑아서 출력하려고 했다. 그러나 조합이 너무 많았고 결과도 제대로 나오지 않았다. 코드도 복잡하고 for문을 너무 많이 돌았다. 나중에 해설 코드를 보고 이상하게 풀었음을 알았다… 코드는 다음과 같다. from itertools import permutations, combinations #서로 다른 L개의 알파벳, 문자의 종류는 C개 있다. 가능성 있는 암호는 총 몇개? # import sys # input = sys.stdin.readline l,c = map(int, input().split()) candidate = list(input().split()) m..
먼저 문제는 다음과 같다. https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 먼저 이 문제는 DFS 문제이다. 다만 적록색약의 경우 빨간색과 초록색을 구별하지 못하기 때문에 DFS를 하기 전 빨간색과 초록색을 한가지 색으로 통일시킨 다음 DFS를 하도록 했다. 즉, 처음에 DFS를 적용하고 그 다음에 색을 통일한 다음 다시 DFS를 하면 해결되는 문제이다. DFS 구현은 recursion 방식으로 하였다. 여기서 중요한 점은 pyth..
코딩테스트 준비하는 Notion Link https://joowhan.notion.site/PPS-Coding-Test-74f06c5242df4f67807d765869394bb4 기억해야 하는 것은, 1. DFS는 깊이 탐색이다. 2. DFS는 Stack을 이용한다. 그걸 알면서도 막상 문제를 풀려고 하면 잘 모르겠다. 이 문제는 처음에 풀지 못해서 풀이 영상을 보고 다시 풀었다. DFS에서 중요한 것은 재귀함수를 통해 stack을 사용한다는 것이며 이는 잘 알고 있었지만, 이 문제의 핵심은 DFS했을 때 방문한 node의 수까지 알아야 한다는 것이다. 이 부분을 어떻게 해야 하는지 잘 몰랐는데, 해결책의 간단하다. return 값을 1로 준 다음 재귀함수에서 나왔을 때에 이 return 값을 더해주면 ..
