출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 🔍 Solve 다이나믹 프로그래밍으로 풀기 전, 완전 탐색으로 풀었을 때 시간 초과가 났던 문제입니다. 완전 탐색으로 풀었을 때 우선순위가 큰 것부터 선택하고 인접한 곳들을 지우는 방법으로 풀었습니다. isSelect배열을 선언하여 지워지는 곳은 1로, 선택된 곳은 2로 저장하였고, isSelect배열이 0이 아닌 수로 꽉 차면 break를 해주었습니다. 해당 방법은 테스트 케..
출처 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 🔍 Solve 완전 탐색으로 문자열 1과 문자열 2를 비교하는 방법을 생각했었는데, 카테고리가 dp인 만큼 시간 초과가 났습니다. dp배열에서 i=0, j=0일 때 i-1, j-1을 비교해야하기 때문에 dp배열의 크기는 (문자열 1의 길이+1) * (문자열 2의 길이+1)로 설정하였습니다. 문자열의 문자들을 비교하면서 문자가 같지 않을 땐 dp..
문제 출처 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 2개의 연속된 칸을 차지하는 파이프를 3가지 방향으로 밀면서 회전시켜서 파이프의 한쪽 끝을 (N,N)으로 이동시키는 방법의 개수를 구하는 문제였습니다. 처음에는 dr, dc의 방향 배열과 위치와 가로, 세로, 대각선 중 어떤 상태인지를 가지는 클래스를 생성하여 bfs로 풀려고 했지만, 따져야 할 조건들이 많아 결국 dfs 재귀 형식으로 풀었습니다. 파이프는..
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 유니온 파인드를 사용하여 해결하였습니다. 경로의 최단경로나 최소개수를 구하는 문제가 아니기때문에 크루스칼 알고리즘까지 할 필요가 없었고, 다른 과정 없이 union-find 로직을 통해 같은 경로에 있는지만 확인 후 true, false를 체크하였습니다. 루트노드가 같은 루트노드라면 같은 경로에 있다고 판단할 수 있습니다. 전체 코드 import java.io.BufferedReader; i..