14 Jul 2021
보자마자 이렇게 풀면 안되는걸 알았는데, 혹시나 수행 시간을 보니 광탈이다… 0.000xx초도 이렇게 critical함을 깨닫는다… Number of Inversion을 구하는 가장 대표적인 알고리즘 문제 유형같다… 처음 접해보는 것에 의의를 두자…(^_^);;
inversion 문제를 접근할 수 있는 방법은 크게 3가지다!
- for loop iteration - 광탈
- merge sort
- AVL tree
- set with upper bound (아직 이해를 못함)
// TimeLimit Exceed 5.00037초 - 0점
#include <vector>
#include <iostream>
using namespace std;
int Answer;
int main(int argc, char** argv)
{
int T, test_case;
setbuf(stdout, NULL);
cin >> T;
for(test_case = 0; test_case < T; test_case++)
{
Answer = 0;
int N; int num;
scanf("%d", &N);
if (N<2 || N>100000) return 0;
vector<int> numbers;
for (int i=0; i<N; i++) {
scanf("%d", &num);
numbers.push_back(num);
}
for (vector<int>::iterator it=numbers.begin(); it!=numbers.end(); ++it)
for (vector<int>::iterator jt=it; jt!=numbers.end(); ++jt)
if (*it>*jt) Answer++;
/////////////////////////////////////////////////////////////////////////////////////////////
// Print the answer to standard output(screen).
cout << "Case #" << test_case+1 << endl;
cout << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
우선 내가 가장 처음에 냈던 답안…(쓰레기 답안) 으로 올리지만, 나머지 방법도 내일 한번 구현해봐야겠다! 시간이 늦어서 우선 자야겠다 ;ㅅ; 갈길이 정말 정말 멀었음을 제대로 깨닫는다! 머리 꽝 🔨🔨🔨
14 Jul 2021
scpc6 연습문제였던 가까운 곱셈 문제랑 Combination(조합) 관련 백트리킹 문제 풀다가 포기하고 돌아왔다,,,,, 이 문제도 트리인데 구글 없이는 못했을 것 같다… 난 언제 구글 없이 스스로 풀 수 있으려나 😥🙏🏼 아무래도 푸는 양과 강도를 많이 늘려야할 듯 싶다… 틈틈히 찾아보기도 하고…
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int N, x, deleteNode;
vector <int> v[51];
int find(){
int answer = 0;
int temp = 0;
for(int i=0; i<N; i++){
if(v[i].size()==0)
answer=answer+1;
}
queue <int> q;
q.push(deleteNode);
while(!q.empty()){
int tmp = q.front();
if(v[tmp].size()==0){
temp=temp+1;
}
else{
for(int i=0; i<v[tmp].size(); i++)
q.push(v[tmp][i]);
}
q.pop();
}
for(int i=0; i<N; i++){
for(int j=0; j<v[i].size(); j++){
if(v[i][j]== deleteNode && v[i].size()==1)
return answer-temp+1;
}
}
return answer-temp;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d", &x);
if(x!=-1) v[x].push_back(i);
}
scanf("%d", &deleteNode);
int result = find();
printf("%d", result);
return 0;
}
13 Jul 2021
보자마자 이렇게 풀면 안되는걸 알았는데, 혹시나 수행 시간을 보니 광탈이다… 0.000xx초도 이렇게 critical함을 깨닫는다… Number of Inversion을 구하는 가장 대표적인 알고리즘 문제 유형같다… 처음 접해보는 것에 의의를 두자…(^_^);;
inversion 문제를 접근할 수 있는 방법은 크게 3가지다!
- for loop iteration - 광탈
- merge sort
- AVL tree
- set with upper bound (아직 이해를 못함)
// TimeLimit Exceed 5.00037초 - 0점
#include <vector>
#include <iostream>
using namespace std;
int Answer;
int main(int argc, char** argv)
{
int T, test_case;
setbuf(stdout, NULL);
cin >> T;
for(test_case = 0; test_case < T; test_case++)
{
Answer = 0;
int N; int num;
scanf("%d", &N);
if (N<2 || N>100000) return 0;
vector<int> numbers;
for (int i=0; i<N; i++) {
scanf("%d", &num);
numbers.push_back(num);
}
for (vector<int>::iterator it=numbers.begin(); it!=numbers.end(); ++it)
for (vector<int>::iterator jt=it; jt!=numbers.end(); ++jt)
if (*it>*jt) Answer++;
/////////////////////////////////////////////////////////////////////////////////////////////
// Print the answer to standard output(screen).
cout << "Case #" << test_case+1 << endl;
cout << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
우선 내가 가장 처음에 냈던 답안…(쓰레기 답안) 으로 올리지만, 나머지 방법도 내일 한번 구현해봐야겠다! 시간이 늦어서 우선 자야겠다 ;ㅅ; 갈길이 정말 정말 멀었음을 제대로 깨닫는다! 머리 꽝 🔨🔨🔨
12 Jul 2021
카드 관련 간단한 문제인데 다음번엔 리스트를 직접 구현해봐도 좋을 것 같다. 사실 구현이 귀찮아서 구글에 linked list 관련 라이브러리를 찾아봤는데, 역시나 C++ Standard Template으로 #include <list>, std::list를 잘, 아주 편하게! 사용했다. 그래서 아주아주 쉽게 금방 풀 수 있었다.
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
list<int> cards;
int N;
cin >> N;
if (N<0 || N>500000) return 0;
for (int i=0; i<N; i++)
cards.push_back(i+1);
int count = 0;
while (cards.size()!=1) {
if (count%2==0) {
cards.pop_front();
count++;
}
else if(count%2==1) {
int temp = cards.front();
cards.pop_front();
cards.push_back(temp);
count++;
}
}
cout << cards.front() << endl;
}
덕분에 오늘도 일찍 취침 가능…! 오늘 연차였고 내일부터 다시 출근 ㅜㅜ이라… 걱정이 이만저만이 아니다…
08 Jul 2021
간단한 스택 문제로 시간이 없다는 핑계로 전에 풀었던 문제를 리뷰했다…
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int size, erase;
stack<int> st;
string num;
cin >> size >> erase;
cin >> num;
for(int i=0; i<size ; ++i){
while(!st.empty() && num[i]-'0'>st.top() && erase>0){
st.pop();
erase--;
}
st.push(num[i]-'0');
}
while(erase>0){
st.pop();
--erase;
}
stack<int> ans;
while(!st.empty()){
ans.push(st.top());
st.pop();
}
while(!ans.empty()){
cout << ans.top();
ans.pop();
}
cout << "\n";
return 0;
}
미루는 습관 버릇을 고치자… 내일 금요일이니까 조금만 힘내쟈,,,, 주말엔 더 난이도 있는거 풀기로 약속 ㅜㅜ
