본문 바로가기

분류 전체보기

1.2 Maximum Range Sum (2) 앞에서 사용한 알고리즘의 Time Complexity는 $O(n^3)$이었다. 이것을 줄이기 위해서는 불필요한 연산을 줄이는 것이 가장 먼저 할 수 있는 방법이다. 일단 앞의 알고리즘을 이용해서 작성한 소스코드를 다시 살펴보도록 하자. int getMaximumRange1(int *arr, int size){ int max = INT_MIN; for(int i=0; i
1.1 Maximum Range Sum (1) Maximum Range Sum이란 길이가 n인 배열을 받아서 구간을 잡아 그 구간에 있는 모든 배열 값을 더해서 그 값이 최대가 되도록 하는 값을 찾도록 하는 문제이다. 그냥 바로 생각하면 배열의 모든 값을 더하면 최댓값이 될 수 있다고 생각할 수도 있지만, 이렇게 하려면 배열의 모든 값이 양수라는 조건이 있어야 한다. 즉, 임의의 숫자에 대해서는 이렇게 생각할 수 없다는 것이다. 그러면 이 문제를 어떻게 하면 해결 할 수 있을까? 가장 간단한 방법은 모든 구간에 대해서 Range Sum을 계산해서 그 값을 계속 비교해나가면서 최대인 것을 선택해서 그 값을 반환해주면 된다. 이제 이것을 C++ 코드로 작성하면 아래와 같다. int getMaximumRange1(int *arr, int size){ in..
Github 소스코드 볼 때 탭 사이즈 조절 코드를 작성할 때 보통은 tab(\t)키로 인덴트를 하기 보다는 spacebar(' ')로 인덴트를 하는 경우가 많은 것 같다. 특히 JetBrains사의 IDE 환경은 기본 인덴트가 spacebar로 되어 있다. 하지만 나의 경우에는 spacebar로 되어 있으면 전부 tab키로 바꾸는 것이 익숙해졌기 때문에 IDE를 tab키로 인덴트를 할 수 있도록 변경하였다. 이렇게 indent를 구분하는 언어인 Python의 경우에는 4칸의 spacebar와 같은 크기로 공간이 되어 있어도 indentation level이 심하지 않기 때문에 크게 상관은 없지만 html과 같은 indentation level이 심한 언어에서는 4칸의 spacebar로 하게 되면 매우 코드가 읽기 어려워진다. 보통 html과 같은..
실습 2주차 [2] Binary Search 문제10^6개 만큼의 서로 다른 unsigned integer가 정렬된 형태로 input에 들어오고, 다음으로는 10^4개 만큼의 서로 다른 unsigned integer가 들어온다.이 때 처음의 10^6개의 데이터는 배열에 들어가며, 그 다음 input인 10^4개의 데이터에 대해서 binary search를 이용해서 해당하는 인덱스를 반환해서 각각 출력하게 한다.만약 해당하는 값이 없는 경우에는 -1을 반환한다. 입력 형식숫자1 숫자2 ... 숫자1000000숫자1 숫자2 ... 숫자10000 출력 형식 : 인덱스 값을 한 줄에 하나씩 찍도록 한다. 즉 찾는 값이 총 10^4개이므로 출력은 10^4줄에 걸쳐서 나와야 한다. 답안 #include using namespace std; #define SI..
약간 늦은 에너지 해커톤 후기 에너지 해커톤이 끝나고 일주일이 지났다. 에너지 해커톤은 '인코어드'라는 스타트업 업체가 주관하는 해커톤 행사로 내가 처음으로 나가 본 해커톤 대회였다. 그냥 단순하게 다른 사람들과 함께 코딩을 해보면 어떨까라는 생각으로 참가한 것이 컸던 것 같다. 즉, 에너지 해커톤이라는 내용에서 "에너지"라는 측면보단 "해커톤"이라는 측면을 보고 지원을 하였다. 일부 해커톤의 경우에는 참가비를 내고 참여하는 것이 있다고 하는데, 이 해커톤의 경우에는 후원하는 업체가 많아서 그런 것인진 몰라도 식사와 간식을 무료로 제공하면서 참가비는 따로 받지 않았다. 그리고 서버의 경우에는 아마존에서 무상으로 지원을 해주어서 그 서버를 이용할 수 있었다. 역시 아마존 ㄷㄷㄷ... 그리고 예선과 본선으로 나누어져서 심사가 이루어지는데..
실습 2주차 [1] Greatest Common Divisor 문제 최대 공약수(Greatest Common Divisor)를 Recursive code로 구현하여 100개의 쌍에 대해서 최대 공약수를 출력하도록 한다. 입력의 경우 음이 아닌 정수가 입력되며 N과 0의 최대 공약수는 N을 출력하도록 한다. 입력 형식숫자1 숫자2 숫자3 숫자4 ... 숫자199 숫자200 출력 형식 : 입력된 두 쌍의 숫자에 대해서 각각 최대공약수를 구해서 각 줄마다 출력을 하도록 한다. 답안 #include using namespace std; int gcd(int, int); int main(){ int a, b; for (int i = 0; i > a >> b; cout b) ? b : a; if (t_min == 0) return t_max; ..
Emmet 참고자료 Emmet의 경우는 HTML 이나 CSS 소스코드를 매우 빠른 속도로 작성을 가능할 수 있도록 하는 플러그인이다.Atom 에디터의 경우에는 기본적으로 제공하고 있는 것으로 알고 있으며, Sublime Text의 경우에는 패키지를 제공하고 있다. Emmet의 큰 장점은 많이 반복되는 소스코드 부분을 몇 자를 입력하지 않더라도 한 번에 생성이 가능하다는 점이다. 예를 들어서 li 태그에 동일한 class 이름을 가지도록 해서 10개를 생성한다는 경우 li.line*10을 입력하는 것만으로 바로 생성이 가능하다.(물론 복사 붙여 넣기로도 가능하지만 더 오래걸린다...) "."의 경우에는 클래스를 나타내고, "#"의 경우에는 id를 타타내며, "{}"안에 값을 넣으면 태그의 속성을 생성할 수 있다. "*"는 반..
실습 1주차 [2] Insertion Sort 문제Insertion sort를 이용해서 주어진 정수들을 오름차순으로 정렬해서 출력한다. 단, 숫자의 개수가 10,000개를 넘지 않는다. 입력 형식(숫자 개수)숫자1 숫자2 ... 숫자N 출력 형식 : 주어진 N개의 숫자를 공백으로 구분하여 오름차순으로 출력 한다. Ex)입력54 7 3 10 1 출력1 3 4 7 10 답안 #include using namespace std; #define MAX_LEN 10000 void insertion_sort(int arr[], int size); int main(){ int N; cin >> N; int arr[MAX_LEN]; for (int i = 0; i > arr[i]; insertion_sort(arr, N); for (in..

티스토리툴바