[백준] 1305 광고 - KMP(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net ​ 📕 문제 접근 📕 - 해당 문제도 KMP 알고리즘을 사용한다(?). - 개인적인 생각으로는 KMP를 위한 table만 설계하면 끝난다고 생각하여 반쪽짜리 KMP 느낌이 든다. 포인트 1) 광고 문자열은 무한히 반복한다. 2) 무한히 반복하는 문자열 중 일부분만 확인하다. 3) 그광고가 될 수 있는 문자열(무한히 반복하는 문자열)이 가능한 경우 중 가장 짧은 문자열의 길이를 구한다. 문자열에서 접두사..

  • format_list_bulleted JAVA/Algo 풀이
  • · 2023. 8. 5.
  • textsms

[백준] 1786 찾기 -KMP(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net ​ 📕 문제 접근 📕 - 가장 이상적인 KMP문제인 것 같다 - 접미사와 접두사가 같은 영역을 찾기 위한 table을 만들고 - 이를 KMP 알고리즘에 대입하여 해결하면 되는 문제다 - KMP 알고리즘은 해당 포스팅에 자세하게 정리해뒀으니 참고 바란다. https://security-gom.tistory.com/36 KMP -JAVA KMP Algorithm : 문자열 검색 알고..

  • format_list_bulleted JAVA/Algo 풀이
  • · 2023. 8. 5.
  • textsms
KMP -JAVA

KMP -JAVA

KMP Algorithm : 문자열 검색 알고리즘 💡 **특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘. 워드 파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다.** 1. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 : ABDEGH 찾는 문자열 : DE 가장 앞 부분부터 찾는 문자열이 매칭될 때까지 탐색을 시작한다. 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 매칭이 이루어졌으면 탐색을 종료한다. 위와 같은 예시가 아닌, “A B A C A A B A”를 검색하는 패턴이 “A B A C A B”인 경우에서는, 불필요한 연산이 다시 진행되는 경우도 ..

  • format_list_bulleted JAVA/Algo 개념
  • · 2023. 8. 5.
  • textsms

양방향 연결리스트 구현하기

양방향 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고 있는 연결 리스트의 한 종류입니다. 각 노드는 데이터와 두 개의 포인터(다음 노드를 가리키는 next 포인터와 이전 노드를 가리키는 prev 포인터)로 구성되어 있습니다. 이러한 구조로 인해 양방향 연결 리스트는 단방향 연결 리스트와 달리 노드의 이전 노드를 쉽게 접근할 수 있습니다. 양방향 연결 리스트의 특징: 노드 구성: 각 노드는 데이터 필드와 두 개의 포인터(다음 노드를 가리키는 next 포인터와 이전 노드를 가리키는 prev 포인터)로 이루어져 있습니다. 양방향 이동: 단방향 연결 리스트와 달리, 양방향 연결 리스트는 노드의 이전 노드를 가리키는 prev 포인터를 통해 역방향으로 이동할 수 있습니다. 이..

  • format_list_bulleted JAVA/Algo 개념
  • · 2023. 8. 5.
  • textsms

[프로그래머스] 야근지수 - JAVA

문제링크 🚩 https://programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ​ 📕 문제 접근 📕 잘 못 된 접근 : // 모든 수를 낮게 만드는게 이득인가? // 7 -> 1 3 3 -> 18 // 2, 2, 3 -> 4 + 4 + 9 => 17 // 모든 수를 가장 낮게 만드는게 이득 // 배열을 순회하기에는 시간이 부족함 // 그럼 어떤 방법으러 해결해야하는가? // 전부다 더하고 n을 빼고 수를 나눈다면? => 문제 발생 그럼 2, 1, 2 에 n이 1 인경우 4가..

  • format_list_bulleted JAVA/Algo 풀이
  • · 2023. 8. 1.
  • textsms

[프로그래머스] 110 옮기기 - Java

문제링크 🚩 https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ​ 📕 문제 접근 📕 110이 생기면 최대한 앞으로 뽑아내는 로직을 생각했다. 원래 문자에 110이 존재하지 않는다면 원본 그대로 저장하고 존재한다면 마지막 0뒤에 110을 찾은 수 만큼 넣는 로직을 생각하였다. 💻 Code 💻 **import java.util.Stack; class Solution { public String\[\] solution(String\[\] s) { St..

  • format_list_bulleted JAVA/Algo 풀이
  • · 2023. 8. 1.
  • textsms
반응형