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

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

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

[프로그래머스] 이중우선순위큐 - TreeMap

문제링크 🚩 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ​ 📕 문제 접근 📕 값을 최대 값과 최소 값을 제거해야한다. 들어갈 때 정렬이 되어서 들어가야한다 이 두가지 특성을 고려했을 때 TreeMap을 이용하여 문제를 해결하면 될 것 같다는 생각이 들었다 💻 Code 💻 import java.util.*; class Solution { public int[] solution(String[] operations) { TreeMap tree ..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 7. 26.
• 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

[백준] 11505.구간 곱 구하기 - 세그먼트트리(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 📕 문제 접근 📕 - 세그먼트 트리의 입문 문제로 구간 합 구하기과 매우 유사한 문제 입니다- 다만 곱이나보니 mulTree 함수를 만들 때 return 값에 유의하여 0이 아닌 1이 반환되도록 하였습니다. -> 0을 곱해버리면 결과가 0이 나오기 때문. 💻 Code 💻 import java.io.BufferedReader..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 7. 14.
• textsms

SegmentTree 개념

💡 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 연산을 진행하기 위해 사용하는 자료구조 문제인식 N개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지의 합을 구하는 것은 어려운 일이 아니다. 예를 들면, 아래 배열에서 5번째에서 11번째 까지 더하는 방법은 그냥 배열을 돌면서 더하면 된다. 그 시간 복잡도는 대략 O(N) 이다. 하지만 이와 같은 a, b의 쌍이 M개 주어졌을 때는 O(M*N) 이 된다. 너무 오래 걸리니까 더 좋은 방법을 찾아보자. 구간 합을 구할 때마다 N을 전부 도는게 너무 오래 걸린다면, 특정 구간의 합을 미리 저장하고 이 값들의 합을 구해보자. 이때, 이진 트리를 활용할 수 있다. 트리 생성 구간 합을 저장해 보자. 이 전체 의 합은 66이다. 이 구간의..

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