http://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net # 조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. # 접근 방법 최대 길이가 1000자 이므도 2중 for문을 돌려도 충분한 길이가 나온다. ACAYK..

http://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net # 조건 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성..

http://www.acmicpc.net/problem/1562 # 조건 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. # 접근 방법 dp와 비트마스킹을 통하여 풀어주었다. DP [마지막 자리의 숫자] [비트 마스킹] 비트 마스킹의 경우 현재까지 사용된 숫자를 기록해준다. 2 4 5를 가지고 있다면 000011010..

알고리즘 기법이라고 볼 수는 없지만 비트마스크 기법을 이용하여 풀 수 있는 문제가 꽤 보여서 알아보기로 하였다. 개념 컴퓨터의 최소 연산 단위 bit 이진수를 나타내기 위해 0과 1로만 이루어져 있는데, 비트 연산을 통하여 빠르게 해결 할 수 있다. 예를 들면 -> bfs나 dfs를 하며 visited를 체크 해줄 때, 크기가 10인 배열을 만드는 경우가 있는데 0b0000000000 와 같이 비트마스킹으로 똑같은 표현을 할 수 있다. 즉 더 작은 메모리를 사용하여 표현 가능하다. 장점 비트 연산은 삽입, 삭제, 조회가 빠르다. 코드가 간결해지며 정수 표현으로 dp문제 해결 가능 비트 연산 2022.08.10 - [ALGORITHM/알고리즘 알아보기] - 알고리즘 - 부분 집합 알고리즘 - 부분 집합 완..

http://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net # 조건 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열이 주어진다. 이 ..

이전 포스팅에서는 dp를 이용하여 회문을 판별하는 알고리즘을 알아보았다. 2023.01.21 - [ALGORITHM/알고리즘 알아보기] - [Algorithm] 팰린드롬 판별 알고리즘 [Algorithm] 팰린드롬 판별 알고리즘 회문이란 반대로 읽어도 원본과 같은 단어를 말한다. 3개의 for 문을 사용하여 모든 회문을 찾을 수 있지만, 이 경우 시간 복잡도가 O(N^3)이 되므로, 이미 반복한 부분인 하위 문제의 결과를 DP table cheon2308.tistory.com 이 경우 시간복잡도가 O(N^2)이 되어 10000이상의 길이를 가진다면 시간이 오래걸린다. 이번엔 O(N)의 시간복잡도를 가지는 Manacher 알고리즘을 알아보자. 동작 원리 우선 문자열 S에 대해 배열 A를 구할 수 있다. 배..

http://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net # 조건 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자..

회문이란 반대로 읽어도 원본과 같은 단어를 말한다. 3개의 for 문을 사용하여 모든 회문을 찾을 수 있지만, 이 경우 시간 복잡도가 O(N^3)이 되므로, 이미 반복한 부분인 하위 문제의 결과를 DP table에 저장하여 시간 복잡도를 줄이는 알고리즘 이 경우 2개의 for문을 이용하므로 O(N^2)의 시간 복잡도를 가지게 된다. N = int(input()) nums = [*map(int, input().split())] M = int(input()) dp = [[0] * (N) for _ in range(N)] # 각 한 단어씩은 팰린드롬 이므로 True 체크 for i in range(1,N): dp[i][i] = True # 11, 22와 같이 연속된 값인 경우 팰린드롬이므로 True for j..

http://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net # 조건 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하여라. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000..