전체 글
-
[BOJ] 10986번: 나머지 합Algorithm/Baekjoon Online Judge 2022. 4. 27. 17:43
문제풀이 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 처음에는 누적합을 구하고 그 안에서 만들수 있는 조합에 대한 범위로 모든 경우를 살펴서 나머지가 0인 것을 찾았지만 이는 시간초과가 났다. 아무래도 2중 반복문을 써서 계속 배열에 접근하는게 문제였던 것 같다. 해결할 방식의 경우 다른사람의 풀이를 참고했는데 이해하기가 쉽지 않았다. 따라서 설명을 자세하게 적어보려고 한다. 주어진 입력이 다..
-
[Algorithm] 이항계수Algorithm 2022. 4. 23. 14:39
이항계수 조합론에서 이항계수는 이항식을 이항 정리로 전개했을 때 각 항의 계수이다. 각 항의 계수는 주어진 크기에서 순서없는 조합의 가짓수이다. 이항계수는 위와 같다. 이때 이항계수는 nCk나 C(n, k)로 쓰기도 한다. 이항계수는 위의 공식을 사용하여 factorial을 사용해 구할 수도 있고 파스칼의 삼각형을 이용한 동적계획법 알고리즘으로 구할 수 있다. 파스칼의 삼각형 이항계수만을 작성해보면 다음과 같이 삼각형의 형태로 작성할 수 있다. 여기서 이항계수간의 관계를 발견할 수 있다. nCk = n-1Ck-1 + n-1Ck 위와같은 점화식이 성립한다. 파스칼의 삼각형을 이용하여 다이나믹프로그래밍의 메모이제이션 방식으로 쉽게 이항계수를 구할 수 있다. Python 다이나믹 프로그래밍 방식 > impor..
-
[BOJ] 12865번: 평범한 배낭Algorithm/Baekjoon Online Judge 2022. 4. 16. 15:17
문제풀이 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 가장 일반적인 냅색 문제이다. dp를 통해 해결할 수 있는데 생각보다 조건을 생각할 것이 많았다. 나의 경우 다이나믹프로그래밍 배열을 1차원으로 작성하는 것을 선호하는데 이 경우에는 2차원 배열로 먼저 작성했다. 2차원 배열의 행은 각 물건을 나타내며, 열은 무게를 나타낸다. 0번째 행, 0번째 열은 비워두기 때문에 (n+..
-
[BOJ] 9251번: LCSAlgorithm/Baekjoon Online Judge 2022. 4. 15. 00:22
문제풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 개의 문자열이 주어질 때 두 문자열에서 매치되는 가장 긴 문자열의 길이를 구하는 문제이다. 사실 어떻게 하면 풀 수 있을지 고민을 좀 했다. 생각보다 쉽게 방식이 안 떠올라서 이전에 계산한 값을 어떻게 하면 현재 계산에 적용할 수 있을지 방법을 알기위해 노력했다. 이 문제에서는 알파벳 하나가 어떤 알파벳과 매치될지 알 수 없다는 점이 가장 ..
-
[BOJ] 2565번: 전깃줄Algorithm/Baekjoon Online Judge 2022. 4. 13. 16:34
문제풀이 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 우선 전깃줄을 하나씩 보면서 그때까지 가질 수 있는 최대 전깃줄 개수를 구해야 한다는 것을 제일 먼저 생각해야한다. 그렇다면 최대 전깃줄 개수를 어떻게 구할 수 있을까를 생각해야한다. 두개의 전깃줄이 있을 때 A와 B에서의 위치를 (a1, b1), (a2, b2)라고 한다면 전깃줄이 교차되지 않기 위해서는 a1 a2 and b1 > b2 여야한다. ..