아네스의 공부일지

흠.. 맨처음에 봤을 때 그냥 map에 넣고빼고 하는건가..? 해서 C++로는 map으로 풀고 나서 알고리즘 분류가 비트마스킹이길레 python은 비트 배열로만 했다. C++ 풀이 #include using namespace std; map m; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int M; cin >> M; for(int i = 0 ; i> cmd; if( cmd == "all" || cmd =="empty"){ if(cmd == "all"){ for(int i = 1; i> tmp; if(cmd == "add"){ if(m.find(tmp) == m.end()..

돈을 인출하는데 필요한 시간을 오름차순으로 정렬해서 더한다. C++ 풀이 #include using namespace std; vector v; int ary[1001]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; for(int i = 0 ; i> tmp; v.push_back(tmp); } sort(v.begin(), v.end()); ary[0] = 0; for(int i = 1 ; i

11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net C++ 풀이 C++에선 priority_queue로 최대힙을 지원하니 사용하면 된다. #include using namespace std; priority_queue pq; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; for (int i = 0 ; i> tmp; if(tmp ==0) { if(!pq.emp..

아이디어는 간단하다. n이 1~10까지 밖에 안되니 n이 10일때 3^10(59049)정도의 연산을 하기때문에 완전탐색으로 풀이가 가능하다. 그러므로 dfs를 통해 모든 경우의 수를 따져보면서 합이 target n보다 커지면 return해버리고 같아지면 count를 1증가시킨다. C++ 풀이 #include using namespace std; vector v; int N, target; int cnt; void dfs(int sum) { if(sum ==target){ cnt +=1; return; } else if (sum > target) return; //sum을 1,2,3씩 증가시켜본다. dfs(sum+1); dfs(sum+2); dfs(sum+3); } int main(void) { ios::..

문제풀이 아이디어 핵심 BFS를 사용하는 queue에 x,y,count값을 저장한다. N,M이 바뀌어서 주어지니 board입력받을 때 유의하자. C++ 풀이 #include using namespace std; queue q; // x,y, count int board[1001][1001]; bool visited[1001][1001]; int dx[4] = {-1, 0 , 1, 0}; //시계방향 탐색 (상 , 우 , 하 , 좌) int dy[4] = {0,1,0,-1}; int N,M; int res=0; void bfs(){ while(!q.empty()){ int x=q.front().first.first; //row 좌표 int y = q.front().first.second; // col 좌표..

아이디어는 아래 분할 정복 문제 풀었던 것과 동일하다. 다만 색종이를 판단해야하는 방법이 추가됐을 뿐. [백준 1074번] Z ( 분할정복, 재귀) ** 다시풀어보기** 처음 분할정복 / 재귀 문제를 풀어보는데, 애초에 이게 분할정복인지 재귀인지 모르고 풀었다. dfs로 풀 수 있을것 같아서 풀어봤었는데 역시 시간초과. 2시간 가량 생각해서 풀었는데.. 분할정복 i-never-stop-study.tistory.com 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net C++ 풀이 #in..

1에서 시작해서 방문할 수 있는 모든 노드를 찾는 문제. C++ 풀이 #include using namespace std; vector v[101]; bool visited[101]; queue q; int cnt = 0; void bfs() { visited[1] =true; q.push(1); while(!q.empty()) { int a = q.front(); q.pop(); for(int i =0; i> N >> M ; for(int i = 0 ; i > a >> b; v[a].push_back(b); v[b].push_back(a); } bfs(); cout

짱구를 굴렸을 때, 음.. 뭔가 그리디하게 선택해서 풀면 되겠다 라고 생각은 했지만, 그리디 증명은 어떻게 하지 ? C++ 풀이 #include using namespace std; vector v; bool compare(pair& a, pair& b){ if(a.second == b.second) { return a.first > N; for(int i = 0; i>..

C++ 풀이 C++은 기본적으로 priority_queue를 지원하는데, 이게 default로 max_heap이라서 min_heap을 쓰려면 음수로 넣어주고 빼서 쓸 때 다시 마이너스 붙여줘서 사용해야한다. #include using namespace std; priority_queue pq; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; for(int i = 0; i> tmp; if(tmp == 0) { if(pq.empty()) { cout

처음에 map에다 때려 박고 M개를 비교했는데, 400ms가 나왔다. 실버에서 400ms라.. 뭔가 이상해서 C++로 푸신분들 보니 30ms도 안나와서 알고리즘 분류를 보니 이분탐색으로 되어있더라.. 그래서 이분탐색으로도 한번 풀어보고, 파이썬으로 이분탐색 안풀어봤으니 풀어보고자한다. #include using namespace std; vector v; map m; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; for(int i = 0 ; i> s; m[s]; // 다 넣고 } for(int i = 0 ; i< M; i++) { string s; c..