본문 바로가기

전체 글108

백준 9252번 : LCS2 (Java) 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 구현 방법 백준 9251 LCS 문제(https://www.acmicpc.net/problem/9251)에 LCS 출력을 추가한 문제 입니다. 결과 값은 LCS 구하는 것의 역방향으로 생각하면 됩니다. 1. LCS 배열의 가장 마지막 값에서 시작 2. LCS[i - 1][j]와 LCS[i][j - 1] 중 현재 값과 같은 값 찾기 2-1. 만약.. 2022. 3. 4.
백준 9251번 : LCS (Java) 문제 구현 방법 LCS (Longest Common Subsequence)는 최장 공통 부분 수열로 모두의 부분 수열이 되는 수열 중 가장 긴 값을 찾는 알고리즘 입니다. 부분 수열이기 때문에 연속할 필요가 없습니다. 2차원 배열을 생성하여 문자를 하나씩 비교해주었습니다. 아래 순서는 구현 과정을 간략하게 나타낸 것 입니다. 1. 편의를 위해 마진 설정 2. 문자가 같다면 이전에 저장된 값에 +1 (이전에 저장된 값에는 현재까지의 최장 부분 수열 길이가 저장) 3. 문자가 같지 않다면 현재까지 탐색한 부분 수열 길이에서 더 큰 값 저장 4. 위 과정 반복 코드를 보고 따라가면서 이해하는 것을 추천드립니다. 구현 코드 package BOJ.Gold; import java.io.BufferedReader; .. 2022. 3. 3.
백준 16940번 : BFS 스페셜 저지 (Java) 문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 구현 방법 BFS 알고리즘 문제입니다. 문제를 보면 정점을 방문하는 순서는 중요하지 않아서 BFS 의 결과는 여러 가지가 나올 수 있다고 명시되어 있습니다. 방문 순서는 중요하지 않다는 말은 같은 레벨에서 삽입하는 정점의 순서가 중요하지 않다는 말입니다. 여기서 주의할 점은 한 정점에서 이동하는 정점들과 또 다른 정점에서 이동하는 정점들의 순서가 섞이면 안 됩니다. 예를 들어 2번, 3번 정점이 큐에 있고 2번은 4번, 5번 정점과 연결, 3번은 6번, 7번 정점과 연결되어있다고 가정할 때 4, 5, 6, .. 2022. 2. 23.
백준 7662번 : 이중 우선순위 큐 (Java) 문제 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 구현 방법 최댓값, 최솟값을 삭제할 때마다 바로 빼낼 수 있도록 최댓값 우선순위 큐와 최솟값 우선순위 큐로 나누어 풀어줬습니다. 만약 최댓값을 삭제한 경우 최솟값 우선순위 큐에 값이 남아있습니다. 어떤 값이 삭제 되었는지 최솟값 우선순위 큐가 알아야 하므로 맵에 삭제된 값을 저장해주었습니다. (동일한 정수가 삽입될 수 있으므로 개수도 같이 저장하기 위해 맵을 사용했습니다) 구현 과정을 단.. 2022. 2. 22.

티스토리툴바