[코딩테스트] 정렬, 이진 탐색, 누적합 프로그래머스 문제 모음

Ⅰ. 정렬 (Sort)

1. K번째 수 (42748, Lv1)

• i ~ j 구간 잘라서 정렬 후 k번째 수를 고르는 기본적인 정렬 연습용 문제
• 부분 배열 자르기 + Arrays.sort() 패턴 연습용으로 좋음

https://school.programmers.co.kr/learn/courses/30/lessons/42748

 

---

 

2. 문자열 내 마음대로 정렬하기 (12915, Lv1)

• 문자열 배열을 n번째 문자 기준으로 정렬하는 문제
• Comparator / 람다로 정렬 기준 (custom key) 주는 연습에 좋음

https://school.programmers.co.kr/learn/courses/30/lessons/12915

 

---

 

3. 가장 큰 수 (42746, Lv2)

• 숫자들을 이어붙여 만들 수 있는 가장 큰 수를 만드는 문제
• (a + b) vs (b + a) 비교하는 방식으로 정렬 기준 설계 연습 가능

https://school.programmers.co.kr/learn/courses/30/lessons/42746

 

---

 

4. H-Index (42747, Lv2)

• 논문 인용 횟수 배열을 정렬하고 조건을 만족하는 최대 h를 찾는 문제
• 정렬 후 조건 체크 패턴에 익숙해지기 좋음

https://school.programmers.co.kr/learn/courses/30/lessons/42747

 

---

 

5. 숫자 게임 (12987, Lv3, 그리디 + 정렬)

• 두 배열을 정렬해놓고 그리디하게 매칭해서 점수를 최대화 하는 문제
• 정렬 후 투 포인터/그리디 조합 연습에 좋음

https://school.programmers.co.kr/learn/courses/30/lessons/12987

 

---

 

Ⅱ. 이진 탐색 (Binary Search)

1. 입국심사 (43238, Lv3)

• 시간을 이분 탐색해서, 주어진 사람 수를 처리할 수 있는 최소 시간을 찾는 전형적인 파라메트릭 서치 문제
• 이분 탐색 템플릿을 몸에 익히기 딱 좋은 대표 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

 

---

 

2. 징검다리 (43236, Lv4)

• 바위를 n개 제거했을 때, 인접 거리의 최소값을 최대화하는 문제
• 답(최소 거리)을 이분 탐색하는 전형적인 결정 문제 패턴

https://school.programmers.co.kr/learn/courses/30/lessons/43236

 

---

 

3. 징검다리 건너기(64062, Lv3, 카카오)

• 최대 몇 명까지 징검다리를 건널 수 있는지 묻는 문제
• 사람 수를 기준으로 이진 탐색하고, 해당 인원으로 건널 수 있는지 체크하는 방식으로 많이 풀이함

https://school.programmers.co.kr/learn/courses/30/lessons/64062

 

---

 

4. 순위 검색 (72412, Lv2, 2021 KAKAO BLIND)

• info 조합을 미리 정해두고, 각 조건에 맞는 점수 리스트에서 점수 기준으로 lower_bound/upper_bound 이분 탐색하는 문제
• 문자열 전처리 + 맵 + 이분 탐색 조합 연습용으로 좋음

https://school.programmers.co.kr/learn/courses/30/lessons/72412

 

---

 

Ⅲ. 누적합

1. 연속 부분 수열 합의 개수 (131701, Lv2)

• 원형 수열에서 가능한 모든 연속 부분 수열의 합의 개수를 구하는 문제
• 원형을 2배 배열로 펼치고, 누적합 + 구간합으로 풀이하는 방식이 많이 쓰임

https://school.programmers.co.kr/learn/courses/30/lessons/131701

 

---

 

2. 파괴되지 않은 건물 (92344, Lv3, 2022 KAKAO)

• 2차원 맵에서 직사각형 범위에 여러 번 데미지/회복을 준 후, 살아남은 건물 개수를 세는 문제
• 단순 구현하면 시간 초과 → 2D 차분 배열 + 누적합(구간합)을 써야 통과

https://school.programmers.co.kr/learn/courses/30/lessons/92344

 

---

 

3. 광고 삽입 (72414, Lv3, 2021 KAKAO)

• 시청 로그를 이용해 어느 구간에 광고를 넣으면 시청 시간이 최대인지 찾는 문제
• 초 단위 배열을 만들어 시청자 수 → 누적합 → 구간합으로 해결하는 전형적인 1D 누적합 + 슬라이딩 윈도우 문제

https://school.programmers.co.kr/learn/courses/30/lessons/72414

불러오는 중입니다...