Algorithm/BOJ45 [백준] 9251번 LCS 자바 문제 (골드5 / dp) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 사실 LCS는 유명한 문제이기에, 얕보고 백준 LCS3문제를 풀다가 너무 어려워서 LCS 먼저 풀면서 개념을 다지기 위해 LCS를 풀었다. 근데 알고보니 내가 알던 LCS 뜻과 약간의 혼동이 있었다. LCS(Longest Common Subsequence): 최장 공통 부분 수열 - 부분 수열이므로 공통된 문자들이 연결되어 있지 않아도 된다. - ex) ABCDEF, GBCDFE -.. 2021. 11. 29. [백준] 17413번 단어 뒤집기2 자바 문제 (실버3) 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 풀이 입력받은 문자열을 toCharArray 함수를 이용하여 char[]배열로 바꾼 후 string변수에 답을 붙여나가면서 진행했다. 문자열 반복을 해주면서 태그표시가 나오면 문자 그대로를 붙이고, 아니면 스택에 넣어주었다. 띄어쓰기가 나오거나 / 다시 태그가 나오거나 / 문자열이 끝나거나 이 세가지 경우에 한해서 스택에 넣은 값들을 비워내면서 string변수에 붙였다. ※ 이유는 모르겠는데 백준에서 코드제출할.. 2021. 11. 27. [백준] 1260번 DFS와 BFS 자바 문제 (실버2) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 이 문제는 진짜 제목 그대로 DFS와 BFS를 직접 구현해보는 문제이다. 코딩테스트 연습을 하다보면 자주 접하게 되는 개념이지만, 어려워서 항상 코드를 보고 풀었다. 이번 기회에 DFS와 BFS개념을 확실히 다지고자 풀게되었다. 이번 기회에 개념 꼭 다지고 넘어가야지! 우선 DFS알고리즘은 깊이 우선 탐색으로 스택을 이용하는 방법과 재귀함수를 이용하는 방법 두가지가 있는데, 대부분 재귀함수를 이용하.. 2021. 11. 17. 이전 1 ··· 5 6 7 8 다음
