전체 글 썸네일형 리스트형 4195번 4195번 - 친구 네트워크 이 문제는 union-find 를 이용해서 문제를 풀었다. 추가적으로 STL 의 map 을 이용했다. 다른 분들 코드를 보니 각 노드에 번호를 다시 매겨서 그 번호를 이용해서 문제를 푸신다. 나는 map 에서 string 을 배열의 인덱스로 사용할 수 있으니 , 그냥 string 을 사용해서 문제를 풀었다. (그런데 이게 다른 문제에서는 메모리 오류나, 시간 오류가 발생하는 지는 모르겠다 아래 질문들 갓들은 대단하다 정말..... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374.. 더보기 1976번 1976번 - 여행 가자 이 문제를 나는 처음에 연결요소의 갯수를 이용해서 문제를 풀었다. 도시들이 연결되어 있기만 한다면, 어떤 경로를 지나던 갈 수 있기 때문이다. 그리고 지금은 disjoint-set 을 배우고 있기 때문에 그 방식을 이용해서 풀어보았다. 하나의 트리 안에 있기 위해서는 각 도시들의 find 값, 즉 루트 노드가 같아야 한다는 점을 이용했다. 주의할 점 --> 나는 처음에 부모노드를 자기 자신으로 초기화 하는 것을 빼먹어서 처음에 문제를 틀림. 고칠 것 --> 처음에 나는 2중 for문에서 예를 들어 1은 0을 부모로, 0은 1을 부모로 해서 , 사이클이 생겨서 부모노드를 못찾는것이 아닌가 혼자 고민했는데, merge 함수에서 이미 부모가 같을 때, 다를 때를 처리해주기 때문에 문제.. 더보기 cin,cout 과 printf,scanf 시간차이 http://gooddaytocode.blogspot.kr/2016/07/cin-scanf.html https://algospot.com/forum/read/2496/ cin,cout 과 scanf,printf 시간차이에 관한 글 더보기 1717번 1717번 - 집합의 표현 union- find 를 통해서 문제를 해결했다. union을 할 때는 경로의 압축을 해주는 것이 시간초과를 해결하는데 주요했다. 그리고 이 문제의 경우, 입력,출력이 많기 떄문에 cin, cout 대신 printf,scanf 를 써줘야 했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include#include using namespace std;int n, m;vector p; int find(int x){ if (x == p[x]) { return x; } return p[x] =.. 더보기 3015번 3015번 - 오아시스 재결합 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-3015 https://blog.naver.com/malmstee/220990386293 ↑↑↑ 문제를 푸는데 참고한 설명들... 이 문제 푸는데 정말 오랜시간이 걸렸다... 우선 핵심은 뒤에서 앞을 본다는 방식으로 생각해야 한다는 점이었다. 그리고 이 문제에서 가장 핵심은 stack에 같은 키를 가진 사람이 연속으로 서있을 때이다. 나는 이를 map 을 이용해서 구현하였다.. 같은 키를 가진 사람이 연속으로 몇명이 세워져있는지를 cnt[ 키 ] = 몇명 으로 계산하였고, 중간에 더 큰놈이 서 있는 경우는 다시 초기화해주었다.. 나중에 시간이 지나서 다시 풀어도 그때 또 .. 더보기 6549번 6549번 - 히스토그램에서 가장 큰 직사각형 이 문제는 종만북에서 분할정복, 스택을 이용한 문제풀이가 나와있는데, 나는 스택을 이용해서 문제를 풀어보았다. 접근법을 보고 이해하면서 문제를 풀었다. 어떻게 이런방법을 생각해서 푸는지, 아직 나는 저런 생각을 못하겠다. 다음에는 분할정복 방법으로 풀어봐야겠다.. 일단 이 문제는 x라는 높이의 직사각형에서 왼쪽으로 최대, 오른쪽으로 최대를 구해서 직사각형의 최대값을 구하는 방법이다. 어떤 사각형에서 자신보다 높이가 낮으면, 왼쪽,오른쪽으로 확장해갈 수 없다는 점을 이용했다. 따라서 그때, 직사각형의 최대값을 구하고면서 계속해서 스택에 최대값이 계산되지 않은 직사각형을 쌓게 된다. 따라서 스택에는 점점 커지는 직사각형이 쌓이게 된다, 마치 오름차순으로 쌓이듯 .. 더보기 1182번 1182번 - 부분 집합의 합 1. 재귀함수를 이용해서 풀이 2. 비트마스크를 이용해서 풀이 for문에서는 0인 공집합을 빼고 모든 부분집합을 도는 조건문이다. 아래의 for문을 for (int subset = set; subset; subset = set & (subset - 1)) 아래처럼 바꿔도 동일하다. for(int subset=1;subset> S; for (int i = 0; i > D[i]; } dfs(0, 0); if (S == 0) { ans -= 1; } cout S; v.resize(N); for (int i = 0; i > v[i]; } int set = (1 더보기 10974번 10974번 - 모든 순열 모든 순열을 구하는 문제인데, 사전식으로 출력하라고 했으니, next_permutation 을 쓰면 된다. ( 10972번) 단 시간 초과 문제로 cin,cout 대신 printf 를 사용해야한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#includeusing namespace std; bool next(vector &v){ int inc = -1; int dec = -1; for (int i = 0; i 더보기 이전 1 ··· 44 45 46 47 48 49 50 ··· 61 다음
