Doby's Lab

[틀렸던 코드] #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector arr; vector answer; for (int i = 0; i > idx; if (idx == 0) { sort(arr.begin(), arr.end()); if (!arr.empty()) { answer.push_back(arr.back()); arr.pop_back(); } else { answer.push_back(0); } } else { arr.push_back(idx); } } for (in..

우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 배열같은 선형적인 구조로 생각할 수 있다. 하지만, 우선순위 큐는 트리의 관점에서 접근해야 한다. 우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만 이를 사용하지 않는 이유가 있다. 데이터를 삽입하거나 삭제하는 과정에서 배열이나 연결 리스트의 메모리를 밀고 당기는데에서 성능 저하를 일으키기 때문에 일반적으로 힙을 사용하여 구현하기 때문이다. (힙이 트리로 이루어졌기 때문) 그리고, 힙에서 데이터를 삽입하거나 삭제할 때는 시간 복잡도가 O(log N)이다. (+ 힙 정렬이 N개의 데이터를 하나씩 다 빼오기(삭제)..

주석 조건 참고 #include #include #include #include using namespace std; queue q; bool visited[100001] = { 0, }; void bfs(int n, int k) { q.push(make_pair(n, 0)); while (!q.empty()) { int value = q.front().first; int cnt = q.front().second; q.pop(); if (value == k) { cout > k; bfs(n, k); return 0; }

이 문제를 직관적으로 풀었을 때는 시간 초과가 발생한다. 구간이 예를 들어 1~100,000이고, 합을 구하는 횟수가 1~100,000이라면 어마한 양의 시간이 발생하기 때문에 다른 방법을 생각해내야 한다. DP (Dynamic Programming) 개념 DP란 큰 문제를 해결하기 위해 작은 문제들로 나누어 작은 문제들을 해결하여 큰 문제들 해결할 수 있도록 도와주는 알고리즘이다. 예를 들어 피보나치 수가 DP의 대표적인 문제라고 할 수 있다. 피보나치 4를 구한다고 생각해보자. 일반적으로 코드는 이렇게 짤 것이다. #include using namespace std; int fibo(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } ..

이번 문제는 DFS를 활용하여 풀려했었다. 하지만, DFS로 구현할 경우에는 TLE가 발생한다. 게시판에서는 BFS를 활용하여 풀어야 한다고 조언한다. 문제를 풀 때 어떤 포인트에서 DFS 혹은 BFS로 풀어야 하는지 알 수 있을까? 여러 블로그를 읽어보다가 감이 잡힌 듯하다. 최단 경로를 알아보아야 할 때, BFS BFS는 어떤 기준점으로부터 인접한 노드들을 차근차근 접근 해나가지만 DFS는 한 군데 길로 쭉 갔다가 조건을 만족하지 못하면 다시 돌아와 다른 노드들을 접근하기 때문에 시간적인 측면에서 BFS가 이런 부분에서는 효율적이다. 하지만, 경로에 대해 가중치(weight)가 붙을 때는 DFS를 활용해야 한다. 이동 과정에 있어서 여러 제약이 있을 때는 DFS (이 점에서 백트래킹과 유사한 거 같다..

이 문제는 논리를 쉽게 떠올릴 수 있었지만 그 논리를 구현하는 데에 있어서 많은 고민을 했다. 밭을 돌아다니는 게 한 사람이 아닌 두 사람이라 함수를 두 개 선언해야 할지 함수를 두 번 콜 해야 할지 혹은 함수 하나에 두 명을 돌아다니게 하는 방법이 있는지 고민을 하다가 모든 방법이 구현이 다 어렵게 느껴져서 논리를 찾아보았다. 논리를 보고서 그냥 말이 안 나왔다. 잠깐 멍 때렸던 거 같다. '왜 이런 생각을 못 했지'라는 말이 나왔다. 두 명을 돌아다니게 하는 것이 아니라 한 명이 모든 구역을 돌아다니게 하는 방법을 생각하면 되었었다. 문법도 알고리즘의 문제도 아닌 논리의 문제가 가끔 머리를 세게 친다. 점점 어려운 문제들을 풀어보면서 결국엔 다 알고리즘 문제가 아니라 논리의 문제 같다고 느껴진다. 생..

1838번 풀이 글과 이어진다. [이전 포스팅 링크] https://draw-code-boy.tistory.com/38 [알고리즘] 백준 1838번: 버블 정렬 (C++), 더 논리적인 감각을 만들어내야 한다 https://www.acmicpc.net/problem/1838 1838번: 버블 정렬 버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개 draw-code-boy.tistory.com [주소 연산자] 포인터에 바로 들어가기 전에 주소 연산자(&)를 알아보자 주소 연산자는 말 그대로 어떤 한 변수의 주소를 가져와주는 연산자이다. 예를 들어 #include int main() { char a = 'i';..

논리적으로는 쉬운 문제였다. 하지만, 내가 짜 놓은 논리와는 계속 엇나가는 출력이 나와서 1시간 동안 정렬할 때 쓴 compare 함수를 들여다보았지만 문제가 없는 듯했다. (일부는 내가 원하는 대로 정렬하지만 일부는 논리를 엇나갔었다.) #include #include #include using namespace std; bool cmp(vector& a, vector& b) { if (a[1] != b[1]) { return a[1] > b[1]; } else { if ((a[1] == b[1]) && (a[2] != b[2])) { return a[2] < b[2]; } else { if (((a[1] == b[1]) && (a[2] == b[2])) && (a[3] != b[3])) { retur..