본문 바로가기

알고리즘72

[코테 직전 유형 정리] - 그리디 다양한 종류의 문제가 존재하는 유형이다. 유형 1. 구간 내 최소 개수 사용하기특정 구간 내에서 몇 개를 설치해야 전체를 커버할 수 있느냐 ~ 이런 유형의 문제이다.풀이 방법만 알면 되게 쉽게 풀 수 있다.진출 시점 (끝점) 기준으로 오름차순 정렬반복문 순회하며 현재 진입시점이 이전 진출 시점보다 작으면 넘어가고, 현재 진입시점이 이전 진출 시점보다 크면 갱신하는 방식 아래 두 문제가 굉장히 유사한 문제다.단속 카메라https://school.programmers.co.kr/learn/courses/30/lessons/42884def solution(routes): answer = 1 # 시작지점에 1개 routes = sorted(routes, key=lambda x: (x[1], x[0]).. 2025. 3. 22.
[코테 직전 유형별 정리] - 이분탐색 알고리즘 문제 중에서 그나마 쉬운 유형에 속하는 것 같다. 탐색 알고리즘 자체는 정형화되어 있으니... 다만 다른 문제 유형이랑 섞이기 시작하면 이제 골치아파지는거다.  유형 1. 단순 탐색 문제이분탐색이 쉽게 나오면 그냥 목표 값을 찾기만 하면 되는 문제가 나온다.목표 값만 잘 설정해두면 low, high 나눠서 찾기만 하면 되니까, 가장 쉬운 난이도의 유형이라 볼 수 있다.용액https://www.acmicpc.net/problem/2467산성 +, 알칼리성 - 용액을 더해서 0에 최대한 가깝게 하는 문제.당연하게도 ph 농도 자체를 탐색 대상으로 잡으면 된다."""어떤 것을 이분탐색 대상으로 놓을지 잘 선택해보자산성 양수 / 알칼리성 음수0에 가장 가까워야 함1. sort를 해요2. min max .. 2025. 3. 21.
[코테 직전 유형별 정리] - DP 개인적으로 내가 가장 어려워하는 유형의 문제다. 학생 시절때부터 수열/점화식에 약해서..... 그래서 복습을 빡세게 해야겠다.유형 1. 단위 숫자로 경우의 수 구하기DP의 대표적인 유형 문제라 볼 수 있다. 아마 DP 풀면 제일 먼저 풀게 될 유형이기도 하고...연산에 사용될 수 있는 숫자가 화폐 단위처럼 특정 단위로 나눠져있는 경우이다.거스름돈https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 고정된 단위 숫자로 목표 숫자를 만들어낼 수 있는 경우의 수를 구하는 문제.# n원을 만들기 위한 경.. 2025. 3. 21.
[코테 직전 유형별 정리] - DFS / BFS 코테 시즌을 맞아 내가 풀어본 문제를 유형별로 풀이 방법을 나눠보고자 한다.이런거 커버하면 정형화된 문제는 대부분 잘 풀리는 듯? 유형 1. 그냥 탐색만 하면 되는 방식크게 신경쓸 거 없이 그냥 탐색만 하면 되는 방식너무 단순해서 그런가 잘 나오지는 않는 듯 게임 맵 최단거리https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 전형적인 탐색 + 이동 문제 → 장애물 피해서 목적지까지 도달하는 문제# 칸의 최솟값# BFS로 풀고 카운트# 상하좌우 이동 가능from collections import d.. 2025. 3. 21.
[프로그래머스] 징검다리 문제https://school.programmers.co.kr/learn/courses/30/lessons/43236# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이전에 풀었던 '징검다리 건너기' 문제와는 비슷하면서도 살짝 다른 문제이다.  주요 아이디어1. 목표값인  "각 지점 사이 거리의 최소값 중에서 가장 큰 값" 을 이분탐색 대상으로 가진다.이게 말이 조금 헷갈리는데,n개 이하의 바위를 파괴하는 모든 경우의 수에서max (min(x1, x2 파괴 시), min(x2, x3 파괴 시) ...) 를 의미한다.그럼 모든 n개의 돌을 파괴해서 최소값 비교하면 안되나??당연히 이분탐색 문제기때문에 시.. 2025. 1. 22.
[BOJ] 1931. 회의실 배정 문제https://www.acmicpc.net/problem/1931    주요 아이디어이전에 풀었던 그리디 문제 (요격 시스템, 단속 카메라) 와 비슷한 유형이다!1. 끝나는 시간을 기준으로 오름차순 정렬을 진행한다.1-1. 이 때, 끝나는 시간이 같을 경우 시작 시간이 빠른 회의를 우선적으로 배치해야 최대 개수 탐색이 가능하므로 2차 정렬 기준을 시작 시간으로 잡는다. 반례 예제 : 시작하자마자 끝나는 회의 input 이 잡힐 경우 에러가 발생하는데,42 21 22 33 4x[1] 기준 정렬 : [(2, 2), (1, 2), (2, 3), (3, 4)]이런 경우 그리디하게 앞에서부터 탐색하면  (2,2)가 빠지게 되므로, 시작 시간이 빠른 회의를 우선적으로 배치해야 한다.  2. 이전 미팅 시작 시간.. 2025. 1. 22.

티스토리툴바