728x90

프로그래밍 410

C++] Vector를 이용한 이중 배열

C++] Vector를 이용한 이중 배열 동적 할당에 대해서 익숙해지면배열을 정적으로 할당하는 경우가 줄어들게 되고거의 대부분 동적으로 할당하게 된다.그렇지 않은 사람들도 있겠지만,나는 변수 사이즈에 따라 배열 크기가 바뀌는 경우 반드시 동적할당을 통해서배열의 크기를 결정 짓는다. 그러다가 STL의 vector라는 걸 알게 되면,동적 할당도 잘 사용하지 않게 된다.구조체가 필요하고 안에 들어가는 변수 관리가 까다로운 경우가 아니면,거의 대부분의 경우 vector를 사용하게 된다.물론, vector에 임의의 구조체를 넣지 못하는 건 아니고그건 순전히 사용하는 나의 숙련도 문제에서 기인한 것이라고 생각된다. Topcoder나 비정기적 혹은 정기적으로 개최되는 코딩 대회에 참가하거나,그곳에서 나온 문제들을 풀..

Algorithm] 합병 정렬(Merge Sort)

Algorithm] 합병 정렬(Merge Sort) 합병 정렬은 대표적인 분할정복 방법(Divide and Conquer)을 사용한다.더 이상 부분 문제로 만들 수 없는 수준까지 분할한 뒤,이를 다시 취합하는 과정에서(정복) 정렬이 이루어지는 정렬 알고리즘이다. 일단 백문이불여일견이니 이것이 작동하는 과정을 그림으로 한 번 살펴보자. 파란색은 정렬이 완료되지 않은 부분문제, 즉 분할 대상이고주황색은 정렬이 완료된 부분문제로 정복 및 정복 대상이다.과정을 보면 알 수 있듯, 다시 한 번 말하지만 합병 정렬은 정복 과정에서 정렬이 이루어진다. 의사 코드를 한 번 살펴보자. MergeSort(arr,start,end)입력 : arr[start] ~ arr[end]출력 : 정렬된 arr[start] ~ arr[..

Algorithm] Quick Select(K번째 숫자 탐색)

Algorithm] Quick Select(K번째 숫자 탐색) 정렬되지 않은 숫자들을 입력 받고 K번째로 작은 숫자를 찾는 방법을 떠올리자면,가장 먼저 떠오르는 것이 정렬한 후에 바로 접근하는 것을 생각해볼 수 있다. 통상 퀵 정렬이나 합병 정렬을 통해서 정렬을 수행하면 시간 복잡도가 O(nlogn)이고,이후 탐색에서의 시간 복잡도는 O(1)로 결과적으로 O(nlogn)의 시간 복잡도를 예상해볼 수 있다.이보다 좀 더 효율적인 것을 찾아볼 수는 없을까? 정렬 중에서 가장 빠른 성능을 보이는, 퀵정렬을 한 번 살펴볼 필요가 있다.퀵정렬은 피봇(pivot)을 선정하여 피봇을 기준으로 분할한 정보를 또 다시 피봇으로 나누는분할 정복 과정을 통해서 정렬을 이루는 방법이다. 여기서 이 피봇에 주목할 필요가 있다...

Algorithm] Closest Pair(최근접 점의 쌍 찾기)

Algorithm] Closest Pair(최근접 점의 쌍 찾기) Closest Pair(말 그대로 최근접 점의 쌍 찾기)XY 좌표 평면 상에 존재하는 점들 중, 가장 근접한 쌍을 골라내는 알고리즘이다.가장 간단한 건, 한 점과 연결되는 모든 점들과의 거리를 계산하고이를 바탕으로 최근접 거리를 탐색하는 것이다. 이 경우 N개의 점이 있다고 했을 때 N(N-1)/2의 비교,Big O로는 N^2에 해당하는 시간복잡도가 소요된다.점의 수가 100개 내외여도 꽤나 느려지는 것이 어마어마한 단점이다. 이 때 우리가 생각해볼 수 있는 것이 분할정복 방식(Divide and Conquer)인데,부분 문제를 만들어서 계산과 비교 회수를 비약적으로 줄일 수 있다.x축을 기준으로 정렬을 수행하고(이 때 정렬은 퀵정렬로 가..

Arduino] LiquidCrystal.h

