반응형 개발자/Algorithm 썸네일형 리스트형 알고리즘 문제풀이 시간 복잡도 예상하기 및 시간 측정 방법 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억($10^8$)을 넘어가면 시간 제한을 초과할 가능성이 있다. 종만북 위 근사치를 이용하면 간단하게 입력의 크기와 제한시간으로 정답 알고리즘의 복잡도를 대략적으로나마 예측해 볼 수 있습니다. 문제에서 가장 먼저 확인해야하는 내용은 시간제한(수행시간 요구사항)입니다. 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다. 입력이 10,000,000 개의 경우: O(N) 알고리즘 입력이 50,000 개인 경우: O(N * log N) 알고리즘 입력이 10,000 개인 경우: O(N * N) 알고리즘 입력이 400개: O(N * N * N) 알고리즘 거꾸로 이야기하면 입력이 100개 .. 더보기 11724 연결요소의 개수 C++ 문제풀이 위 문제는 BFS 혹은 DFS 로 간단히 풀리는 문제다. 아래 코드는 BFS로 푼 형태이고 코드의 핵심은 BFS이다. BFS는 자료구조 큐를 FIFO로서 이용하는것과, 큐 자료구조를 순회하기 위한 iterator를 자주 써보는것. 지나갔던 Vertex에 대해서 visited 처리하는 것이 무엇보다 중요함! #include #include #include #include #include #include using namespace std; vector ll_edge[1001]; bool visited[1001]; int cnt; void bfs(int start,int N) { queueq; q.push(start); visited[start] = true; while (!q.empty()) { int c.. 더보기 1099 백준 알고리즘 문제 풀이 진행중 문제 풀이 코드는 아래와 같다. 아래 문제는 Dynamic Programming이라고 보면 된다. DP로서 각 문장의 단어들의 Length만큼 잘라서 계속 Compare하면서 정답을 찾아 나가면 된다. // 문제 // 형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다. // 이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다. 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다. //이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. //이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다. //예를 들어, .. 더보기 코테 시 ios_base::sync_with_stdio(false); cin.tie(null); 추가 이유 C++로 알고리즘을 풀 때 실행 속도를 높이기 위해 흔히 아래와 같은 구문을 작성해줍니다. ios_base::sync_with_stdio(false); cin.tie(null); 저 같은 경우 단순히 시간초과가 발생했을 때 남들이 위 코드를 작성하면 AC를 받을 수 있다고 하여 지속적으로 작성하고 있었는데, 어느 날 갑자기 원리가 궁금해져 찾아봤는데 내용이 흥미로워 오랜만에 포스팅을 작성합니다. ios_base::sync_with_stdio(false);의 장점 ios_base::sync_with_stdio 구문은 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생합니다. 따라서, ios_base::s.. 더보기 이전 1 2 3 4 다음
