알고리즘 (104) 썸네일형 리스트형 [알고스팟] 울타리 잘라내기 문제 링크 울타리 잘라내기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)FENCE3000ms131072kb94872890 (30%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비.. [알고스팟] 쿼드 트리 뒤집기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)QUADTREE10000ms65536kb57762760 (47%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N× 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.이.. [분할 정복] 분할 정복에 대해서 알아보자 분할 정복은 이름 그대로 문제를 작은 부분으로 쪼개어서 해답을 찾은 뒤에 작은 조각들을 합치면서 다시 해답을 찾아내가는 방식입니다. 대표적인 분할 정복 방식으로는 병합 정렬이 있습니다. 위 그림에서 보듯이 병합 정렬은 배열을 반씩 쪼개서 가장 작은 단위로 쪼갠 다음에 정렬하고, 이 정렬된 배열을 점차적으로 정렬하는 방식입니다. 분할 정복을 할 때 가장 중요하게 고려해야 할 점이 있습니다. 바로 조그만 조각에서 나온 최적해를 이용해서 구해나간 답이 결국 최종 해답과 일치해야 한다는 것입니다. 작은 조각에서 나온 답이 결국 더 큰 조각에서는 쓸모가 없어진다면 의미없는 일을 한 것이겠죠... 또 다른 예로는 행렬의 거듭제곱을 구하는 코드가 있습니다. 보통의 방법으로 행렬의 m 제곱을 구하게 되면, n x n의.. [정렬] 병합 정렬 ( Merge Sort) 오늘은 정렬 방법 중에 하나인 '병합 정렬'에 대해서 알아봅시다! 분할 정복에 대해 간단히 설명하면, 하나의 큰 덩어리를 작게 분할하여 해결하고, 이 작은 덩어리들을 묶어서 또 다시 해결을 하다보면 최종적으로 자신이 원하는 답을 찾는다는 것입니다. 어디서 많이 들었던 소리이지 않습니까?! 바로 재귀 함수에서 나왔던 개념입니다!따라서, 분할 정복은 재귀를 통해서 해결하는 경우가 많습니다. 어쨌든, 이 병합 정렬도 분할 정복을 통해 정렬하는 방법입니다. 방법은 간단합니다! 데이터를 한 조각이 남을 때까지 계속해서 쪼개고, 쪼개고, 또 쪼갭니다.그리고 쪼개진 것들끼리 정렬을 하고, 이를 이용해서 만들어진 조금 큰 조각을 또 정렬을 하는 방법입니다! 그림으로 확인해봅시다! 그림에서 처럼 우선 데이터를 반 씩 쪼.. [완전탐색/부분집합] 비트를 이용하여 모든 부분집합을 구하자! 부분 집합이란 전체의 집합에서 하나의 원소를 '고른다 / 안 고른다' 두 가지의 경우에 대해 살펴보는 것이므로 2^n 가지의 경우가 나옵니다. 이는 비트를 이용하면 굉장히 쉽게 구할 수 있습니다! 왜냐하면 비트는 이진수이기 때문에, 하나의 자리수마다 고른다 (1) / 안 고른다(0)을 설정할 수 있기 때문입니다! 우선 코드를 보겠습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 #include#include#include int arr[10]; void print(int bit){ int idx = 0; while (bit) { if (bit & 1) { printf("%d ", a.. [완전탐색] 완전탐색에 대해 알아보자 완.전.탐.색! 말 그대로 무식하게 모든 경우를 다 보는 것입니다!컴퓨터의 가장 강한 이점인 '속도'를 극한으로 이용할 수 있는 방법입니다.보통 완전 탐색은 최적화 문제에서 많이 사용합니다.최적화 문제란, 여러가지 경우를 만들 수 있을 때, 가장 적합한 답의 경우를 구하는 문제를 말합니다.예를 들면, 마을 사이를 잇는 도로가 있고 도로마다 거리가 다를 때, A에서 B로 가는데 가장 짧은 도로의 길이를 구하는 문제가 있습니다.이와 같은 문제를 풀 때 완전탐색을 이용하면 A에서 B로 가는 모든 도로의 경우를 구한 뒤에 그 중 거리가 가장 짧은 값을 답으로 선정합니다.물론, 완전탐색을 이용해서 문제를 풀기 위해서는 문제의 조건에서 주어진 시간 내에 풀 수 있을지 잘 생각해보아야 합니다.완전탐색을 너무 많이하면.. [완전탐색/조합] 비트 연산을 이용하여 조합 만들기 - 비트 조합 예전에 대학생활을 하면서 '로봇 연구회' 동아리 활동을 하면서 아트메가 128을 사용했기 때문에 비트연산을 이용한 경험이 있습니다. 덕분에 프로그래밍을 하면서 비트를 이용해서 문제를 해결한 적이 있는데, 이번에는 그 중에서도 특히 인상 깊었던 '조합 만드는 법'에 대해서 설명하려고 합니다! 우선, 그 전에 비트 연산에 대해서 간단히 알아봅시다. 1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. ex) 0b 1111 & 0b 0011 = 0b 0011 2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.ex) 0b 1100 | 0b 1010 = 0b 1110 3. ~ : 모든.. [종만북] 소문의 책을 구입하다. 많은 개발자들의 컵라면 받침대로 사용되고 있다는 종만북!! 두께마저도 정말로 두꺼웠습니다. 1권 2권 합쳐서 약 1천 페이지 정도라서 꽤 놀랐습니다. 알고리즘을 배우기 위해 입문할 때 많이 읽는다고 소문을 많이 들었기 때문에 이번에는 이 책을 다 읽어보려고 합니다. 실은 책을 산 지는 꽤 되었지만! 블로그를 시작한 것은 얼마 안되었기에! 마치 처음 보는 것 처럼 얘기하겠습니다! 종만북 1권 보다는 먼저 2 권을 읽는 분들이 많은 것 같습니다. 일단은 목차를 보면서 '알고리즘' 위주로 볼 생각이지만, 아마 앞에서부터 읽을 것 같습니다. 종만북을 라면 받침대로는 절대 사용하지 않으리..! 참! 종만북에는 알고리즘을 설명하면서 그 알고리즘에 대한 문제도 다수 존재합니다. 이 문제들은 '알고 스팟'이라는 홈페이.. 이전 1 ··· 10 11 12 13 다음
