곰탱이의 공부정리

https://www.acmicpc.net/problem/17070 이 문제는 파이프를 정해진 방식대로 밀어서 끝까지 가는 경로가 몇 개인지 구하는 문제이다. 이 문제에서 파이프는 3가지 상태를 가지고 있다. 가로,세로,대각선이다. 그리고 이 세가지 상태에 따라 다음칸으로 움직일 수 있는 방법이 나뉜다. 가로의 경우에는 가로로 한칸 대각선으로 한칸, 세로의 경우에는 세로로 한칸 대각선으로 한칸, 대각선의 경우에는 가로로,세로로,대각선으로 한칸 움직일 수 있다. 이렇게 움직일 때 꼭 비어있어야 하는 칸들은 아래와 같다.우리는 시작이 있고 끝으로 가는 경우의 수란 점에서 그래프 경로 찾기라는 걸 알게된다. 그렇다면 경로 찾기하면 BFS 아님 DFS인 것을 알 수 있다. 그런데 이 문제의 추가시간이 엄격한걸..

https://www.acmicpc.net/problem/1865  이 문제는 양방향 도로와 단방향 웜홀(시간이 뒤로감) 이 주어지고 이 때 음의 사이클이 존재하는지 물어보는 문제이다. 음의 사이클이 있는지를 알아내려면 벨만-포드 알고리즘을 쓰는 것이 제격이다.   벨만 - 포드 알고리즘은 그래프의 노드의 개수만큼 반복하며, 다익스트라 알고리즘처럼 경유하는 경우가 더 짧을 경우 계속해서 갱신하는 방식이다. 얼핏보면 쓸데 없는 계산을 더하는 것처럼 보이지만, 이 알고리즘의 장점은 이미 그래프의 노드의 개수만큼 반복하여 최적의 거리를 구했다고 생각했을때, 한번 더 돌려서 이때 최적경로가 갱신된다면, 음의 사이클이 생긴 것이라는 것을 알아챌 수 있단 점이다.   필자는 본디 처음엔 거리 리스트를 math.in..

https://www.acmicpc.net/problem/1238  이 문제는 단방향 엣지가 주어진 그래프에서, 모든 노드에서 특정 노드로  최단거리로 왕복했을 때의 최댓값을 구하는 문제이다.   이 문제는 다익스트라 알고리즘을 사용하면 간편하게 풀 수 있다. 다만 오고 갈 때가 다르기에, 필자는 올때의 그래프, 갈때의 그래프를 따로 만들고 시작점을 X로 하여 모든 노드로 가는 최단거리를 구하고 각 인덱스에서 더해서 최댓값을 구했다. X를 도착으로 하든 시작으로 하든, 어차피 그래프만 거꾸로 뒤집으면 X를 시작으로 하여, 오고가는 것을 다 커버할 수 있다.import sysinput = sys.stdin.readlineimport mathimport heapqdef dijkstra(start,graph)..

https://www.acmicpc.net/problem/11404  이 문제는 말 그대로 플로이드 워셜 알고리즘을 구현하는 문제이다. 플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점으로 향하는 최단거리를 구할 때 사용한다. 이 알고리즘은 중간으로 경유하는 점들을 하나하나 검사해, 시작과 끝의 최단거리를 구한다. 그렇기에 시간복잡도는 O(n^3)이다.   이 때 유의할 점이, 가장 바깥쪽의 for문에는 중간 경유하는 점을 넣어야 한단 점이다. 만약 그렇지 않다면, 완벽히 계산되지 않은채로, 어느 정점에서는 시작과 끝이 끝나버리고, 새로운 최단거리가 발견되어도 갱신하지 못하기 때문이다. 그렇기에 시작과 끝의 계산을 최대한 뒤로 미루어서 항상 갱신할 수 있도록 해야한다. import sysinput ..

