전체 글

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS를 진행할 때, 독립된 그래프의 순회를 해도 되는 상황이다. 우선 BFS 특성 상 동시에 두개의 이동이 가능한 주체에 대한 BFS는 불가능하다. 그러나 이 문제는 이동이 가능한 대상이 둘이다. 따라서 각각 진행을 하되 앞서서 BFS를 진행한 주체의 타임 스탬프와 비교하는 과정이 필요하다. 내가 작성한 코드 from collections import deque # 입력 받기 TC = int(input()) for _ in range(TC): bY, bX = map(int, input().split()) board = [[0 for _ in range(bY)] for _ in range(bX)] visF = [[0 for _ in range(bY)] ..

분류 완전 탐색 혼자 힘으로 해결 했는가? △ (엄청난 삽질을 해서 애매함) 느낀 점 이번 문제를 직접 모두 백트래킹으로 구현을 하려고 하니 너무 실수가 잦았다. 우선 각 칼럼마다 가능한 조합을 만들고 (백트래킹 + for문) 각 조합마다 다시 겹치는지 검사를 위해 다시한번 완전탐색을 사용하고 (2중 for) 만들어진 조합이 최소성을 충족하는지 따지기 위해 다시 백트래킹을 사용했다. 이렇게 구현을 하니 너무 힘이들었다. 이후 다른 분은 어떻게 해결했는지 참고했고 itertools와 set을 활용하는 인사이트를 얻을 수 있었다. 우선 각 칼럼마다 가능한 조합 자체를 itertools로 만들고 (물론 순수 백트래킹으로 만드는 방법도 알아야 한다고 생각한다.) 이후 하나의 칼럼의 조합이 유일성을 만족하는지 체..

분류 스택, 재귀 혼자 힘으로 해결 했는가? △ (예외를 못 잡아서 오래걸림) 느낀 점 스택을 사용하는 문제이나 구현력이 조금 필요한 문제라고 생각한다. 처음에는 재귀로 접근을 했으나 2(1)3(12(2)) 와 같이 완전한 괄호 쌍이 여러개가 나오는 경우를 놓쳤고, 이런 경우까지 해결하기에는 스택을 사용해야 해결이 가능 할 것 같았다. 이를 위해 스택에 앞 부분부터 집어넣고 )를 만난 경우 스택에서 값을 빼서 계산하는 방식으로 구현을 했으나 한가지 발목은 잡은 부분이 이 문제는 딱 봐도 문자열을 직접 만들면서 진행하면 시간초과 or 메모리 초과가 무조건 생길 문제이다. 즉, 나는 중간 값으로 문자열 자체를 활용하면 안되고 길이만을 저장해야 하는데, 562(12(2))와 같은 경우, 스택에 5 6 2 이런..