BerryDevelop

백준 11663번 문제에서 lower_bound와 upper_bound 적용문제 요구사항점 xxx가 선분 [l,r][l, r][l,r]에 포함되는지 확인하려면 l≤x≤rl \leq x \leq rl≤x≤r를 만족해야 합니다. 이를 효율적으로 계산하기 위해 선분의 시작점과 끝점을 각각 정렬하고 이분 탐색을 활용합니다.적용 방법정렬된 시작점 배열 (starts)에서 l≤xl \leq xl≤x를 만족하는 시작점의 개수를 upper_bound로 구합니다.정렬된 끝점 배열 (ends)에서 rrx를 만족하는 끝점의 개수를 lower_bound로 구합니다.점 xxx를 포함하는 선분의 개수는: {포함 선분 개수} = upper_bound - lower_bound lower_bound와 upper_bound의 차이점과 ..

DFS, BFS, 다익스트라, DFS+DP, 백트래킹 문제 유형 정리문제에서 사용해야 할 알고리즘 유형은 입력 범위, 문제 요구사항, 시간 복잡도, 그래프 구조를 기준으로 구별할 수 있습니다. 아래는 각 유형의 특징, 시간 복잡도, 입력 범위, 적용 예시, 구별 기준을 한눈에 정리한 표입니다.1. DFS (Depth-First Search)특징:한 경로를 끝까지 탐색한 뒤, 백트래킹하면서 다른 경로를 탐색.트리나 그래프의 경로 조사, 특정 조건을 만족하는 경로 찾기.시간 복잡도:그래프 전체 탐색: O(V+E)O(V + E)O(V+E) (V: 정점, E: 간선).경우의 수 탐색: O(2N)O(2^N)O(2N) (예: 모든 경로 탐색).입력 범위:노드 수 V≤103V \leq 10^3V≤103 (그래프가 작..

DFS와 DP를 함께 사용하는 문제 유형은 최적 경로 탐색, 특정 상태에서의 최적화 문제, 또는 경로 개수를 구하는 문제에 자주 등장합니다. 아래는 DFS + DP를 사용하는 대표적인 문제와 관련 백준 문제 목록입니다.1. 경로 탐색 및 최적화 문제이 유형은 그래프나 격자에서 특정 조건에 맞는 경로를 찾거나, 경로의 수를 세거나, 경로의 최적값을 계산하는 문제입니다.추천 문제백준 1520 - 내리막 길DFS로 가능한 모든 경로를 탐색하고, DP로 중복 계산을 방지하여 경로 수를 효율적으로 계산.백준 11403 - 경로 찾기그래프에서 특정 정점 간에 경로가 존재하는지 확인하는 문제로, DFS와 DP를 통해 경로 여부를 기록.백준 1240 - 노드 사이의 거리그래프에서 두 노드 간의 거리를 구하는 문제로, ..

문제왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.입력아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.출력일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황에서 사용 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작함. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 다익스트라 알고리즘 동작 과정 출발 노드를 설정한..

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과는 별도의 메모리영역에 저장하여 다시 계산하지 않도록 함 일반적으로 탑다운과 보텀업 방식으로 구성 탑다운: 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식 보텀업: 작은 문제부터 차근차근 답을 도출하는 방식 동적 계획법 -> 자료구조에서 동적할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다. 다이나믹 프로그래밍에서의 다이나믹은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해..

이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 좁혀간다 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 (ex: 선택 정렬에서 매 단계마다 가장 작은 값 찾기) 이진탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례함. 예를 들어 초기 데이터 개수가 32일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남음. 2단계 : 8개 가량 3단계 4개 가량 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장함 #이진 탐색 소스코드 구현(재귀함수) def binary_searc..

문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20)..

정렬(Sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 각 정렬 알고리즘 비교 정렬 알고리즘 핵심 아이디어 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법 O(N^2) O(N) 아이디어가 매우 간단합니다. 삽입 정렬 데이터를 앞쪽에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때 가장 빠름 퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 O(NlogN) O(N) 대부분에 경우에 가장 적합 충분히 빠름 계수 정렬 특정한 값..

문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은..