목록백준 (475)

1일1알

백준 16922번 로마 숫자 만들기 C++

백트래킹을 이용하여 가능한 모든 경우를 구해서 나온 값을 set에 넣는데, 문자의 순서는 상관 없기 때문에 중복을 피하도록 구현했다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; int values[4] = { 1,5,10,50 }; unordered_set s; void BT(int idx, int cnt, int sum) { if (cnt >= n) { s.insert(sum); return; } for (int i = idx; i < 4; i++) ..
알고리즘 2022. 1. 16. 13:02
백준 2210번 숫자판 점프 C++

1. 백트래킹으로 5번 이동하는 경우를 모두 구한다. 2. 모든 칸에 대하여 1에서 구한 이동하는 경우를 적용한다. 3. 2의 과정에서 6자리수를 만들 수 있으면 그 수를 set에 넣는다. 4. set의 size를 출력한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector board(5, vector(5)); vector dirV; set s; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; void Sol..
알고리즘 2022. 1. 16. 12:56
백준 1068번 트리 C++

1. root부터 탐색하면서 삭제할 노드의 부모 노드를 알아낸다. 2. 삭제할 노드를 dfs를 이용하여 제일 밑에있는 자식 노드부터 차례로 삭제한다. 3. 2번이 끝났으면 삭제할 노드의 자식들은 모두 삭제가 된 상태이기 때문에 1번에서 파악한 부모 노드를 이용하여 삭제할 노드를 삭제한다. 4. root부터 탐색하면서 리프 노드의 갯수를 알아낸다. 예외) 삭제할 노드가 root노드라면 부모 노드가 없기때문에 0을 출력하고 프로그램을 종료한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lon..
알고리즘 2022. 1. 15. 14:54
백준 5014번 스타트링크 C++

어렵지 않은 bfs 탐색 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int f, s, g, u, d; vector found(1000001, false); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> f >> s >> g >> u >> d; queue q; q.push({ s,0 }); found[s] = true; int ans = -1; bool..
알고리즘 2022. 1. 14. 11:58
백준 13549번 숨바꼭질 3 C++

bfs로 풀었는데, 위치를 찾았는지를 저장하는 found배열을 찾았는지 여부와, 얼마만에 찾았는지 시간의 정보를 함께 저장해서 찾았다고 무조건 건너뛰는 것이 아니라 얼마만에 찾았는지 비교하여서 만약 지금 큐에 넣으려는 경로가 더 빠르다면 이미 찾은 위치라고 하더라도 큐에 넣어주었다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, k; vector found(100001, { false,0 }); int main() { ios_base::sync_with_s..
알고리즘 2022. 1. 13. 12:09
백준 9019번 DSLR C++

a에서 b로 변환되는 경우를 bfs를 통해 탐색하였고, 탐색하는 과정에서 parent벡터를 만들어서 어떤 수에서 어떤 레지스터를 사용해서 값이 나왔는지를 저장하였다. 탐색이 끝났을 때 parent벡터를 이용해 역추적해서 사용된 레지스터들을 알아낼 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int Register(int num, int val) { int ret; int tmp; switch (num) { case 0: ret = (val * 2) % 10..
알고리즘 2022. 1. 12. 12:00
이전 Prev 1 ··· 69 70 71 72 73 74 75 ··· 80 Next 다음