Algorithm283 [BOJ]16922번: 로마 숫자 만들기 문제: https://www.acmicpc.net/problem/16922 BFS 문제입니다. 매 깊이 마다 1,5,10,50을 더해봐서 X개의 숫자의 합으로 Y를 만든 적이 있는지 계속 저장하면서 N개를 모두 합쳤을 때의 값을 set에 저장해주었습니다. 상태를 탐색하는 방법은 DFS도 가능하겠지만 아마 재구 깊이를 20까지 탐색 하면 터지지 않을까 싶네요. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16922.cc 2020. 5. 20. [BOJ]18290번: NM과 K(1) 문제: https://www.acmicpc.net/problem/18290 완전 탐색문제입니다. 맨 처음에 문제를 잘못 이해해서 헤맸었네요. 주어진 NM 칸에 대해 최대 4칸을 뽑고 그 칸이 인접해있는지 확인하면 되는 문제입니다. 두 가지만 처리하면 해결할 수 있는 문제입니다. 1. 100 콤비네이션 K만큼의 경우의 수를 생성한다. (NM의 상한이 100이니, 최대 100 콤비네이션4 만큼 경우의 수가 뽑히겠네요.) 2. 뽑은 K칸들이 인접한지 확인한다. 3. 인접하지 않다면 SUM을 구해 최댓값을 갱신한다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ18290.cc 2020. 5. 20. [BOJ]16957번: 체스판 위의 공 문제: https://www.acmicpc.net/problem/16957 유니온 파인드 문제입니다. BFS로 문제를 접근한다면 O(R^2*C^2) 으로 시간초과가 납니다. 주변에 인접한 칸 중에 가장 작은 칸 A를 루트라고 생각해봅시다. 그러면 A칸과 인접한 모든 칸은 A를 부모로 가지고 있습니다 즉, parent[SUM_NODE] = A 이런식입니다. 이런식으로 우선 R*C만큼 돌면서 각 노드가 부모로 가지는 노드가 무엇인지 find연산을 해줍니다. 그러면 자기 자신이 가장 작은 칸은 parent[NODE] = NODE가 될것이고, 자기보다 작은 칸이 존재한다면 parent[NODE] = MORE_SMALL_NODE가 될 것입니다. 이 다음엔 진짜 루트 노드를 구하러 갑니다. 무슨 말이냐면 누군가에겐.. 2020. 5. 19. [BOJ]17837번: 새로운 게임2 문제: https://www.acmicpc.net/problem/17837 시뮬레이션 문제입니다. 이 문제에서 순서를 뒤집고 관리하기 편한 자료구조는 스택입니다. 2차원 벡터의 각 자료형을 스택으로 하여 [y][x] 칸에 존재하는 말의 상태를 관리해주었습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17837.cc 2020. 5. 18. 이전 1 ··· 57 58 59 60 61 62 63 ··· 71 다음
