알고리즘 공부

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 문제 상황에서 시작점과 도착점이 동일하게 주어진 경우를 놓쳐서 여러번 틀린 문제이다. 문제 자체는 그렇게 어렵지 않은 BFS문제이다. 내가 작성한 코드 from collections import deque F, S, G, U, D = map(int, input().split()) graph = [0 for _ in range(F + 1)] search = deque() dx = [U, -D] moves = -1 search.append((S,1)) graph[S] = 1 while search: C, T = search.popleft() if C == G: moves = T - 1 break for i in range(2): nC = C + dx[i] ..

분류 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 이런..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS 유형의 문제는 여러가지 유형이 존재한다. 가장 기본 유형은 하나번의 BFS만을 이용하는 경우이며 이런 경우는 대개 그래프가 연결이 되었는지를 체크할 때 주로 사용이 된다. 그러나 해당 유형은 난이도가 낮아서 BFS 익힐 때 푸는 정도이다. 이 문제는 BFS를 여러번 시도를 해야 하는 경우에 대한 인사이트를 제공하는 것 같다. 문제 난이도가 그렇게 높지 않기 때문에 무의식적으로 잘 해결을 할 수 있지만 한번 고민을 해볼 필요는 있다고 생각한다. BFS를 여러번 수행하는 경우에도 아래와 같이 나눌 수 있다고 생각한다. 각각의 BFS를 따로 진행해도 된다. 그리고 서로에게 어떠한 영향도 없다. 각각의 BFS를 따로 진행해도 되지만 서로에게 영향이 있다..

분류 스택 혼자 힘으로 해결 했는가? O 느낀 점 앞서 2493번을 통해 monotone 스택 문제에 대한 감을 잡은 뒤 도전했다. 등급은 골드4로 2493보다 한단계 더 높지만 둘 다 난이도가 똑같이 느껴졌다. 다만 이 문제는 2493과 달리 검사의 대상이 되는 숫자가 담긴 배열의 역순으로 진행을 해야했다. 아마 현재 값의 우측 값에 관심이 있기 때문에 우측부터 시작해서 현재 값을 기준으로 선행 된 값 중 나보다 큰 값이 처음으로 나오는가? 이렇게 문제를 해결하기 때문인 것 같다. 그리고 이 문제에서 중요한 키워드는 현재 값을 기준으로 오른쪽 값 중에서 가장 왼쪽에 있는 큰 값 이라고 생각한다. 위의 말을 다시 풀어서 쓰면 나보다 우측에 있는 값 중에 처음으로 발견되는 큰 값 따라서 스택을 써서 처음으..

분류 스택 혼자 힘으로 해결 했는가? X 느낀 점 스택 문제를 많이 풀지 않았기 때문에 억지로 스택을 활용하려고 하다가 시간 초과를 맞이했고 결국 실패했다. 스택 하나만으로 이 문제를 어떻게 해결해야하는지 감이 오지 않아 구글링을 해 보았고 Monotone 스택 유형임을 알게 되었다. 그와 동시에 이 문제에서 제시하는 사고 흐름은 반드시 익혀야겠다는 생각을 했다. 내가 작성한 코드 오답 import sys from collections import deque N = int(input()) tower = list(map(int, sys.stdin.readline().rstrip().split())) stack = deque() for i in range(N): tower[i] = (tower[i], i +..