Arduino] LiquidCrystal.h 아두이노 강의를 들으면서 LCD 출력을 하면서 정리했던 LiquidCrystal 헤더 파일에 대한 내용이다. 주로 사용하는 부분들에 대해서 정리가 되어 있다.디테일한 예시는 차후 올라가는 포스트(사실은 보고서로 제출했던 것들)을 통해 소개할 예정이다. LiquidCrystal.h LCD 모듈을 사용할 수 있는 라이브러리(Library)로 아두이노에서는 여러 가지 함수를 지원하며,아두이노 설치와 동시에 포함되는 라이브러리. - LiquidCrystal()여러 가지 형태의 LCD의 제어 타입을 설정하고, 제어 핀과 데이터 핀을 설정함.K-아두이노 브레드보드에선 4 data 라인과, RS, EN 제어 라인만 사용, RW 제어 라인은 접지시킴.제어와 data 라인은 ..

Arduino] PWM 출력으로 LED 스트립 써먹기

Arduino] PWM 출력으로 LED 스트립 써먹기 원래부터 아두이노, 임베디드 시스템에 관심이 많았던 찰나에,학교에서 기존에 하던 AVL 보드 설계를 아두이노로 대체하면서 이런저런 소자를 써보게 됐다.그전에 이미 스타터 키트라고 시중에 나와 있는 패키지를 사서 이런저런 시도를 해보긴 했지만,없는 소자들도 있어서 다방면으로 써볼 기회가 없었는데 기회를 얻었다.(물론, 3색 LED 스트립이 무슨 대단한 설정이 필요하거나 비용이 드는 건 아니었지만...)반강제적으로(?) 활용하게 되면서 경험을 쌓았다고 생각하자.아무튼 나는 돈 쓰지 않고, 소자도 얻고 경험도 쌓은 것이니까.. 영상에 사용된 소스 코드는 아래 '소스코드 보기'를 클릭하면 나온다. 1234567891011121314151617181920212..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 3

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 3 C언어로 쉽게 풀어쓴 자료구조8장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 18. 앞에서 공부한 리스트 추상 자료형을 사용하여 우선순위 큐 추상 자료형을 구현하여보라.리스트 추상 자료형의 각종 연산들을 사용하라.삽입 연산은 O(1)의 시간 안에, 삭제 연산은 O(n)만큼의 시간이 걸리게끔 구현하라.여기서 n은 큐 안에 있는 요소들의 개수이다. 12345678910111213141516171819202122232425262728293031#ifndef __S_L..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 2

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 2 C언어로 쉽게 풀어쓴 자료구조8장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 17. 연결 리스트(linked list)를 이용하여 우선순위 큐 추상 자료형의 각종 연산들을 구현하여보라. 1234567891011121314151617181920212223242526#ifndef __LIST_PQ_H__#define __LIST_PQ_H__#define ELEMENT_MAX 200 typedef int element;typedef struct ListNode { e..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 1

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 1 C언어로 쉽게 풀어쓴 자료구조8장 Exercise 문제다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 16. 정렬되지 않은 배열(array)를 이용하여 우선순위 큐 추상 자료형의 각종 연산들을 구현하여 보라. 1234567891011121314151617181920212223#ifndef __ARRAY_PQ_H__#define __ARRAY_PQ_H__ #define ELEMENT_MAX 200 typedef int element;typedef struct { element Queue[..

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 3

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 3 C언어로 쉽게 풀어쓴 자료구조4장 Exercise 문제들이다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 29번. 이중 연결 리스트를 이용하여 숫자들을 항상 정렬된 상태로 유지하는 리스트 SortedList를 구현하여보라.앞의 문제의 연산들을 구현하면 된다. 123456789101112131415161718192021222324252627282930#ifndef __SORTED_LIST_H__#define __SORTED_LIST_H__#define TRUE 1#define FALSE ..

728x90