devlog

출처 :https://www.acmicpc.net/problem/2533 풀이 방법우선 완전 탐색을 이용해서 풀이했었다. 하지만 시간 초과가 발생한다. 해당 문제를 dp로 풀이하기 위해선 문제를 나누는 것이 가장 중요하고(순서를 정하기 위해), 이를 위해서 트리를 만들어야 한다.루트노드는 임의로 설정해도 상관이 없다. (첫 번째 노드로 설정) 트리를 만들었으므로 자식과의 관계만 고려하면 된다.현재가 얼리 아답터면 자식은 얼리 아답터, 얼리 아답터가 아닌경우 상관이 없으므로 둘 중 최솟값을 현재 노드의 dp에 더해준다.만약 현재가 얼리 아답터가 아니면 자식은 무조건 얼리 아답터가 되어야 하기 때문에 해당 경우만 더해준다.모든 자식을 돌며 자식의 dfs 값을 더해주면 된다.그리고 마지막 리프 노드를 처리하기..

출처 : https://www.acmicpc.net/problem/11723 풀이 방법배열을 사용하여 풀이하는 방법도 있지만 비트를 사용한다면 더 빠르게 계산할 수 있다.unsigned int s = 0;을 선언하고 각 연산을 s에 해준다. addn 자리에 or 연산을 통해 1비트를 기록한다.s |= (1  removen 자리에 0을 and연산하여 무조건 0으로 만들어 준다.s &= ~(1  check해당 비트에 1과 and연산을 하여 1이 된다면 1 출력 0이면 0을 출력한다.s &  (1  toggle해당 비트자리에 1과 xor연산을 하여 비어 있으면 채워 넣어주고 값이 있다면 제거해 주는 연산을 수행한다.s ^= (1  all21에서 1을 빼주면 비트는 20자리까지 모두 1로 채워진다. 즉 모든 값..

출처 : https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=2&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 풀이 방법구현 문제이기 때문에 구현해야 할 함수들만 잘 정리해서 구현해 주면 된다. 1. rotate_90(int y, int x, int cnt):  • 특정 좌표 (y, x)를 중심으로 시계 방향으로 cnt만큼 90도 회전시킨다. • 회전할 3x3 영역의 좌표 값을 미리 rotate..

출처 : https://www.acmicpc.net/problem/21608풀이 방법호흡이 길 뿐 어려운 문제는 아니다 순서대로 하나씩 배열한 후 점수를 구하면 된다.다음 좌석을 구하기 위해 선호하는 학생 수 , 빈자리 수, y가 작은, x가 작은으로 정렬을 하기 위해 모든 자리를 돌며 우선순위 큐를 사용해서 다음 자리를 선택했다. 주의 점기본적인 우선순위 큐는 MAX Heap이다bool operator 위 함수는 작은 경우 true를 리턴해야 하므로 주의해야 한다. 일반적인 sort에서 사용하려는 사용자 정의 cmp은 다름점수 계산시 모든 좌석을 배정 다 한 후 해야 한다. 전체 코드#include #include #include #include using namespace std;int N, stud..

출처 :https://www.acmicpc.net/problem/2170풀이 방법라인스와핑 문제로 경우를 나누면 탐색 한 번으로 풀이할 수 있다.먼저 선을 시작 좌표, 마지막 좌표 기준으로 정렬한다.그 후 줄이 끊기는 경우와 연장되는 경우를 나누어 풀이하면 된다.줄이 연장이 되려면 현재 줄의 end보다 다음 줄의 시작 부분의 좌표가 작아야 한다. 그리고 현재 줄의 마지막과 다음 줄의 마지막 중 좌표가 큰 것을 end 좌표로 설정한다. 끊기는 경우는 다음 시작 좌표가 현재 end좌표보가 큰 경우로 이때 끊긴 줄의 길이를 더해주고 start, end값을 초기화해준다. 루프를 다 돈 후 마지막 줄에 대해 더해주는 과정이 필요하다. 입력이 많은 문제이므로 아래 코드를 추가하지 않으면 시간초과가 발생한다.  ..

