문제https://www.acmicpc.net/problem/2573 해설BFS를 이용하여 해결할 수 있었다. melting, multipartite 검사, BFS로 각 스텝을 구성하였다. 녹는 빙하에 대해서는 loop를 줄이기 위해 BFS에서 녹아야 하는 빙하의 좌표를 미리 입력받았다. Pythonfrom sys import stdinfrom collections import dequecommand = [[-1, 0], [0, -1], [0, 1], [1, 0]]def bfs(graph: list, visited: list, start_x: int, start_y: int, melt_list: list): queue = deque() queue.append([start_x, start_y])..
문제https://www.acmicpc.net/problem/1707 해설DFS와 BFS 모두 사용가능한 문제이다. DFS를 이용하는 것이 개인적으로 이번 문제에선 이해가 잘 되었던 것 같다. PythonPython은 파이썬의 기본 재귀 깊이 제한은 1000이기 때문에 setrecursionlimit를 사용하지 않으면 런타임 에러가 발생한다. 너무 크게 설정해도 메모리 오류가 발생하므로 적절한 크기로 조절이 필요하였다. DFSfrom sys import stdin, setrecursionlimitsetrecursionlimit(100000)def dfs(graph: list, visited: list, colors: list, node: int, color: int): visited[node] = ..
문제https://www.acmicpc.net/problem/2667 해설DFS와 BFS 모두 사용하여 풀이가 가능한 문제라고 한다. 두 방법 모두 이용하여 풀어보았다. 아직 실력이 초보에 가까워 직관적으로 구현하려고 노력하였다. 이 문제는 DFS가 더 적절한 방법이라고 생각한다. 이 문제에선 DFS의 탐색 속도가 조금 더 빠르기 때문이다. BFS는 주변의 요소만 판단하며 거의 마지막 그리드까지 하나씩 확인해나가야 한다. 반면, DFS는 하나의 hit를 찾았을 때 한 번에 끝까지 모든 인접 경로를 탐색하는 방식이므로 visited 검사를 통해 BFS보다 좀 더 빠르게 조건문에서 필터가 가능하다. 다만 DFS를 사용하였을 땐 Stack Overflow의 위험이 내재되어 있다는 점은 인지하여야 한다. Pyt..
문제https://www.acmicpc.net/problem/1697 해설최단 경로를 탐색하는 문제이므로 BFS를 사용하였다. Pythonqueue에서 pop하는 과정은 deque 자료구조를 활용하여 시간초과에 관한 문제를 개선하였다. 이후 set을 이용하여 visited를 저장하였지만, 메모리 초과가 발생하였다. 이 부분을 list를 이용하여 최대 사이즈를 지정하여 메모리 초과를 해결할 수 있었다. from sys import stdinfrom collections import dequeMAX = 100001def bfs(start: int, end: int): visited = [False] * MAX visited[start] = True queue = deque([(start, ..
문제https://www.acmicpc.net/problem/1260 해설알고리즘 문제에서 자주 활용되는 DFS와 BFS 구현에 대한 문제였다. 모든 Vertex(정점)을 방문할 땐 DFS, BFS 모두 사용하여도 무관하지만 경로의 특징에 따라 처리가 되는 문제라면 DFS를 사용하는 것이 유리하다. 반면 최단거리를 구하는 문제는 BFS를 사용하는 것이 유리하다. 깊이 내려가지 않고 가까운 곳에서 탐색할 수 있기 때문이다. 참고로 간선은 Edge라고 표현한다. Pythonfrom sys import stdindef dfs(graph: list, start: int, visited: list): dfs_result.append(str(start)) visited[start] = True fo..
논문 링크: https://arxiv.org/abs/1409.3215 Sequence to Sequence Learning with Neural NetworksDeep Neural Networks (DNNs) are powerful models that have achieved excellent performance on difficult learning tasks. Although DNNs work well whenever large labeled training sets are available, they cannot be used to map sequences to sequences. In this paparxiv.org 1. 서론1.1 논문 선정 이유자연어 처리 분야에서 가장 강력한 모델로 평가받..
