문제 링크 www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 기본 논리는 간단합니다. 입력받은 두 문자열을 $u$, $v$라 하고, $i$는 $u$의 인덱스, $j$는 $v$의 인덱스라 합시다. 모든 $i$, $j$ 쌍에 대해 탐색하면서, $u[i]$ == $v[j]$ 인 지점에서 다음 문자부터 시작하는 최대 길이의 공통 부분 문자열의 길이값을 가지고 테이블을 업데이트해줍니다. 따로 정답을 저장하는 변수를 두어 그때그때 갱신하면 쉽게 짤 수 있..
문제 링크 www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 현재 클립보드에 들어있는 이모티콘의 개수와, 화면에 나타난 이모티콘의 개수를 바탕으로 상태를 정의합시다. $d[clip][screen]$: 클립보드에 $clip$개, 화면에 $screen$개 이모티콘이 있을 때 시간의 최솟값입니다. 한 상태에서 갈 수 있는 다른 상태가 명확합니다. 1) $clip$을 $screen$으로 변경 2) $screen$을 하나 삭제 3) $screen$을 $clip$만큼..
문제 링크 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 풀이 예제 설명을 색깔별로 친절하게 그려준 게 아마 큰 힌트가 되지 않을까 싶습니다. 1) 사다리를 쓰지 않고 이동할 수 있는 정점별로 그룹을 만들어줍니다. BFS, DFS 상관없습니다. 2) 위 그룹핑을 바탕으로 그래프를 재구성할 수 있습니다. 각 그룹을 정점으로, 그룹과 그룹 사이 사다리의 ..
문제 링크 www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 풀이 간단한 트리 DP 문제입니다. 1) 만약 현재 정점을 고르면 -> 자식들은 골라도 되고, 안골라도 됩니다. 2) 만약 현재 정점을 고르지 않으면 -> 모든 자식들을 골라야 합니다. $d[now][k]$를 k가 0일때 안고름, 1일 때 고르는 상황의 최솟값이라고 합시다. now의 모든 자식 next에 대해 $d[now][0] = \text{sum}(d[next][1])$ $d[now][1] ..
문제 링크 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 예제 2번으로 시뮬레이션해봅시다. 1번 비행기) 2번 게이트가 비어 들어갈 수 있습니다. 2번 비행기) 2번 게이트가 비어있지 않아 그 앞의 1번 게이트로 들어갑니다. 3번 비행기) 3번 게이트가 비어있어 들어갈 수 있습니다. 4번 비행기 3번, 2번, 1번 게이트가 모두 비어있지 않아 끝나게 됩니다. 문제를 풀어봅시다. 게이트의 수가 10만이라 그냥 시뮬레이션..
문제 링크 www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 풀이 1) 1부터 x 이하 모든 수의 1의 개수를 구해주는 함수 go를 구현합시다. 2) go$(B)$ - go$(A-1)$ 를 구해주면 됩니다! 이제 go함수를 만드는 방법을 알아봅시다. 1. 누적합 구하기 우선 최상위 비트가 $i$번 이하인 모든 수의 1의 개수의 합을 누적합으로 구해줘야 합니다. 편의상 $i$는 0부터 시작한다고 합시다. 이를 어떻게 구할 수 있을까요? ..