배열 검색 결과

해당 글 8건
배열에서 가장 큰 직사각형 구하기 : 관찰을 통해 풀어봅시다.

(2차원) 배열에서 가장 큰 정사각형을 찾는 것은 dp로 해결할 수 있습니다. 문제를 조금 바꿔보겠습니다. 가장 큰 직사각형은 어떻게 구해야 할까요? 문제의 제한이 딱 하나 바뀌었을 뿐인데, 난이도는 4단계 정도 높아졌습니다. 이 문제를 보도록 하겠습니다. 문제를 요약하면 다음과 같습니다. n이 범위는 1이상 2000 이하입니다. 시간 제한이 3초인 것을 감안했을 때, O(n^2)나 O(n^2logn) 정도에 풀어야 한다는 결론을 얻을 수 있습니다. 그런데, 후자는 생각보다 상수 줄이기가 빡빡하기도 하고 제가 시도해 본 방법이 아니므로, 저는 전자로 시도해 보겠습니다. 먼저 간단한 상식 아닌 상식을 통해서 관찰을 하나 해 보도록 하겠습니다. 길이가 3, 4, 2, 6인 높이 1짜리 직사각형이 있습니다. ..
자료알고/알고리즘 2020. 10. 18. 17:40
배열 원소 삽입 삭제 패턴만 익혀봅시다.

사실, 이런 류의 기능을 하는 함수는 구현을 해야 할 일이 있을 겁니다. 여기에서는 optimize 생각 안 하고, 어떻게 빠르게 구현을 할 지, 패턴 정도만 이야기 해 보도록 하겠습니다. 3 종류의 쿼리가, Q개 들어온다고 생각해 보겠습니다. 이 때, insert 하는 위치와, delete 하는 위치 모두는 vaild 하다고 생각해 봅시다. 먼저, 구조체를 하나 정의하기 전에, 어떤 구조가 적합한지 먼저 생각해 봅시다. 사실, 적절한 자료구조가 있습니다. i번째 위치를 빠르게 찾는다. [s, e]번째 위치에 있는 원소 item들을 모두 delete 하는 것 또한, s번째 item을 찾고, e번째 item을 찾기만 하면 됩니다. 그러면 kth를 빠르게 찾을 수 있는 구조면 좋은데요. 그 중 하나는, sk..
구현 2020. 2. 16. 02:04
상수 포인터 == 배열? 잠깐 짚고 넘어갑시다.

배열이랑 포인터의 관계를 들어가기 전에, 하나만 짚고 넘어가겠습니다. 배열과 포인터는 같은 개념일까요? 결론부터 말하면 아닙니다. 따라서, 배열 이름을 상수 포인터라고 한 것은, 올바른 표현이 아닙니다. 후자는 아래와 같이 선언된 것을 의미합니다. address 값을 저장하기 위한 별도의 변수가 5번째 줄에 선언이 되어 있습니다. 예제 1을 봅시다. 5개의 원소를 저장하고 있는 배열 arr을 선언했습니다. 그리고 어떠한 공간을 가리키는 int형 포인터 변수인 p를 선언했어요. 그리고 p가 가리키고 있는 데이터를 출력하는 간단한 프로그램입니다. 4번째 줄을 보시면, arr을 선언했습니다. 그러면 메모리 상에 다음과 같이 할당될 겁니다. 그런데, 배열이던, int형이던, double형이던, 메모리의 어디에 ..
코딩/C 2019. 11. 1. 00:34
c언어 2차원 배열 : 메모리 상에 어떻게 저장이 될까요?

C언어에서 2차원 배열은, 어떻게 메모리 상에 저장이 될까요? 오늘은 이 부분만 집중적으로 보도록 하겠습니다. 먼저, int형 배열인, arr[3][4]를 선언하였습니다. 그러면 메모리 상에 어떻게 생성이 될까요? 일단 행렬로 치면, 3행 4열이라고 볼 수는 있는데요. & 연산자를 쓰면, 현재 주솟값을 볼 수 있는데요. 예제 프로그램을 보면서 이해를 해 보도록 합시다. 먼저, 예제 1을 봅시다. 3행 4열의 배열을 선언하였습니다. 그리고 2중 for loop를 돌면서, 저는 i와 j와 arr[i][j]의 주솟값을 출력하고 있습니다. 그러면 어떻게 결과가 나올까요? 위와 같이 나오는데요. arr[0][0], arr[0][1], arr[0][2], arr[0][3], arr[1][0], ... 순으로 주솟값..
코딩/C 2019. 9. 14. 00:22
c언어 배열 : 기본형인 1차원 array 부터 알아봅시다.

보통 제어문을 배우시고, 함수로 넘어가는 경우가 많아요. 저는 C언어 배열 먼저 다루도록 하겠습니다. 함수는 조금 뒤에 배워도 크게 문제는 없습니다. 먼저 array는 같은 자료형을 여러 개 묶어놓은 자료 구조 정도로 생각하면 좋아요. 그런데, 그걸 어떻게 묶느냐가 문제입니다. 이 친구는 시작 위치를 기준으로 연속이 되게 저장이 되어 있어요. 흔히 이런 말을 들어보신 적이 있을 겁니다. array는 삽입, 삭제는 매우 오래 걸리지만, x번째에 있는 원소는 굉장히 빠르게 찾을 수 있다. 그 이유는 간단합니다. 메모리 상에 연속적으로 저장이 되기 때문입니다. 즉, 실제로 arr[2]에 접근하기 위해서, arr의 기준 위치를 알아냅니다. 그림에서는 0x80번지입니다. 그 다음에, 첨자가 2가 붙었기 때문에, ..
코딩/C 2019. 9. 6. 23:41