코딩스토리

www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 오랜만에 정말 오랫동안 고민한 문제다. 물론 새벽이라 피곤했다는 핑계가 있지만.. 최근 들어서는 오래 고민하는 습관을 버리려고 노력했는데 실패.. 도저히 떠오르지가 않아서 구글링을 해보았다. 더 놀라운건 구글링을 한 페이지 가까이했는데도 이해가 잘 안 간다........ㅠ 너무나도 길고 복잡한 재귀 코드들... 난 이해하고 싶지 않았다 (제가 구글링을 하면서 느낀 건데 코드가 간단할수록 이해하기 좋더라고요.. 그래서 스포? 지..

www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP를 공부했던 사람들이라면 아마 대부분 RGB거리 1을 풀어봤을 것이다. 나 역시 RGB거리 1을 얼마 전에 풀어봤고, 어렵지 않게 점화식을 구할 수 있었기에 RGB2에 도전하였다. 빨리 풀고 그냥 딴 거 하려 했는데 코드가 생각보다 더럽고.. 뭐 일단 맞긴 했는데 정확한 풀이인지 확신이 안 서서 딴 사람들 풀이가 궁금해서 구글링 해봤는데.. 뭔 소린지 모르겠어 이게 컴공의 특성인..

오랜만에 블로그에 알고리즘 관련 글을 작성하는 것 같은데.. 절대 알고리즘에 손을 놓고 있던 게 아니라 우리 학교 알고리즘 소학회에 참여하느라 ㅎㅎ.. ( KOALA 뽜이팅!!) LCS 알고리즘은 DP를 공부했던 시점부터 계속 공부해야지, 공부해야지 했던 알고리즘인데 결국 오늘에서야 공부했다. ( 다음 주 학회의 주제가 마침 DP여서도 있고 ) 어쨌든 LCS 알고리즘에 대해 알아보면 Longest Common Subsequence, 즉 최장 공통부분 수열이라는 뜻이다. 만약 ACAYKP 란 문자열과 CAPCAK 란 두 개의 문자열이 주어졌을 때, LCS = ACAK 가 된다. 최장 길이 문자열과 살짝 헷갈릴 수 있는데, 우리가 구해야 하는 LCS는 최장 부분 공통 수열, 즉 수열이다. 수열이란 뜻은 결국..

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에 너무 많은 데이터가..