https://www.acmicpc.net/problem/1753  이 문제는 간편하게 시작지점에서 다른 모든 지점으로의 최소경로의 길이를 구하는 문제이다.   이 문제는 그냥 데이크스트라 알고리즘을 충실히 구현하면 풀린다. 데이크스트라 알고리즘에 관해서는 https://jangbearbio.tistory.com/102 이 글에서 자세히 다뤘으므로, 이 글에서는 자세히는 다루지 않겠다.  이 문제를 풀면서, 필자는 무의식적으로 데이크스트라 알고리즘을 구현할 때 큐를 말그대로 덱으로 하여, bfs의 큐처럼 사용했지만, 무게를 기준으로 최솟값이 항상 앞으로 튀어나오게 하는 heapq 자료형을 사용하는 것이 시간적이나 알고리즘적으로 더 낫다는 것을 기억하게 되었다. 가장 작은 무게가 먼저 나오기에, 같은 경로..

https://www.acmicpc.net/problem/13549  이 문제는 누나가 동생을 찾을 때 지금 위치에서 2배로 순간이동하면 0초, +-1로 이동하면 1초 걸려서 하나씩 탐색을 한다. 이때 동생을 찾는 가장 빠른 시간을 구하는것이 문제이다.  이 문제는 언뜻보면 그냥 보통의 BFS로 풀어야하거나, 다익스트라 알고리즘으로 풀어야 할 것처럼 보인다. 그런 식으로 풀어도 괜찮지만 문제의 의도는 0-1 너비우선탐색 방법을 쓰는 것이 의도이기에 0-1 너비우선탐색을 알아보자.  0-1 너비우선 탐색이란 그래프에서 모든 노드 사이의 엣지의 웨이트가 0혹은 1로 이루어져 있을 때 사용할 수 있다. 이 알고리즘의 작동을 간편히 설명하면, 일단 거리를 저장할 배열 뭐 dist를 정의한다. 그리고 우리가 통상..

https://www.acmicpc.net/problem/1916  이 문제는 도시 간의 버스비용이 최소로 해서 출발지와 도착지로 가는 버스비용 중 가장 최소비용을 구하는 문제이다. 이 문제는 정확히 데이크스트라 알고리즘(다익스트라 알고리즘이라고도 불림)을 사용하는 문제이다. 데이크스트라 알고리즘은 거칠게 설명하자면 그래프를 탐색하면서 내가 지나온 비용을 들고 탐색하고, 도시에 도착할 때 마다 그 전의 최소비용과 비교하며 지금이 더 최소라면 새로 업데이트 하는 식으로 한 도시에서 다른 도시로 가는 최소비용을 구하는 알고리즘이다. import sysinput = sys.stdin.readlineimport heapq cities = int(input().rstrip())buses = i..

https://www.acmicpc.net/problem/11725  이 문제는 노드의 개수 N이 주어지고 이후 N-1개의 노드 간 연결을 보여준다. 그리고 1을 루트로 하는 트리에서 2번 노드부터의 부모 노드를 출력하는 문제이다.  이 문제는 양방향 graph를 defaultdict를 사용하여 구현하고, DFS를 이용하여 1부터 시작하여 트리를 그려나가며 부모와 자식을 저장하는 식으로 풀었다. 필자는 처음엔 재귀를 이용하여 DFS를 풀었으나, 입력 범위가 매우 넓어, 재귀오류가 일어나, 스택을 이용하여 DFS를 구현하였다 from collections import defaultdict as ddimport sysinput = sys.stdin.readlinedef iterative_DFS(start):..

ProblemFigure 1. The suffix tree for s = GTCCGAAGCTCCGG. Note that the dollar sign has been appended to a substring of the tree to mark the end of s. Every path from the root to a leaf corresponds to a unique suffix of GTCCGAAGCTCCGG, and each leaf is labeled with the location in s of the suffix ending at that leaf.Given a string s">ss having length n">nn, recall that its suffix tree T(s)">T(s)T..

https://rosalind.info/problems/sgra/ ROSALIND | Using the Spectrum Graph to Infer PeptidesIt appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Using the Spectrum Graph to Infer Peptides solved by 533 Getting Real with Spectra In “Inferring Peptide from Full Spectrum”, we considered arosalind.infoProblemFor a weighted alphabet A">AA and a ..