https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 위 문제는 기존의 그래프 문제들과는 많이 다른 유형이었다. 큐나 배열에 해당 좌표뿐만 아니라 벽을 부술 수 있는지와 이전에 벽..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 수빈이가 동생에게 도달하는 최소의 시간을 구하는 문제입니다. 해당 좌표까지 가는데 3가지 방법이 있는데 이는 x2, +1, -1이 있습니다..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 1629번 곱셈 문제만 보면 정말 단순해 보인다. 그냥 B번만큼 곱한 후 C로 나눠주면 된다. 여기서 생각해볼 점은 A^B = A^(B/2) * A^(B/2)이라는 것이다. 홀수면 A^(B/2) * A^(B/2) * A이다. 그래서 재귀로 해결해도 된다. 또 다른 방법은 B를 2로 나누어 주면서 나머지가 홀수 일때만 결과값에 곱해주고 나머지는 계속 A값을 곱해가면 된다. 그리고 여기서 C로 나누어주어야하는데 마지막 결과값에 나누어주면 long long 형도 버틸..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net 백준 2004 조합 0의 개수는 조합의 결과가 제일 뒤 0의 개수가 몇개가 나오는지 확인하는 문제이다. 1676번 팩토리얼의 0의 개수와 같듯이 2, 5의 등장횟수를 구한 뒤 적은 등장 횟수가 답이된다. 왜냐하면 2*5가 한개씩 있으면 10이되고 두개씩 있으면 100이되면서 뒤의 숫자들은 2와 5의 개수로 결졍된다. 조합은 아래와 같은 공식을 따른다. 그래서 우리는 n!, (n-r)!, r!에 5와 2가 몇번 등장해야하는지 확인해야한다. 예를 들어 25!이면 1 부터 25까지의 곱셈을 의미한다. 그..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 두개의 문자열 중 동일한 부분수열 중 가장 긴 부분수열의 개수를 구하는 문제이다. 하나의 문자열을 베이스로 하나하나 동일한지 비교하며 표를 채워 나가면된다. if (letter1[i] == letter2[j] ) 이전 문자열 단계(이전 문자열의 최장 길이)에서 하나씩 증가하면 된다. 결국 ACAYKP와 CAPCAK는 K의 이전 ACAY와 CA..

LIS 알고리즘 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 문제는 간단하다. 아래와 같은 수열 중 부분수열 중 길이가 증가하면서 가장 긴 부분수열을 구하는 문제이다. {10, 20, 10, 30, 20, 50} => {10, 20, 30, 50} 푸는 방법이 이진 탐색을 사용하여 O(nlogn)이 걸리는 방법 dp를 사용하는 방법O(n^2) ..