본문 바로가기

알고리즘

 (43)
백준 알고리즘 중급 - 분할정복 (도전) 도전 문제답게 어렵다. 어느정도 고민의 시간을 가지고, 분석한다는 마음으로 코드를 따라갔다. 정리 시작! - * 스카이라인 (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)이 주어진다. 둘째 ..
백준 알고리즘 중급 - 그리디 알고리즘 (도전) 3문제 뿐이었지만, 도전 챕터답게 무게감 있는 문제들이었다. 내 힘으로 풀어내지는 못 했지만.. 문제 풀이 과정을 익히는 것만으로도 충분히 가치 있었다. 추후에 써먹을 곳이 많을 것 같으니 잘 정리해두자. 정리 시작! - * NMK (high) : N까지의 자연수를 LIS가 M, LDS가 K가 되도록 나열하는 문제다. 1201번: NMK 1부터 N까지의 수를 한 번씩 이용해서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 출력한다. www.acmicpc.net - 우선 N값의 범위를 생각해줘야 한다. 최솟값은 어떻게 될까? 증가하는 숫자가 최소 M개, 감소하는 숫자가 최소 K개 있어야 한다. 증가와 감소의 분기점 또한 존재할 것이므로 중복을 하나 빼준다. 따라서 N은 ..
백준 알고리즘 중급 - 그리디 알고리즘 (연습) 뭐랄까.. 문제 자체는 그렇게 복잡하지 않았는데.. 지나치게 많은 시간이 소요된다. 어찌된 노릇일까. 속도를 좀 더 빠르게 할 수는 없을까..? ㅠㅠ뭐 실력이 쌓이면 속도도 자연스럽게 빨라지겠지.. 의식적으로도 시간을 단축하기 위해 슬슬 노력하자. 정리 시작! - * 잃어버린 괄호 (mid) : 식에 괄호를 적절하게 쳐서 최소값을 구하는 문제다. 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net - 마이너스가 나오는 순간부터 그 뒤는 모두 마이너스가 된다는 것만 알면 바로 풀 수 있다. 근데 그게 생각 안..
백준 알고리즘 중급 - 그리디 알고리즘 - 2 이번 챕터에서는 얻을 게 엄청 많았다. 특히 큰 수가 들어갈 때 항상 쩔쩔 맸는데, 전환점이 될 수도 있을 정도로 많은 것을 얻은 것 같다. 체크 해뒀다가 잘 써먹어보자. 이제 효율적인 공부 흐름을 어느정도 터득한 것 같다. 이 흐름대로 꾸준히 잘 해보자. 정리 시작! - * 보석 도둑 (high) : 보석 도둑이 훔칠 수 있는 최댓값을 구하는 문제다. 어려웠다. 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net - 보석의 가격을 기준으로 한 풀이와 무게를 기준으로 한 풀이, 2가지의 해결법이 있다. 보..
백준 알고리즘 중급 - 그리디 알고리즘 - 1 이미 풀어본 문제가 많아서 빠르게 클리어 했다. 그땐 쩔쩔 맸던 문제들이 지금은 수월하게 풀린다는 것에 놀라기도 했다. 패턴을 찾아도 알고리즘을 짜는 게 은근 까다로워서 고생한 문제도 있었다. 정리 해보자! - * 그리디 알고리즘 : 결정해야 하는 그 순간에 가장 좋다고 생각하는 것을 찾아가며 답을 찾아가는 알고리즘이다. 뒤이에 올 것은 생각하지 않고 그때 그때 가장 좋은 선택을 한다고 욕심쟁이라는 이름이 붙었다. 바로 예제로 들어가보자. * 동전 0 (low) : 가장 간단한 그리디 문제인 거스름돈 문제다. 필요한 동전 개수의 최솟값을 구하면 된다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 ..
백준 알고리즘 중급 - BFS (연습) - 2 정말 늪같은 챕터였다.. 문제도 많고.. 어려웠어.. 하지만 그만큼 많은 걸 배웠다. 근데 제발 시간을 재면서 풀자. 한번 매달리면 거의 하루종일 그 문제만 쳐다보는데.. 끈기는 좋지만 효율이 안 나온다. 똑똑하게 공부하자. 정리 시작! - * 벽 부수고 이동하기 (mid) : 벽을 하나까지 부술 수 있는 조건에서 최단 경로를 구하는 문제다. 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net - 벽을 부쉈는지, 안 부쉈는지까지 생각해서 기록해줘야 한다는 것이 포인트였다. #inclu..

티스토리툴바