#문제정보 출처 : https://www.acmicpc.net/problem/2776 난이도 : 실버3 사용된 알고리즘 : 이진탐색 알고리즘 #문제분석 단순 중첩 for로 돌리면 시간초과(TLE)가 나기에, 이진탐색 알고리즘(binary search)을 이용해 풀이했습니다. C++ STL의 라이브러리는 binary search 알고리즘을 지원하지만, 연습용으로 직접 이진탐색을 구현했습니다. int binSearch(int arr[], int len, int key) { int l = 0; int r = len - 1; int m; while (l
#1 선형 탐색 알고리즘이란? #2 구현 with C/C++ #1 선형 탐색 알고리즘이란? 선형 탐색 알고리즘 [Linear Search Algorithm]이란, 단방향으로 탐색을 시작하여 원하는 데이터를 찾아내는 매우 단순한 형태의 알고리즘입니다. 구현이 아주 쉽다는 장점이 있지만 모든 데이터를 탐색해야 하기에 최악의 경우 O(N)의 시간 복잡도를 가지며 데이터가 많아질수록 효율이 떨어진다는 단점이 있습니다. * 배열 {1, 2, 3, 4, 5} 에서 3의 위치를 선형탐색을 이용해 찾아보도록 하겠습니다. [1번째 탐색] 0번째 원소와 3(찾고자 하는 수)를 비교합니다. 일치하지 않기에 넘어갑니다. [2번째 탐색] 1번째 원소와 3(찾고자 하는 수)를 비교합니다. 일치하지 않기에 넘어갑니다. [3번째 탐..
#문제정보 출처 : www.acmicpc.net/problem/11000 난이도 : 골드5 분류 : 그리디(GREEDY) 알고리즘 #문제분석 저는 11000 문제 풀이를 위해서 C++ STL의 우선순위 큐(priority_queue) 자료구조를 사용했습니다. 문제에서 주어진 예제(1,3)(2,4)(3,5)를 통해서 설명하도록 하겠습니다. 우선, 시작시간을 기준으로 오름차 정렬을 수행합니다. 다음으로, 시작시간이 가장 빠른 수업의 끝나는 시간(3)을 우선순위 큐(priority_queue)에 push합니다. (* 참고로 priority_queue는 오름차순으로 설정합니다.) priority_queue 에 다음으로 시작시간이 빠른 수업의 끝나는시간(4)를 push 합니다. 그 후 , 첫 번째 수업의 끝나는 ..
#1 About Deque #2 Deque 사용방법 -2.1 deque 선언 & 초기화 -2.2 deque 값 삽입/삭제 - push_back() pop_back() push_front() pop_front() -2.3 deque 값 중간 삽입/삭제 - insert() erase() -2.4 첫 번째 원소 / 마지막 원소 접근 - front() back() #3 Deque 원소 접근 * 개인적인 공부 내용 기록용으로 작성한 글이기에 잘못된 내용이 있을 수 있으며, 지속적으로 수정해 나갈 예정입니다. #1 About Deque Deque 컨테이너는 시퀀스 컨테이너이자, 배열 기반 컨테이너입니다. 그래서 Vector 컨테이너와 특징이 매우 유사합니다.하나의 메모리 블록에 저장되는 Vector와 달리 Dequ..
#문제정보 출처 : www.acmicpc.net/problem/2847 난이도 : 실버4 분류 : 그리디(GREEDY) 알고리즘 #문제분석 레벨별로 점수를 부여하기 위해서는, 각 레벨의 점수가 오름차 순으로 주어져야 합니다. 단, 점수를 내리는것을 최소한으로 해야 하기 때문에, i-1번째 레벨의 점수가 i번째 레벨의 점수보다 높은 점수를 갖고 있다면, i번째 레벨의 점수 - 1 값을 i-1번째 레벨에 부여하면 됩니다. 따라서 저는 레벨의 점수를 갖고 있는 level 벡터의 마지막 값을 compare 점수에 초기화 한 뒤 반복문을 돌려서 뒤에서부터 차례로 검사했습니다. int compare = level[N-1]; for (int i = N - 2 ; i >= 0 ; i--) { while (level[i..