본문 바로가기

분류 전체보기

 (209)
[ 백준 / C++ ] 2776 : 암기왕 [ 문제 ] 2776번: 암기왕 [ 접근방법 ] c++을 사용한다면 헤더에 내장된 binary_search() 함수를 통해 쉽게 이분 탐색을 구현할 수 있다. 존재 여부 뿐만 아니라 개수는 upper_bound() - lower_bound() 를 통해 구할 수 있다. [ 소스코드 ] #include #include #include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ int n, m, cnt; cin >> n; vector vec(n); for(int i = 0; i > vec[i]; ..
[ 백준 / C++ ] 11501 : 주식 [ 문제 ] 11501번: 주식 [ 접근방법 ] 입력을 내림차순 정렬한 후 순회하면서, 현재 처리중인 인덱스보다 순회중인 인덱스가 큰 경우 차이를 계산한다. 이 과정에서 구간합을 빠르게 구하기 위해 sum 배열을 미리 만들었다. 시간복잡도는 t * O(n log n) 이다. [ 소스코드 ] #include #include #include using namespace std;typedef long long ll;bool cmp(pair x, pair y){ if(x.first != y.first)return x.first > y.first; return x.second > y.second;}int main(){ ios::sync_with_stdio(0); cin.tie(0); i..
[ 백준 / C++ ] 4659 : 비밀번호 발음하기 [ 문제 ] 4659번: 비밀번호 발음하기 [ 접근방법 ] 품질 조건별로 함수를 구현하였다. [ 소스코드 ] #include using namespace std;bool isVowel(char ch){ return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';}bool chk1(const string& str){ for(auto ch : str){ if(isVowel(ch)){ return true; } } return false;}bool chk2(const string& str){ if(str.length() > str; if(str == "end")b..
[ 백준 / C++ ] 2961 : 도영이가 만든 맛있는 음식 [ 문제 ] 2961번: 도영이가 만든 맛있는 음식 [ 접근방법 ] n이 최대 10 이므로 백트래킹으로도 충분히 가능하다. 재료 사용 여부를 비트마스크를 통해 처리했다. [ 소스코드 ] #include #include #include #include using namespace std;int n;vector> taste;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; taste.resize(n); for(int i = 0; i > taste[i].first >> taste[i].second; } int ans = 1e9; for(int i = 1; i
[ 백준 / C++ ] 1495 : 기타리스트 [ 문제 ] 1495번: 기타리스트 [ 접근방법 ] 직전 상황에 가능한 볼륨값에서 현재 볼륨 차이를 적용하여 가능한 볼륨값을 주기적으로 갱신한다. 시간복잡도는 O(N*M)으로 충분하다. [ 소스코드 ] #include #include #include using namespace std;int n, s, m;vector vol;vector cur, nxt;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> s >> m; vol.resize(n + 1); cur.resize(m + 1, false); nxt.resize(m + 1, false); for(int i = 1; i > vol[i]; cur[s] =..
[ 백준 / C++ ] 2304 : 창고 다각형 [ 문제 ] 2304번: 창고 다각형 [ 접근방법 ] 스택을 활용하여 값을 갱신한다. 일단 입력값을 위치순으로 정렬한 후, 문제 5번 조건을 위해 스택에 저장된 값과 입력값을 비교해준다. "스택에 저장된 값  [ 소스코드 ] #include #include #include #include using namespace std;int n, ans;vector> vec;stack> st;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; vec.resize(n); for (int i = 0; i > vec[i].first >> vec[i].second; } sort(vec.begin(), vec.end()); st..
[ 백준 / C++ ] 5397 : 키로거 [ 문제 ] 5397번: 키로거 [ 접근방법 ] O(1) 만에 중간 삽입/삭제 가능한 list 를 사용했다. list 사용시 주의해야 할 점은erase() 함수를 사용하고 나서 iterator 가 가리키고 있던 노드가 삭제되었기에 반환값을 받아야 한다. list 는 vector 와는 달리 노드의 메모리가 불연속적이기 때문에 이러한 문제가 발생한다. [ 소스코드 ] #include #include using namespace std;int n;string str;list li;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; while (n--) { cin >> str; li.clear(); ..
[ 백준 / C++ ] 1890 : 점프 [ 문제 ] 1890번: 점프 [ 접근방법 ] DP를 통해 O( n² ) 만에 문제를 해결할 수 있다. [ 소스코드 ] #include using namespace std;int n, board[105][105];long long dp[105][105];int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i > board[i][j]; dp[0][0] = 1; for(int i = 0; i

티스토리툴바