개발/알고리즘

15685번 : 드래곤 커브 K 가 1 초과이니 경우, K 세대 드래곤 커브는 K-1 세대 드래곤 커브를 끝점을 기준으로 -90도 회전시킨 다음, 그것을 끝 점에 붙인 것이라고 한다. d 가 0~3 일 때, 각각 오른쪽, 위, 왼쪽, 아래인데 이것들을 90도 회전시키면 걸 d' 이라고 한다면 d' 은 위, 왼쪽, 아래, 오른쪽으로 d 를 기준으로 1, 2, 3, 0 이다. 따라서 -90도 회전시킨 d = (d' + 1) % 4 라는 걸 알 수 있다. prev_move 벡터에 이전 세대에 움직였던 방향들을 넣어두고, 역순으로 -90도 회전해서 적용하면 다음 세대 드래곤 커브가 된다. 정사각형의 경우 네 꼭짓점이 true 여도, 한 변이 비어있을 수 있어 고민했었는데, 문제를 다시 읽어보니 네 꼭짓저머이 드..

5430번 : AC 맨 앞자리를 간단하게 버리기 위해 deque 를 사용하여 해결했다. 1차 시도 때는 말 그대로 구현했고, 시간 초과가 나와서 그 다음으로는 R 이 연속으로 짝수 번 있으면 무시하고 넘어가도록 처리했다. 하지만 여전히 시간 초과가 나와서 고민해보니 R 명령의 경우 D 만 잘 처리해주면 마지막에 처리해도 상관 없는 것 같아서 Reverse 여부를 확인하는 isReverse 변수를 만들어서 처리했다. #include #include #include #include using namespace std; int T, n; bool isError, isReverse; string p, input, trans; deque seq; int main(void) { ios_base::sync_with_..

5567 번 : 결혼식 Queue 에 { 노드 번호, 1 번 노드와의 거리 } 를 넣어서 BFS 로 탐색하도록 구현했다. #include #include #include using namespace std; int n, m, a, b; vector relation; vector visited; int main(void) { int ans = 0; queue q; cin >> n >> m; relation.assign(n + 1, vector()); visited.assign(n + 1, false); for (int i = 0; i > a >> b; relation[a].push_back(b); relation[b].push_back(a); } q.push({ 1, 0 })..

16234 번 : 인구 이동 BFS 로 연합의 인구 수의 합을 구한 후, 칸의 개수로 나누어 평균 인구 수를 구했다. BFS 로 연결된 칸을 확인하며 A_union 에 위치를 저장한 뒤 평균 인구 수를 구한 후 A_union 내의 모든 값을 평균 인구 수로 대체했다. 이렇게 모든 칸이 조건을 충족하지 않을 때까지 반복하여 답을 구했다. #include #include #include using namespace std; int N, L, R; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; vector A; vector visited; queue A_union; int bfs(int x, int y) { int cnt = 1, total = 0; q..

코드 #include using namespace std; // list 라고 이름 붙인 변수에 주소값이 들어있으니 * 로 값을 가져온다. void merge(int* list, int left, int mid, int right) { int sorted[8]; int i = left; // 두 번째 배열의 시작점 int j = mid+1; int k = left; while(i

// 0, 1 이기에 먼저 찾아낸 게 무조건 빠름. #include #include #include using namespace std; int N, K; vector dist(100001, 100001); priority_queue q; void approach(int pos) { dist[pos] = 0; q.push({0, pos}); while(!q.empty()) { int nextTime; int here = q.top().second; int weight = -q.top().first; q.pop(); if(here == K) break; if(dist[here] 0) { nextTime = weight + 1; if(nextTime < ..

문제 접근 처음에는 무게 기준 내림차순으로 정렬해서 탐욕법으로 풀 수 있을거라고 생각했는데 예외가 있어서 안 됐다. 알고리즘 분류를 확인해보니까 1. 큰 배열은 함수 안에서 호출하면 segmentation fault 난다. 문제 코드 #include #include using namespace std; int cache[101][100001]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int W[101], V[101]; int N, K; fill(&cache[0][0], &cache[100][100000], 0); cin>>N>>K; for(int i=1; i>W[i]>>V[i]; for(int i=1; i

문제 접근 'Queen을 한 줄에 하나밖에 배치하지 못한다.'는 점을 이용하여 풀었다. 우선 NxN 크기의 Board 배열을 만들어 놓고, 모든 열에 대해 Queen을 놓을 수 있는 위치에 하나를 배치하고, 그다음 줄을 확인한다. line 이 N까지 가면 N 개를 배치한 것이므로 1을 반환하고, line-1 번째 줄로 돌아가도록 구현했다. 처음에는 board 에 Queen을 배치할 때 안 되는 부분을 1 증가시키는 방식으로 풀이했는데, 풀고 나니 더 깔끔한 풀이들이 보였다. 첫 번째는 Queen 이 배치되면 대각선 2개, 세로줄, 가로줄 전체가 안 되는 것이므로 크기 N*2 배열을 2개 만들어 대각선까지 한 번에 처리하는 것이고, 두 번째는 이전 줄에서 Queen 이 놓인 위치를 통해 해당 위치가 안 되..