방배동 고구마

malloc, calloc은 메모리 동적할당에 쓰인다. 아래를 보자. int N=4; int arr[N]; //int arr[4]; 위의 코드는 실행 가능할까? C언어 컴파일러의 버전에 따라 실행 가능 할 수도 있고 가능하지 않을 수도 있다. VLA를 지원하는지 하지 않는지에 따라 다르다. C99버전에서는 VLA를 지원하나 구버전에서는 기대할 수 없다. 구버전을 예로 든다면 아쉽게도 에러가 난다. 배열은 변수로서 선언할 수 없기 때문이다. 왜 안되는 걸까? 메모리 구조를 먼저 알아야한다. N이 지역변수임을 가정하면 N에 대한 메모리크기는 컴파일타임에 정해진다. 4byte일 것이다. 그러나 N의 값이 4라고 인식되는 것은 컴파일타임이 아닌 런타임이다. 따라서 프로그램이 수행되어야 한다는 뜻이다. 마찬가지로..

스택문제는 참으로 까다롭다. 경험으로 봤을때는 코드로 만들고나서 반드시 Test case를 손으로 똑같이 해봐야 하는 거 같다. 그래야 문제점을 발견할 수 있다. 또한 스택처리 반복안에서 분기를 치거나 첫노드를 먼저 Push하거나 하는 것은 좋지 못하다. 스택처리 반복이 복잡해질 수록 추적하기 어렵기 때문이다. 간단한 스택처리 Test case로 한줄한줄 한손한손 따라가면서 디버깅해보자. 문제 높이가 다른 N개의 전봇대가 주어진다. 서로다른 전봇대끼리 전깃줄을 잇는다. 1. 이웃한 두개의 전봇대는 전깃줄을 잇는 것이 무조건 가능하다. 2. 이웃하지 않은 두개의 전봇대 사이에 양측의 두 전봇대보다 높이가 높거나 같다면 전깃줄을 이을 수 없다. 위의 그림의 경우 5가지의 경우가 있다. 1번과 3번 전봇대는 ..

문제 꼬리잡기 게임을 한다. 일직선 상에서 진행하며 모두 동시에 출발하지만 출발 위치와 속도는 다르다. T분동안 게임이 진행되며 일직선 상이기 때문에 추월할 수 없고 속도가 빠른 뒷사람의 앞사람의 꼬리를 잡으면 하나의 그룹으로 인식된다. 주어진 조건에서 몇개의 그룹이 형성되는지 구하라 입력 참가자 수 N : 1~100,000 게임시간 T : 1~1,000,000,000 각 참가자출발 위치 P : 0 ~ 1,000,000,000 각 참가자 속도 S : 0 ~ 1,000,000,000 ※ 출발위치는 오름차순으로 입력됨 5 3 0 1 1 2 2 3 3 2 6 1 출력 3 접근방식 아주 간단하게 생각해보자. 1. 각 참가자의 계산된 T분 후 위치를 구한다.2. 뒷 사람이 앞사람보다 위치가 클 경우, 앞사람의 위..

문제 1. N개의 건물 높이가 주어진다. (최대 80000) 2. 건물옥상에서 좌에서 우측 방향으로만 바라볼 수 있다. 3. 높이가 같거나 높으면 옥상을 볼 수 없다. 4. 이때 옥상을 볼 수있는 최대의 합을 구하라 접근 N의 갯수가 최대 8만이기 때문에 i번째 건물'이' 볼 수 있는 옥상을 이중 루프로 비교 탐색을 수행할시 시간복잡도는 O(N제곱)이다. 때문에 시간이 초과될 수 있다. i번째 건물'을' 볼 수 있는 건물을 탐색해야한다. 시간 복잡도 O(N). 1. i번째 건물을 볼 수 있는 건물을 스택에 저장한다. 2. i+1번째 건물을 볼 수 있으면 pop하지 않는다. 3. i+1번째 건물을 볼 수 없다면 pop한다. 스택에 있는 전체 건물 후보에 대해 2,3을 판단한다. 4. 스택에 남아있는 건물 ..