기록

문제 보기 이 문제는 DFS 문제이다. N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성해야 한다. 모든이라는 글자가 나오면 자연스럽게 완전 탐색(Brute Force)을 생각하게 된다. 또한 자연수 N의 범위가 크지 않아서 완전 탐색으로도 충분히 구현 가능할 것이라고 생각하였다. 시간제한이 충분하지 않을 때는 BFS를 많이 사용하지만 여유로우면 DFS를 즐겨 사용한다. 해당 문제는 위에서 말했듯이 시간제한이 여유로웠으며 순차적으로 연산('+', '-', '')을 삽입하는 DFS가 가장 구현하기 편해 보였다. 알고리즘 구현 과정은 아래와 같다. 1. 1 ~ N의 값을 갖는 리스트를 생성한다. 2. 숫자 사이에 연산을 대입한다. ('+', '-', '' 모든 경우를 고려한다) 3..

문제 보기 이 문제는 DFS 문제이다. DFS를 구현하는 것은 어렵지 않았으나, 시간 초과를 해결하는 부분이 쉽지 않았다. 알고리즘 1번부터 N번까지 순서대로 탐색을 시작한다. 해당 번호에서 DFS 탐색을 시작한다. (지나간 부분은 같은 팀으로 가정) 위에서 탐색한 방향의 역순으로 탐색하면서 사이클을 확인한다. (-1을 대입) 역순으로 탐색하면서 -1로 채워지지 않은 부분은 팀을 이루지 못한 것이라고 생각하면 된다. 처음에는 역순으로 탐색하지 않고, 팀을 관리하는 별도의 배열을 만들어서 append, in 연산자를 활용하였다. 그 결과 80%에서 시간 초과가 발생하였다. 시간을 절약하면서 최소한의 탐색을 할 수 있는 방법이 무엇이 있을까 생각해보니 역순으로 탐색하는 방법이었다. 코드 import sys ..