한달꾸 한달꾸

히스토그램에서 가장 큰 직사각형 click 3달 전에 도전했다가 바로 포기했었던 문제이다. 이번에는 다행히 풀려서 기쁜 마음으로 포스팅한다. 백준에서 처음으로 플레티넘 문제에서 정답을 받았다. 힌트도 없이! 문제 분석 높이가 다른 직사각형 여러 개로 이루어진 히스토그램이 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제이다. 직사각형들을 왼쪽에 위치하는 것 부터 차례대로 stack에 쌓아 나갔다. stack에 직사각형의 높이 정보와 그 직사각형이 왼쪽으로 어디까지 이어질 수 있는지에 대한 정보를 저장했다. stack에는 직사각형의 높이 정보와 왼쪽으로 이어질 수 있는 최소의 index를 저장한다. maxSize에는 직사각형의 최대 높이를 저장하고, 초기값은 0이다. 먼저 높이 2의 직사..

가장 긴 증가하는 부분 수열 click 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾는 문제이다. 가장 긴 증가하는 부분 수열 포스팅 가장 긴 증가하는 부분 수열 3 포스팅 이전에 포스팅을 하긴 했지만, 진정으로 이해하고 포스팅한 것들이 아니라서 굉장히 부실했다. 이번 기회에 보다 자세하게 이분 탐색을 어떻게 사용하는지, Lower Bound는 왜 사용하는지 설명해보려고 한다. 이분 탐색을 이용한 구현을 설명하기 전에 DP로 푸는 방식에 대해서 간단히 짚고 넘어가자. DP - O(N^2) DP에는 해당 숫자가 증가하는 부분 수열을 만들 때, 최대 몇 번째 칸에 위치할 수 있는지에 대한 정보를 저장한다. DP[i]에는 [0, i-1]의 범위에서 value[i] > value[i-1]을 만족하는..

처음으로 CodeForce Contest에 참가해 보았다. Div(1~3) 별로 난이도가 나뉘는데 이중 제일 쉬운 Div3를 시도해 봤다. 총 일곱문제가 출제되었고, 이중 3문제 밖에 풀지 못했다. 첫 시도 치고 나쁘지 않은 것 같지만, 앞으로 자극받고 더 열심히 공부하는 계기로 삼아야겠다. 문제 난이도는 그렇게 어렵다고 느껴지진 않았다. 내 실력이 부족할 뿐... E1문제를 풀고 포스팅해보려 했지만, 계속 시간초과의 벽에 부딪히는 바람에 C-Unique Number 문제로 포스팅할 예정이다. Code Froce - Unique Number click 각각의 인풋 X가 주어졌을 때, 숫자의 각 자리수가 중복되지 않으면서, 모두 더했을 때 X가 되는 가장 작은 수를 찾는 문제이다. 먼저, 10보다 작은 인..

타일 채우기3 2133-타일채우기문제와 유사한 DP문제이다. 포스팅한지 정확히 한달이 지나서 응용문제를 다시 한 번 풀어봤다. DP문제 중에서도 특히 2133번은 블로그에 해설을 아무리 찾아봐도 이해가 안되었던 문제였다. DP문제가 늘 그렇듯 이전단계에서 찾아낸 값을 어떻게 활용할지 찾아내야 하는데, 타일 문제들은 이 부분이 유독 안보였다. 문제 분석 먼저, 세로로 더이상 나눌 수 없게 배치한 경우와 세로로 나눌 수 없는 경우를 구별할 줄 알아야 한다. 이에 관한 것은 2133-타일채우기여기에 포스팅해 놓았으니 참고하자. 2 X N 크기의 타일을 세로로 나눌 수 없게 배치하는 경우를 그려보며 생각해보면 위와 같다. N이 2일때는 3가지가 있으며, 나머지는 모두 두가지씩이다. 자연스럽게 N = 1인 경우 ..

타일 채우기 이번주 내내 고민했던 문제였다. 블로그 풀이들을 봐도 이해가 잘 안됐었는데, 오늘 결국 이해를 해서 다른 블로그들 보다 조금 더 자세하게 설명해보려 한다. 그림을 통해 이해를 시도하기 전에 짚고 넘어가야할 부분이 몇가지 있다. 먼저, N X 3 크기의 벽에서 N이 홀수인 경우에는 2 X 1 타일 혹은 1 X 2 타일로 벽을 완전히 채울 수 없다. 타일의 넓이는 2로 짝수임으로 벽의 넓이도 짝수인 경우에만 벽을 완전히 채울 수 있다. 다음으로, 2 X 3크기의 벽을 채우는 경우의 수는 3가지이다. (그려보자) 마지막으로, N X 3(N%2==0) 크기의 벽에 타일을 배열할 때 1) 세로로 나눌 수 없게_ 배치하는 경우의 수는 2) N에 상관 없이 2가지이다. 1)세로로 나눌 수 없는 경우란? ..

단어 정렬 C++ 정렬 길이가 짧은 것부터 길이가 같으면 사전 순으로 정렬해야 한다. &#39;sort&#39; 함수를 사용해야 한다. sort(arr, arr + n) 배열의 첫 번째 포인터 값과, n번째 포인터 값을 전달해 arr 배열을 오름차순 정렬할 수 있다. 이때, 다른 기준으로 정렬하고 싶다면, 세번째 인자로 정렬 기준을 전달해 줘야 한다. bool Comp(string a, string b) { if (a.length() != b.length()) { return a.length() < b.length(); } else { return a < b; } } int main(){ . . . sort(arr, arr + n, Comp) } True, False를 return하는 &#39;Comp&..

수 정렬하기2 Python의 sort함수를 사용해 문제를 풀고, Quick_sort와 Merge_sort를 추가로 구현해 보았다. sort함수를 사용했을 때 시간이 가장 빨랐고, Merge_sort가 다음, Quick_sort는 시간초과가 발생했다. 어찌 되었든, 목적은 정렬 알고리즘들을 한 번 구현해보는 것이었다. Merge sort를 살펴보자. Merge sort Merge sort(합병 정렬)은 분할 정복을 사용해 정렬하는 방식이다. 분할 정복은 어떤 문제를 더 작은 문제들로 나눠서 해결해 나가는 방식이다. 문제를 분할해 작게 만들고, 작은 문제들을 정복한 후에 이들을 조합해서 원래 문제에 대한 결과를 이끌어 낸다. 6 2 4 1 5 3 을 정렬하는 과정을 그림으로 나타내 보았다. 분할 - 먼저 6..

N-Queen click 비트 연산자를 사용하고, 대칭성을 이용해 첫째 줄에서는 절반까지 탐색하도록 해서 결국 풀 수 있었다. 유독 시간제한이 심하게 빡빡한 것 같다. 크기가 N X N인 체스판 위에 퀸 N 개를 공격할 수 없도록 배치하는 문제이다. 처음 문제를 풀 때, 배열로 체스판을 실제로 만든 다음에 퀸을 가능한 자리에 배치하고 그 자리에서 공격할 수 있는 구역들을 모두 표시해 주는 식으로 풀었다. 하지만, 당연하게도 시간 초과가 발생해서 다른 방법을 찾아 풀어야 했다. 위의 그림과 같이 퀸을 특정 칸에 배치하면, 해당 칸으로부터 가로, 세로 그리고 대각선에 퀸을 놓을 수 없게 된다. 이때, 퀸을 배치한 자리로부터 한 칸씩 아래 칸으로 내려갈 때마다 대각선 성분들이 한 칸씩 좌우로 멀어져 가는 것을..