도전 (4) 썸네일형 리스트형 백준 알고리즘 중급 - 분할정복 (도전) 도전 문제답게 어렵다. 어느정도 고민의 시간을 가지고, 분석한다는 마음으로 코드를 따라갔다. 정리 시작! - * 스카이라인 (high) : 건물의 정보가 주어졌을 때, 스카이라인을 구하는 문제다. 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오� www.acmicpc.net - 처음엔 높은 건물부터 정렬해서 위치별로 중복되지 않게 스카이라인을 구해보려고 했다. 하지만 건물의 위치와 높이 범위가 1억이나 되고.. 중복을 표시할 수 있는 방법이 없기에.. 무리였다. 분할 정복이니 머지를 이용할텐데.. 어떤 식으로 .. 백준 알고리즘 중급 - 그리디 알고리즘 (도전) 3문제 뿐이었지만, 도전 챕터답게 무게감 있는 문제들이었다. 내 힘으로 풀어내지는 못 했지만.. 문제 풀이 과정을 익히는 것만으로도 충분히 가치 있었다. 추후에 써먹을 곳이 많을 것 같으니 잘 정리해두자. 정리 시작! - * NMK (high) : N까지의 자연수를 LIS가 M, LDS가 K가 되도록 나열하는 문제다. 1201번: NMK 1부터 N까지의 수를 한 번씩 이용해서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 출력한다. www.acmicpc.net - 우선 N값의 범위를 생각해줘야 한다. 최솟값은 어떻게 될까? 증가하는 숫자가 최소 M개, 감소하는 숫자가 최소 K개 있어야 한다. 증가와 감소의 분기점 또한 존재할 것이므로 중복을 하나 빼준다. 따라서 N은 .. 백준 알고리즘 기초 - 그래프1 (도전) 푹 쉬고 나니 좀 낫다. 뭘 해도 건강이 우선이다. 다시 차근차근 해나가보자. 정리 시작. - * BFS 스페셜 저지 (mid) : 주어진 경우가 bfs 탐색이 맞는지 확인하는 문제다. 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net - 처음엔 단순하게 모든 bfs 경우를 생각했을 때 해당 경우가 나오는지 생각해서 풀어봤다. #include #include #include using namespace std; int n, cnt = 1; vector a[100000], ans; bool check[100000]; void bfs(int e) { queue q; check[e] = true; q.push(e); while (!q.. 백준 알고리즘 기초 - 다이나믹 프로그래밍 (도전) 난이도가 높은 새로운 문제를 풀줄 알았는데, 기존의 문제를 좀 더 어려운 방법으로 풀거나 조건을 더 추가해서 푸는 식이었다. 새로운 문제를 푸는 것 보다 훨씬 와닿는 도전이었다. '이걸 이렇게 더 빨리 풀 수 있구나' 하는 깨달음도 얻었다. 벌써 dp 챕터의 마지막 강의다.. 정리 시작 해보자! - * 동물원 (high) : 2차원으로 풀던 걸 1차원으로 풀었다. 배열을 어떻게 정의하느냐가 관건이다. 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net - 기존에는 d[i][j]로 두고, i번째 줄에 j 경우일 때까지의 경우의 수로 생각했는데, 이번엔 일차원 배열로 생각해본다. - d[i]를 i번째에 동물이 무조건 들어가 있는 i번째까지의 경우의 .. 이전 1 다음
