본문 바로가기

알고리즘/백준 알고리즘 강의

 (40)
백준 알고리즘 중급 - 브루트 포스(문제2) * 숫자 재배치 (low) : 두 정수 a, b가 주어지고 a에 포함된 숫자를 섞어서 새로운 수 c를 만든다고 할 때 b보다 작거나 같으면서 가장 큰 c값을 구하는 문제다. www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicpc.net #include #include #include using namespace std; int main() { string a; int b; int ans = -1; cin >> a >> b; sort(a.begin(), ..
백준 알고리즘 중급 - 브루트 포스(문제) 쭉쭉 풀어보자. * 차량 번호판 1 (mid) : 조건을 만족하는 차량 번호판 개수를 구하는 문제다. 16968번: 차량 번호판 1 00부터 99까지 총 100가지 중에서 00, 11, 22, 33, 44, 55, 66, 77, 88, 99가 불가능하다. www.acmicpc.net - 같은 글자가 두 번 연속해서 나타나면 안 된다는 조건은, 무조건 그 앞의 숫자랑만 다르면 되는 거니까 맨 앞에는 n, 그 다음부터는 쭉 n-1이라고 보면 된다. #include #include #include using namespace std; int main() { int ans = 1; string num; cin >> num; int cC = 0, cD = 0; int ch = 26, d = 10; for (int..
백준 알고리즘 중급 - 이분 탐색 (연습) 하나 정리해둘 것 : 최댓값의 최솟값, 최솟값의 최댓값을 구하라고 하면 이분 탐색이라고 보면 된다. 중급 1 마지막 강의다. 여기까지 정리하고, 당분간은 자소서 쓰기 바쁠 것 같다. 정리 시작! - * 기타 레슨 (mid) : 가능한 블루레이의 길이 중 최소를 구하는 문제다. 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net - n개의 레슨을 m개의 블루레이에 저장하려고 한다. 구하려는 최댓값의 최솟값은 블루레이의 크기다. - left는 레슨 중 가장 긴 값을 넣는다. 그러면 모든 레슨을 하나씩 담을 수 있을 거다..
백준 알고리즘 중급 - 이분 탐색 이분 탐색에 대해 ARABOJA - * 이분 탐색 (binary serach) : 어떤 기준을 가지고 yes or no 판별을 반복하여 답을 구하는 방법이다. - 가능한 정답의 최솟값 (left), 최댓값 (right), yes or no 판별 함수가 필요하고 조건에 따라 값이 더 커지거나 작아진다. - 어느정도의 포맷이 있어서 좀 적응하면 문제의 해결의 틀은 비교적 쉽게 잡힌다. 바로 예제 풀어보자. * 수 이어 쓰기 (mid) : n까지 수를 이어서 썼을 때, k번째 수가 뭔지 찾는 문제다. 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.ne..
백준 알고리즘 중급 - 정렬 기본 중에 기본이 되는 알고리즘. 그만큼 중요하다. 중요하고 자주 사용되는 만큼, 대부분의 정렬 함수는 C++에서 표준 함수로 제공한다. 하지만 정렬 자체로는 그리 의미 있는 문제가 많이 없어서 간단하게 중요한 개념 정리하고, 풀면서 조금 헷갈렸던 문제를 꼽아 정리했다. 정리 시작! - * 정렬 (Sorting) : 리스트에 담긴 자료를 어떠한 순서로 나열하는 것. 선택, 버블, 삽입, 퀵, 힙, 병합 등 다양한 정렬 알고리즘이 있는데.. 그냥 빠른 걸 사용하면 된다. 확장성을 가지려면 O(nlogn)이 걸리는 정렬을 사용해야 한다. 보통 STL로 제공되는 sort 함수를 사용하는데, 이는 퀵 정렬을 기반으로 한다. - 기본값은 오름차순이지만, 여러 값을 기준으로 정렬하고 싶으면 함수를 따로 만들면 된다..
백준 알고리즘 중급 - 분할정복 (도전) 도전 문제답게 어렵다. 어느정도 고민의 시간을 가지고, 분석한다는 마음으로 코드를 따라갔다. 정리 시작! - * 스카이라인 (high) : 건물의 정보가 주어졌을 때, 스카이라인을 구하는 문제다. 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오� www.acmicpc.net - 처음엔 높은 건물부터 정렬해서 위치별로 중복되지 않게 스카이라인을 구해보려고 했다. 하지만 건물의 위치와 높이 범위가 1억이나 되고.. 중복을 표시할 수 있는 방법이 없기에.. 무리였다. 분할 정복이니 머지를 이용할텐데.. 어떤 식으로 ..
백준 알고리즘 중급 - 분할정복 (연습) 감을 잡을 것 같으면서도 못 잡겠다. 많이 헤맸던 챕터였다. 그만큼 꼭꼭 씹고 넘어가자. 정리 시작. - * 종이의 개수 (mid) : 종이가 모두 같은 수면 그 종이를 사용하고, 아니면 9개로 나눠서 앞의 조건을 다시 검사해준다. 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net - 모든 수가 같은가? -> yes : 해당 수 count +1 / no : 9개로 분할 (재귀) #include #include using namespace std; int a[2187][2187]; int c[3] = ..
백준 알고리즘 중급 - 분할정복 분할 정복에 대해 간단하게 정리해보자. - * 분할 정복 (Divide & Conquer) : 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 푸는 것. - '나눠서 푼다'는 점에서 DP와 같지만, DP는 문제가 겹쳐서 메모를 이용해야 하고, 분할 정복은 문제가 겹치지 않는다. * 이분 탐색 (Binary Search) : 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘. 크기가 N일 때, O(logN). - 중간값과 비교해서 범위를 조금씩 좁혀 가면 된다. 예제를 한번 풀어보자. - 숫자 카드 (low) : 숫자 카드 중에 구하려는 값이 있는지 판별하는 문제다. 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 ..

티스토리툴바