softwareNote softwareNote

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 문제 설명 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 짧은 소요시간을 구하는 문제이다. 문제 해결과정 처음에 문제를 읽어보고 당연히 다익스트라로 풀어야겠다고 생각하고 봤는데 고려해야 할 요소가 2가지였다. 가장 빠른 길만 고려해야했다면 너무 쉬운 문제이니 골드1이 아니었겠지. 그래서 백트래킹 형태로 visited 여부를 체크하면서 코드를 짰..

https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 겨울에 스프링 하느라 알고리즘 오랜만에 푸는데 시간은 좀 걸렸지만 한번만에 풀려서 행복했던 문제 kotlin에서 푼 사람도 두 명 밖에 없고 해서 블로그에 풀이 해보기로했다. 문제 요약 NxN 의 체스판에 K(1 ~ K) 개의 말이 번호순서대로 움직인다. (4 ≤ N ≤ 12, 4 ≤ K ≤ 10) 체스판은 흰색(0) 또는 빨간색(1) 또는 파란색(2) 으로 색칠되어 있다. 말은 상하좌우 움직일 ..

피보나치 수는 0, 1로 시작하고 i번째 피보나치 수가 바로 앞 두 수의 합이 되는 수열이다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2) 이렇게 나타낼 수 있다. n이 작을때, 피보나치수는 간단한 연산으로 구할 수 있지만 n이 굉장히 커지면 이를 구하는 데 시간이 많이 든다. 이때 행렬로 피보나치 수를 나타내는 방식은 도움이 된다. 위의 식을 행렬로 나타낸 것이다. 오른쪽 항의 뒤쪽 행렬과 비슷한 꼴로 맞춰주기 위해 조금 변형을 해보자. 0번째 피보나치수는 0, 1번째 피보나치수는 1이므로 위 식을 재귀적으로 연산하게되면 다음과 같은 결과를 얻을 수 있다. n + 2번째 피보나치 수를 구하는 문제는 행렬을 n + 1번 제곱하는 문제로 바뀌었다. 위 식의 오른쪽 항의 앞쪽 행렬을 A라..

LCS란 주어진 모든 수열들의 부분 수열(연속적이지 않아도 된다)이 되는 수열 중 가장 긴 것이다. str1과 str2라는 두 수열이 주어졌다고 하자. P] str1과 str2의 부분수열 중 가장 긴 수열의 길이를 구하라. Sol) str1의 시작부터 x번째까지의 문자열과 str2의 시작부터 y번째까지의 문자열의 LCS를 f(x, y)라고 하자. 이때 f(m, n)은, 1) str1의 m번째 문자 == str2의 n번째 문자일때 f(m, n) = f(m - 1, n - 1) + 1 : 현재 일치하는 문자를 제외하고 나머지 문자열들의 LCS가 현재 문자열들의 LCS보다 하나 짧아야 하므로 자명하다. 2) str1의 m번째 문자 != str2의 n번째 문자일때 f(m, n) = max(f(m - 1, n) ..