[프로그래머스] 양과 늑대 - JAVA

문제링크 🚩https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  ​📕 문제 접근 📕- 모든 상황에 대해 DFS 순회가 가능하도록 설계 해당 노드 방문 여부에 따른 Cnt 체크 sheepCnt가 wolfCnt보다 작거나 같은 경우 Return 부모 노드 방문, 자식 노드 미방문 시 순회.💻 Code 💻class Solution { int[] copyInfo; int[][] copyEdges; int ma..

• format_list_bulleted JAVA/Algo 개념
• · 2024. 7. 4.
• textsms

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

슬라이딩 윈도우와 투 포인터

슬라이딩 윈도우와 투 포인터 알고리즘의 차이 두 알고리즘은 1차원 배열에서 사용시 선형 공간을 2회 이상 반복적으로 탐색해야할 경우 O(N^2) 이상 걸리는 시간 복잡도를 부분 배열을 활용하여 O(N)의 시간으로 단축 시키는데 의의가 있다 두 알고리즘의 차이는 부분 배열 길의의 변화 슬라이딩 윈도우 : 부분 배열의 길이가 고정적 투 포인터 : 부분 배열의 길이가 가변적 슬라이딩 윈도우 : 개념 부분 배열의 길이가 고정적인 알고리즘 투 포인터와 같이 2개의 포인터가 필요하지 않음 : 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나로도 종료지점을 알 수 있음 배열의 부분 합을 구하는 문제 : 오른쪽으로 한 칸 옮기고 옮기기 전 부분 배열과 옮기고 난 후에 겹치는 부분이 존재할 때, 기존 구간..

• format_list_bulleted JAVA/Algo 개념
• · 2023. 7. 30.
• textsms

TreeMap - Red-Black Tree

https://security-gom.tistory.com/30 개념 숙지 후 해당 문제를 풀어보면 도움이 될 것이라고 생각한다. [프로그래머스] 이중우선순위큐 - TreeMap 문제링크 🚩 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 security-gom.tistory.com TreeMap이란? TreeMap은 이진 트리를 기반으로 한 MAP의 컬렉션이다 기존의 TreeSet과의 차이는 값만 저장하는 것이 키와 값이 저장될 수 있는 Map, Etnry를 저장하는 것이다. TreeMap에 객체를 저장하면 자동으..

• format_list_bulleted JAVA/Algo 개념
• · 2023. 7. 26.
• textsms

DP - LIS(최장 증가 수열) 및 0-1 Knapsack 개념 (JAVA)

최장 증가 부분 수열(LIS) 최장 증가 부분 수열이란? 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로, 순서를 유지한 채 몇 개의 숫자들을 뽑아서 부분 수열을 만들 수 있다. 이렇게 만들 수 있는 부분 수열 중 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어, [6, 2, 1, 4, 3, 5]라는 수열이 있다면마지막 원소 5를 붙일 거라면, 5보다 앞에 있고, 5보다 작은 수로 끝나는 가장 긴 부분 수열에 붙이는 것이 좋다. [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이다. (여러 개 일 수 있다. ) DP를 활용하여 O(N²)으로 구해보기 배열의 숫자를 하나씩 살펴..

• format_list_bulleted JAVA/Algo 개념
• · 2023. 7. 16.
• textsms