> >
본문 바로가기

Algorithm

 (31)
[BOJ] 14267번 회사 문화 1 Sol1) 트리 DP상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 그래프로 간선을 연결해주면 간단하게 트리 DP를 이용해먹을 수 있겠다고 생각했다. for (int i = 0; i DFS를 돌기 전에 반영을 해줘야 계속해서 자식 노드에 전달할 수 있다. 소스 코드#include #define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)using namespace std;#define ll long longconst int MAXN = 100005;ll dp[MAXN], arr[MAXN];vector trees[MAXN];bool visited[MAXN];void dfs(int cur){ ..
[BOJ] 1253번 좋다 Sol1) 투 포인터배열을 정렬하고 투 포인터를 돌리면서 해당하는 값이 나올 수 있는지 확인합니다. 주의할 것은 s와 e로 만들어지는 수가 s와 e랑은 다른 인덱스를 가져야 합니다. 소스 코드#include #define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)using namespace std;const int MAXN = 2005;int arr[MAXN];int main(){ FASTIO; int n, res = 0; cin >> n; for (int i = 0; i > arr[i]; sort(arr, arr + n); for (int i = 0; i arr[i]) e--; ..
[BOJ] 1337번 올바른 배열 Sol1) 자료구조50개의 원소를 set에 넣고 원소 it에 대하여 [it + 1, it + 4]의 개수가 몇 개인지 확인합니다. 소스 코드#include #define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)using namespace std;int main(){ FASTIO; int n, num, res = 4; set s; cin >> n; for (int i = 0; i > num; s.insert(num); } for (auto it : s){ int tmp = 0; for (int i = it + 1; i
[BOJ] 2213번 트리의 독립집합 Sol1) Tree DP트리의 독립집합 크기1. dp[cur][1] = sum(dp[next][0]) + arr[cur]-> 1은 집합에 선택되었음을 표현 합니다. next는 모두 선택되지 않아야 합니다.2. dp[cur][0] = sum(max(dp[next][0], dp[next][1]))-> cur이 선택되지 않으면 next는 선택하거나 안하거나 상관없습니다.  독립집합의 정점vector res[MAXN][2]를 선언해서 next의 정점들을 cur로 올려줍니다. cur이 선택되지 않는 독립집합의 경우 두 가지로 나눠서 next가 선택되었을 때랑 안되었을 때 구분합니다. 소스 코드#include #define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.ti..
[BOJ] 2629번 양팔저울 Sol1) DP추를 쓸지 안쓸지로 생각하면 2^30이기 때문에 백트래킹으로는 안 풀린다는 것이 느껴집니다. N이 애매한 수치인데 배낭문제 아닐까 생각하게 됩니다. 추가 1g, 4g이 있다고 가정해봅시다.1g만 있을 때는 1만 체크할 수 있습니다.4g이 추가적으로 들어온다면 4-1, 4+1, 4, 1을 체크할 수 있습니다. 1. DP[i][j] = DP[i - 1][j + arr[i])) // j = 1, arr[i] = 42. DP[i][j] = DP[i - 1][abs(j - arr[i])] // j = 1, arr[i] = 4 -> 4  - 13. DP[i][j] = DP[i - 1][j] // i - 1번째에서 성공한 모든 경우는 i번째 추를 안쓰면 되기 때문에 다 됩니다.4. DP[i][arr[i..
[BOJ] 1477번 휴게소 세우기 문제 풀이얼마 전까지 이분 탐색 문제에서 조건을 어떻게 써야하는지 어떤 것을 출력해야 하는지 헷갈릴 때가 있었습니다. 보통 처음 배우는 이분 탐색의 식은 특정 조건을 만족할 때 while문을 탈출하는 식이라서 더 그랬던 것 같습니다. 동기들과 알고리즘 스터디를 진행하면서 이분 탐색이 좀 명확하게 보이기 시작했고 여러분과 나누고자 합니다. 1. 이분 탐색의 변수를 어떤 것으로 할 것인가?-> 사실 이 질문에서 이분 탐색인지 몰랐던 문제가 갑자기 명확해지는 경우가 많습니다. 이 문제의 경우 고속도로 길이를 이분 탐색의 변수로 둡니다. 보통 문제에서 구하라고 명시되어 있는 것이긴 합니다.2. True -> False 혹은 False -> True-> 이분 탐색이 헷갈려서 구글에 치면 가장 먼저 나오는 백준의 ..
엘리스 코드 챌린지 예선 후기 2주 동안 참여하면서 저의 부족한 실력을 뼈저리게 느꼈습니다. 마지막 문제를 해결하지 못한 것은 아쉽지만 대회를 참가하면서 많이 발전했기에 만족합니다.
[BOJ] 15685번 드래곤 커브 Sol1) 방향을 기준으로 string 만들기#include #define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)using namespace std;int n, x, y, d, g, res;bool visited[105][1005];int dx[] = {1, 0, -1, 0};int dy[] = {0, -1, 0, 1};int main(){ FASTIO; cin >> n; for (int i = 0; i > x >> y >> d >> g; string tmp = to_string(d); for (int j = 0; j  시계 방향으로 90도를 돌린다는 것은 기준점의 관점에서는 반시계..

티스토리툴바