본문 바로가기

Java

[알고리즘] 문자열 매칭 알고리즘 KMP (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 5. 11. [알고리즘] 문자열 매칭 알고리즘 KMP (Java) 문자열 매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다. 워드파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 ABDEGH 찾는 문자열 DE 가장 앞부분부터 찾는 문자열이 매칭될 때 까지 탐색을 시작한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어졌으면 탐색을 종료한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 코드 이 알고리즘은 이중포문으로 시간..
[프로그래머스] 2021 카카오/ 매출 하락 최소화 (Java)
Dot Algo∙ DS/PS 2021. 5. 6. [프로그래머스] 2021 카카오/ 매출 하락 최소화 (Java) #7 매출 하락 최소화 2021 카카오 블라인드 난이도 : LEVEL 4 유형 : 트리 순회 / DP 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr [문제] 직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완..
[BOJ] 백준 12015번 가장 긴 증가하는 부분 수열2 LIS - 이진탐색 (Java)
Dot Algo∙ DS/PS 2021. 5. 5. [BOJ] 백준 12015번 가장 긴 증가하는 부분 수열2 LIS - 이진탐색 (Java) #12015 가장 긴 증가하는 부분 수열 2 (LIS) 난이도 : 골드 2 유형 : DP 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ▸ 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ▸ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에..
[BOJ] 백준 11053번 LIS 가장 긴 증가하는 부분 수열 LIS - DP(Java)
Dot Algo∙ DS/PS 2021. 5. 5. [BOJ] 백준 11053번 LIS 가장 긴 증가하는 부분 수열 LIS - DP(Java) #11053 가장 긴 증가하는 부분 수열 LIS 난이도 : 실버 2 유형 : DP 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ▸ 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ▸ 입력 첫째 줄에 수열 ..
[BOJ] 백준 9251번 LCS (Java)
Dot Algo∙ DS/PS 2021. 5. 4. [BOJ] 백준 9251번 LCS (Java) #9251 LCS 난이도 : 골드 5 유형 : DP 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ▸ 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. ▸ 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로..
[프로그래머스] 2021 카카오/ 신규 아이디 추천 (Java)
Dot Algo∙ DS/PS 2021. 5. 3. [프로그래머스] 2021 카카오/ 신규 아이디 추천 (Java) #1 신규 아이디 추천 2021 카카오 블라인드 난이도 : LEVEL 1 유형 : 문자열 / 정규식 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr [문제] 신규 유저가 입력한 아이디를 나타내는 new_id가 매개변수로 주어질 때, "네오"가 설계한 7단계의 처리 과정을 거친 후의 추천 아이디를 return 하도록 solution 함수를 완성해 주세요. [제한사항] new_id는 길이 1 이상 1,000 이하인 문자열입니다. new_id는 알파벳 대문자, 알파벳 소문자, 숫자, 특수문자로 구성되어 있습..
[BOJ] 백준 1922번 네트워크 연결 (Java)
Dot Algo∙ DS/PS 2021. 5. 3. [BOJ] 백준 1922번 네트워크 연결 (Java) #1922 네트워크 연결 난이도 : 골드 4 유형 : 그래프/ 최소 신장트리 (크루스칼알고리즘) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net ▸ 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최..
[BOJ] 백준 1562번 계단 수 (Java)
Dot Algo∙ DS/PS 2021. 5. 2. [BOJ] 백준 1562번 계단 수 (Java) #1562 계단 수 난이도 : 골드 1 유형 : DP / 비트마스킹 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ▸ 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) ▸ 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. ▸ 출력 첫째 줄..

티스토리툴바

티스토리툴바