[Algorithm] BOJ 다리놓기 - 1010번

1. 문제 풀이 다리 놓기는 일직선 모양의 강의 동쪽과 서쪽에 다리를 겹치지 않게 놓을 수 있는 경우의 수를 구하는 문제이다. 서쪽과 동쪽에는 각 N개와 M개의 다리를 둘 수 있는 곳이 있고 0 > ca; //경우의 수 long long count = 1; for (int i ..

[Algorithm] BOJ LCS 2 - 9252번

1. 문제 풀이 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 처음에는 일치하는 문자열을 찾아 char 배열에 저장 한 뒤 바로 출력하는 방식으로 풀어보려 했지만 구현이 복잡해져 정확히 먼저 수를 구한 뒤 가장 긴 수열을 찾아 역추적하는 방식으로 풀었다... 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 우선 1000자를 담을 수 있는 이차원배열을 0으로 초기화 한뒤 문자가 일치할 시에 이전에 일치한 개수에 1을 더해가는 방식으로 구현했다. 아래 표를 보면 일치하는 문자를 만나면 이전 인덱스의 값에 + 1을 하고 result[i][j] = result[i - 1][j - 1] + 1; 불일치 하면 그대로 i와 j 중 더 큰 값을 넣어 줌으로 긴 카운트를..

[Algorithm] BOJ 동전 1 - 2293번

1. 문제 풀이 n 가지 종류의 동전으로 그 가치의 합이 k원이 될 수 있는 경우의 수를 구하는 문제이다. 각각의 동전은 몇개라도 사용할 수 있다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 으로 주어진다. 우선 해당 값을 만들 수 있는 경우의 수는 값의 배수 일때 1번. 순열으로 만들었을때 두가지 동전으로 만들 수 있는 경우의 수 = 이전 동전으로 만들 수 있는 경우의 수 + 현재 동전으로 만들 수 있는 경우의 수 가 되는것이다. 이것을 점화식으로 인덱스에 기록해가며 더해가면 해당 동전들로 가능한 경우의 수를 구할 수 있다. 처음 첫 인덱스에 값을 1로 설정하고 그 뒤를 0으로 초기화해 처음 coin의 값이 들어갈 때 1이 더해지도록 했다. 2. 코드 #include using namespa..

[Algorithm] BOJ 팰린드롬? - 10942번

1. 문제 풀이 팰린드롬? 문제는 자연수 N 안에서 S번째와 E번째 수까지 팰린드롬, 곧 거꾸로 읽어도 제대로 읽는 것과 동일한지 알아내는 문제이다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. 우선 S부터 E사이의 차를 거리라 부르고 S와 E의 사이의 결과를 담을 이차원배열을 N*N 크기로 생성했다. 펠린드롬의 패턴은 S와 E 보다 1씩 줄어든 거리가 팰린드롬이고 S와 E가 같으면 팰린드롬이 되는 규칙을 이용해 하나씩 1로 채워가는 방식으로 풀이하였다. 거리가 0, 곧 같은 인덱스 일때는 1로 모두 초기화를 하고 거리가 1일때 j , j+1이 같으면 1로 설정했다. 거리가 2이상일때는 거리를 j , 대상인덱스를 z 로 while 문을돌려가며 z / j + z 가 같고 그 안에 직전 값이 1이..