오딩이

출처 : 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/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 해당 문제에서는 Q만큼의 두 정수 k와 v를 입력으로 주는데, 이 두 정수 관계를 이해하는데 시간이 오래 걸렸습니다. 테스트 케이스를 손으로 그려보면서 따라가니 주어진 k, v가 의미하는 것은 ' v에서 시작해서 간선 비용이 k보다 크면 진출한다 '라는 결론을 내렸습니다. 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재..

문제 출처 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..