본문 바로가기

분류 전체보기

 (211)
[ 백준 / C++ ] 2631 : 줄세우기 [ 문제 ] 2631번: 줄세우기 [ 접근방법 ] 전체에서 순서를 바꾸지 않아도 되는 번호를 빼주는 방식으로 풀었다. 즉, 최장 증가 부분 수열( LIS )의 길이를 구하고 n에서 빼주면 된다. dp[ i ] = i + 1번째 수를 끝으로 하는 LIS의 길이. 위와 같이 dp를 설정하고 2중 for문을 돌면서 값을 갱신한다. [ 소스코드 ] #include #include using namespace std;int n, maxLength;vector vec, dp;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; vec.resize(n); for(int i = 0; i > vec[i]; dp.assign(n, 1); ..
[ 백준 / C++ ] 10973 : 이전 순열 [ 문제 ] 10973번: 이전 순열 [ 접근방법 ] 먼저 순열 뒤에서부터 앞으로 탐색하면서 처음으로 연속한 수가 감소하는 인덱스를 찾는다.= vec[ idx ] > vec[ idx + 1 ] vec[ idx ] 뒤에서 이보다 작으면서 제일 큰 수를 찾는다.= vec[ idx ] > vec[ midx ], idx  마지막으로 vec[ idx ] 와 vec[ midx ] 를 교환한 후, vec[ idx ] 뒤를 내림차순 정렬한다.1 3 2 4 5 → 1 2 3 4 5  → 1 2 5 4 3 [ 소스코드 ] #include #include #include using namespace std;int n;vector vec;bool cmp(int x, int y){ return x > y;}int main..
[ 백준 / C++ ] 15903 : 카드 합체 놀이 [ 문제 ] 15903번: 카드 합체 놀이 [ 접근방법 ] 우선순위 큐를 활용하여 매번 제일 작은 두 카드를 고르고 합친다. [ 소스코드 ] #include #include #include using namespace std;typedef long long ll;int n, m;priority_queue, greater> pq;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > cnt; pq.push(cnt); } while(m--){ ll a = pq.top(); pq.pop(); ll b = pq.top(); p..
[ 백준 / C++ ] 13335 : 트럭 [ 문제 ] 13335번: 트럭 [ 접근방법 ] queue의 선입선출 특성을 활용하여 시뮬레이션한다. 다리의 길이 및 최대하중을 고려하였을 때 새로운 트럭이 다리에 들어오지 못한다면,임의로 0을 넣어 트럭 이동을 표현한다. [ 소스코드 ] #include #include using namespace std;int n, w, l;queue leftQ, bridge, rightQ;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> w >> l; for(int i = 0; i > weight; rightQ.push(weight); } for(int i = 0; i
[ 백준 / C++ ] 10804 : 카드 역배치 [ 문제 ] 10804번: 카드 역배치 [ 접근방법 ] 에 속한 reverse 함수를 활용하여 카드 역배치를 구현할 수 있다. [ 소스코드 ] #include #include #include using namespace std;int a, b;vector vec;int main(){ ios::sync_with_stdio(0); cin.tie(0); for(int i = 0; i > a >> b; reverse(vec.begin() + a, vec.begin() + b + 1); } for(int i = 1; i
[ 백준 / C++ ] 4470 : 줄번호 [ 문제 ] 4470번: 줄번호 [ 접근방법 ] 공백을 포함하여 한 줄 입력을 받는 방법 중 하나는 에 속한 getline 함수를 사용하는 것이다.개행문자를 받을 때까지 입력을 받는 방식이다. 주의할 점이 하나 있는데,cin은 개행 문자를 버퍼에 그대로 남겨두기에, cin 이후에 getline을 사용하면 문제가 발생한다. 따라서, cin >> n 후에 cin.ignore() 을 실행하여 입력버퍼를 지워줘야 한다.  [ 소스코드 ] #include #include using namespace std;int n;string str;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; cin.ignore(); for(int i = ..
[ 백준 / C++ ] 17413 : 단어 뒤집기 2 [ 문제 ] 17413번: 단어 뒤집기 2 (acmicpc.net) [ 접근방법 ] 태그는 그대로 출력하고, 아닌 경우에는 스택을 활용하여 뒤집는다. [ 소스코드 ] #include #include #include using namespace std;string str;bool isSpecial;stack st;void swapWord(){ while (!st.empty()) { cout ') { isSpecial = false; cout
[ 백준 / C++ ] 2075 : N번째 큰 수 [ 문제 ] 2075번: N번째 큰 수 (acmicpc.net) [ 접근방법 ] 일단 우선순위 큐에 n번째 행의 값들을 넣는다. 그 후 큐에서 최대값을 추출하고, 추출한 값의 한칸 위에 있는 값을 큐에 넣는 과정을 반복한다. 각 과정은 log N 의 시간복잡도를 가지므로 총 O(N log N)의 시간복잡도를 가진다. [ 소스코드 ] #include #include #include using namespace std;int n, arr[1505][1505], idx[1505];pair ans;priority_queue> pq;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i > arr[i][j]; ..

티스토리툴바