출처 : https://www.acmicpc.net/problem/17144 풀이 방법문제의 핵심미세 먼지는 동시에 전파된다.임시 배열을 사용해서 한 번에 업데이트하면 된다.임시 배열을 로컬 변수로 선언했다. 로컬 배열은 항상 memset으로 초기화 해야한다.공기 청정기의 미세먼지 밀어내기 구현코너 부분에서 간단하게 구현하기 위해 밀어내기를 구현하는 순서가 중요하다.윗부분 같은 경우 왼쪽, 밑, 오른쪽, 위 쪽 순서로 밀어낸다면 코너 부분에 크게 신경 쓰지 않아도 된다.공기 청정기 위 아래 구하기두 입력을 받고 정렬을 통해 위 아래 구분이 가능하다.#include #include #include #include using namespace std;int R, C, T;int room[51][51];vec..

출처 :https://www.acmicpc.net/problem/1744풀이 방법그리디 문제로 엣지 케이스를 생각하는 것이 쉽진 않았다.아래 규칙만 잘 지켜 준다면 해결 가능하다.1. 양수면 무조건 큰 수 끼리 곱하기2. 만약 수가 1이면 곱하지 않고 더하기3. 음수 끼리 곱하면 양수가 되므로 작은 수끼리 곱하기4. 양수 또는 음수가 홀수개가 존재하면 마지막 수는 그냥 더하기 문제의 핵심 포인트 : 수를 잘 나누어서 저장한다 (양수, 0 이하 따라)수를 나누어 저장해 계산을 구현하기 쉽게 한다. #include #include #include using namespace std;int N ,ans = 0;vector p, n; bool cmp1(int a, int b) { return a > b;..

출처 : https://www.acmicpc.net/problem/14890풀이 방법길이가 같을 땐 count를 올리다가 높이 차이가 정확하게 1 정도만 난다면 경사로를 추가해서 이동하는 문제이다먼저 새로와 가로를 나누어 2번 for문을 반복했다.또한 cnt변수를 두어 현재까지의 연속된 길이를 저장하고, 높이가 높아졌을 때 L보다 크면 cnt를 1로 초기화했다. 또한 높이가 낮아졌을 때는 cnt를 -L+1을 하는 과정을 두어 이후에 같은 길이가 L개의 같은 길이가 나오게 된다면 가능한 경우로 설정했다. 만약 그전에 높이가 다르게 된다면 플레그 변수를 false로 설정했다.  #include #include using namespace std;int N, L;int board[101][101];int an..

출처 : https://www.acmicpc.net/problem/15486 풀이 방법일반적인 dp 알고리즘인데 여기서 고려해야 할 부분은 경계 값의 처리와, 일을 건너뛰는 경우 최댓값으로 갱신해야 한다는 것이다. dp[i]를 i일 이전까지의 최대로 벌 수 있는 돈이라고 하고 work[i][0], work[i][1]을 각각 소요 시간과, 버는 돈이라고 했을 때점화식을 dp[i + work[i][0]] = max(dp[i], dp[i + work[i][0]])로만 설정한다면 아래와 같은 문제가 발생한다.1~3까지 50만 원  5~6까지 20만 원을 벌 수 있을 때 5일에 일을 시작할 때도 50만 원이 최대였다면 50만 원으로 시작해야 하는데, 0원으로 시작한다는 것이다. 그러므로 4일에서 5일에 시작하더라..

출처 : https://www.acmicpc.net/problem/16562 풀이 방법간단한 bfs문제이다.친구의 친구도 친구, 친구의 친구의 친구도 친구 이므로 bfs를 통해 친구 그룹을 만든 후 그 친구들 중 친구비가 가장 작은 값을 구해서 더해주면 된다.#include #include #include #include #include using namespace std;int N, M, K;vector money;vector > f;int visited[10001];int bfs(int idx) { int min_money = money[idx]; // 현재 친구 그룹에서 가장 작은 값 queue q; q.push(idx); visited[idx] = 1; while(!q...