📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 이분 탐색 1. times 배열을 오름차순 정렬한다. 2. left는 0으로, right는 times 배열의 마지막 원소 * 사람 수로 정한다. 3. left
이분탐색
📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 투 포인터 ▷ 탐색 대상 : 모든 보석 구매하기 위한 최소 구간 필요 자료구조 - 보석 "종류" 저장용 Set - 보석 "구간" 저장용 Set - 저장용 Map 투 포인터 구간 탐색 위한 int형 변수 - left와 right (초기값 : 모두 0) 1. map에 right쪽에 위치한 보석을 넣는다. 2. left에 위치한 보석이 중복이라면, 보석 갯수를 줄이고, 시작 구간을 1 증가한다. 3. 모든 보석을 탐색했으며 (set1.size() == set2.size()), 최단 구간이..
📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 이분 탐색 ▷ 대상 : 징검다리 건널 수 있는 친구들 수 1. 탐색하는 친구가 건널 수 있다면, 중간 값보다 작은 값들로 모두 건널 수 있음을 의미한다. 그러면 그 때 중간 값보다 많은 인원으로 건널 수 있는지 확인한다. 2. 탐색하는 친구가 건널 수 없다면, 중간 값보다 큰 수로는 건널 수 없음을 의미하므로, 중간 값보다 적은 인원으로 건널 수 있는지 확인한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..
📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS + 이분 탐색 필요 자료구조 - (문자열, 점수 저장하는 리스트) 저장하는 HashMap - DFS로 info가 포함될 수 있는 모든 경우의 수를 HashMap으로 만들어 map에 key로 넣고 점수를 value의 리스트의 값으로 넣어준다. - query를 key로 하는 value들을 가져와 이분 탐색한다. → 그래야 시간초과가 안 난다고 함 HashMap을 사용하는 이유 : 한 번에 바로 탐색하기 위해 💥 유의사항 - 시간 초과 주의 - 이분 탐색 전 HashMap의 val..
🔺 문제 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.util.*; import java.io.*; public class Main { static int[] A; static int N, M; pub..
🔺 문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buffer..
🔺 문제 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.util.*; import java.io.*; public class Main { public static void main(String[] args)..
📍 정의 및 특징 주어진 수열에서 증가하는 순서로 연속되는 부분 수열 중 가장 긴 길이를 구하는 문제 📍 LIS 실행 방법 1) DP 활용 → 시간 복잡도 : O(N^2) 2) 이분 탐색 활용 → 시간 복잡도 : O(N log N) 📍 필요 변수 ✔ DP / LIS 배열 🧩 1) DP를 활용한 LIS 실행 과정 : O(n^2) DP 테이블을 생성하여 각 원소를 마지막으로 하는 LIS의 길이 저장 초기값으로 모든 원소의 LIS 길이를 1로 설정 각 원소 i에 대해, 이전 원소 j(0 nums[j]인지로 판단) 만약 nums[i] > nums[j]라면, dp[i] = max(dp[i], dp[j] + 1) 수행 ⇨ i번째 원소를 마지막으로 하는 LIS의 길이 갱신 모든 i에 대해 위 과정을 반복하면, dp ..
🔺 문제 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) t..
