[알고리즘] 투 포인터(Two Pointers)란?

투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에서 연속된(정렬이 아닌) 부분 배열을 통해 문제를 해결할 수 있어야 합니다. 투 포인터 알고리즘을 활용하는 대표적인 예로는 배열에서 특정한 합을 갖는 부분 연속 수열을 찾을 때가 있습니다. 만약 이중 반복문을 통해 부분 연속 수열을 찾는다면 O(n^2)의 시간복잡도가 소요되는 반면 투 포인터를 활용한다면 O(n)의 시간복잡도로 시간을 단축 시킬 수 있습니다. 투 포인터는 두 개의 포인터를 사용하기 때문에 두 개의 인덱스를 가르키는 변수가 필요합니다. 그 변수를 하나는 "시작점을 가르키는 start", 다른 하나는 "..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 27.
• textsms

[Java/자바] 프로그래머스 Lv2 - 연속 부분 수열 합의 개수 (Set)

문제 설명 철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다. 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 3 ≤ elements의 길이 ≤ 1,000 1 ≤ el..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 1. 26.
• textsms

[알고리즘] LIS(최장 증가 부분 수열)이란 ?

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열 최장 증가 부분 수열은 말 그대로 가장 길게 증가하는 부분 수열으로 즉, 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열을 LIS라고 합니다. 좀 더 이해하기 쉽도록 아래 그림을 봅시다. 만약 위와 같은 배열이 있을 때 만들수 있는 증가 부분 수열은 위와 같으며 최장 증가 부분 수열은 만들 수 있는 증가 부분 수열 중 길이가 가장 긴 [1, 2, 6]이 됩니다. LIS를 구현하는 방법으로는 두가지가 있습니다. DP [알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법 동적 프로그래밍(Dynamic programming) 란? 동적 프로그래밍은 "큰 문제"를 "부분 문제"로..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 26.
• textsms

[Java/자바] 프로그래머스 Lv2 - k진수에서 소수 개수 구하기

문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 P처럼 소수 양쪽에 아무것도 없는 경우 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다. 예를 들어, 101은 P가 될 수 없습니다. 예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 1. 25.
• textsms

[Java/자바] 프로그래머스 Lv2 - 타겟 넘버 (DFS 깊이 우선 탐색)

문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 100..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 1. 22.
• textsms

[Java/자바] 프로그래머스 Lv2 - 귤 고르기 (getOrDefault 활용)

문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 1. 21.
• textsms