곰탱이의 공부정리

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/9465  이 문제는 가로로 N줄 세로로 2줄인 스티커 배열이 주어진다. 스티커 배열 안의 스티커는 각자 점수가 있다. 어떠한 스티커를 떼어낸다면 그 스티커와 변이 맞닿아있는 스티커는 못 쓴다는 설정이다.  이러한 경우 스티커 배열에서 가장 점수가 높게 스티커를 떼어낼 때의 점수를 출력하는 것이 문제이다.  이 문제는 언뜻 보면 브루트포스처럼 모든 것을 해야할 것 처럼 보이지만, 이 문제 또한 일종의 다이나믹 프로그래밍 문제이다. 이 문제를 왼쪽부터 훑어가면서 특정 스티커를 뽑을 때, 이 스티커를 뽑을 수 있게하는 직전 스티커들 중, 가장 점수가 높은 것들을 따라가는 식으로 하면된다. 이게 말로하면 복잡한데 그림으로 그려주자면  내가 지금 체크표시..

https://rosalind.info/problems/edta/ ROSALIND | Edit Distance AlignmentIt appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Edit Distance Alignment solved by 1221 Reconstructing Edit Distance In “Counting Point Mutations”, the calculation of Hamming distance gave urosalind.infoProblemAn alignment of two strings s">ss and t">tt is defined ..

https://rosalind.info/problems/lcsq/ ROSALIND | Finding a Shared Spliced MotifIt appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Finding a Shared Spliced Motif solved by 2456 Locating Motifs Despite Introns In “Finding a Shared Motif”, we discussed searching through a drosalind.infoProblemA string u">uu is a common subsequence of string..

https://rosalind.info/problems/lgis/ ROSALIND | Longest Increasing SubsequenceIt appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Longest Increasing Subsequence solved by 3342 A Simple Measure of Gene Order Similarity In “Enumerating Gene Orders”, we started talking abourosalind.infoProblemA subsequence of a permutation is a collection o..