코딩스토리

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS에 관한 설명은 해당 블로그에 자세히 작성해 놓았습니다. kimtaehyun98.tistory.com/64 Longest Common Subsequence (LCS, 최장 공통 부분 수열) 오랜만에 블로그에 알고리즘 관련 글을 작성하는 것 같은데.. 절대 알고리즘에 손을 놓고 있던 게 아니라 우리 학교 알고리즘 소학회에 참여하느라 ㅎㅎ.. ( KOALA 뽜이팅!..

www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net dp 문제이다. 요즘 dp를 많이 풀어보고 싶어서 풀어봤는데 처음 봤을때 dp가 아닌줄 알았다. 누가봐도 bfs 문제 같아서 에라 모르겠다 하고 bfs로 풀다 보니 뭔가 이상.. bfs와 dp를 섞어서 풀다보니 뭔가 쎄~ 했다. 일단 예제랑 반례들 답이 잘 나오길래 제출하긴 했는데 메모리초과!! 역시 느낌이 중요하다니까 잠시 고민해봤는데 아무래도 bfs를 사용할 때 queue에 너무 많은 데이터가..

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 옛날부터 이문제 한번 풀어보고 싶었는데 골드 3에 dp라 뭔가 엄청 어려울 것 같아서 못풀었었다. 오늘 날잡고 어떻게든 한번 풀어보자 하고 풀어봤다. 처음 문제를 봤을때 재귀가 떠올랐다. 이런 문제의 경우 dfs라고 하는게 맞겠지만.. 분명 dp와 재귀를 통해 풀 수 있을것 같은데 이게 맞을까 싶어서, 해결법이 맞는지를 한참 고민했다. 아무리 봐도 다른 방법은 떠오르지 않아서 그냥 풀었는데 다행히 맞았다...

www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 기초적인 DP 문제였다. 인접리스트를 사용하는게 해결 방법이였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #include #include using namespace std; typedef long long ll; int main() { ios_..

codeforces.com/contest/1452/problem/C Problem - C - Codeforces codeforces.com 기초적인 stack 문제였다. 괄호의 짝을 stack을 사용해서 구하는 문제는 기초중의 기초니까 꼭 알고 넘어가자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::..