개발

A : Computer Game (0:19) (0,0) 위치에서 (1,n) 까지 갈 수 있는지 확인하는 문제이다. 오랜만에 알고리즘 문제를 풀어서 Virtual participation(이하 VP) 당시 얼탔다. 그냥 느낌대로 풀었는데 시간도 20분 가까이 걸렸고, 코드도 안 예쁘다. 어차피 오른쪽 아래로만 가니 8방위가 아니라 오른쪽 위, 오른쪽 아래, 아래, 이렇게 3 방향만 고려하면 됐다. 다음에는 예쁘게 풀어보자. #include #include #include #include using namespace std; vector field; vector visited; int dx[8] = { 0,1,1,1,0,-1,-1,-1 }; int dy[8] = { 1,1,0,-1,-1,-1,0,1 }; 0..

A : Regular Bracket Sequences (0:20) n 을 입력 받았을 때, n 쌍의 괄호가 만들어지는 경우 중 n 개를 출력하는 문제이다. 백트래킹 개념으로 풀려고 접근을 했는데 흐름이 머리 속에서 바로 그려지지 않아서 여러 방법으로 시도하다가 시간이 오래 걸린 문제이다. #include #include using namespace std; int ans; void bracket(vector &s, int l, int r) { if (ans == 0) return; if (l == 0 && r == 0) { for (int i = 0; i t; while (t--) { cin >> n; ans = n; bracket(s, n, n); } } B ..

문제 접근 지민이가 가지고 있는 케이크 N조각 을 최대 M번 자를 때, 무게가 가장 많이 나가는 조각과 적게 나가는 조각의 차이를 최소화하여 그 값을 출력하는 문제이다. 이 값을 최소화하려면 잘라야하는 조각은 무게가 가장 많이 나가는 조각이다. 적게 나가는 조각을 잘라봤다 차이가 더 커질 뿐이다. 구현할 때는 deque 와 upper_bound 를 사용하여 케이크의 목록을 만들고 업데이트했다. 처음에는 가장 무거운 조각을 자를 때는 가장 가벼운 조각의 무게에 맞춰 자르려고 노력했는데 그 이유는 가장 무거운 조각과 가벼운 조각의 차이가 바로 모든 값의 범위이기 때문이다. 가장 가벼운 조각에 맞춰 자르면 범위는 필연적으로 줄어들 수 밖에 없다. 하지만 나누었을 때 어쩔 수 없이 범위가 늘어나는 경우, 반으로..

문제 접근 세준이가 가지고 있는 N 자리 수에서 주어진 수를 하나씩 지워 만들 수 있는 가장 큰 수를 구하는 문제이다. 고민해보다가 앞자리부터 크게 만들면 가장 큰 수가 될 것 같았다. 따라서 0부터 9 까지의 수가 처음으로 나올 때까지 나열되어있는 다른 숫자 개수를 각각 temp 배열에 저장한 뒤, 9부터 0까지의 수를 전부 확인해 temp 배열 값을 다 지울 수 있다면 해당 수는 남도록 구현했다. 문제 접근 // 1:45 ~ 3:10 // 17:35 ~ 20:10 // 01:00 ~ 02:00 #include #include #include // 테스트케이스 확인용 파일 입출력 헤더 #include using namespace std; // erase_cnt : 지워야하는 수의 개수 // cur : ..

문제 접근 거의 최단 경로를 구해야한다. 이 문제에서 '거의 최단 경로'란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 따라서 다익스트라 알고리즘을 통해 최단 경로에 포함되는 도로를 찾은 후, 해당 도로를 배제한 뒤 다시 다익스트라 알고리즘을 통해 거의 최단 경로를 찾도록 구현했다. 문제 코드 #include #include #include using namespace std; int N, M; int S, D; int U, V, P; int ans; // 인접 노드들의 정보가 담겨있는 vector 이다. vector adj; // 최단 경로의 포함되는 장소의 부모를 저장하는 vector 이다. vector parent; // 최단 경로를 배제할 때 중복해서 처리하지 않..

문제 접근 3x3x3 큐브를 여러 번 돌린 후 가장 윗 면의 색상을 구하는 문제이다. 각 면에 0 부터 5 까지의 번호를 부여한 후, 그에 따라 3x3 구성에서 어느 부분이 돌아가는지, 어떤 순서로 돌아가는지 저장하는 배열을 만들어 구현했다. 또한 육면체의 전개도를 기준으로 상하좌우를 고정해서 회전하면서 바뀔 때 혼동되지 않도록 했다. 문제 코드 #include using namespace std; // 각 면의 현재 색을 저장하는 배열이다. char side[6][3][3]; // 번호에 따른 색상과 위치를 나타내는 배열이다. char color[6] = { 'r', 'w', 'b', 'o', 'y', 'g' }; char com[6] = { 'F', 'U', 'R', 'B', 'D', 'L' }; /..

17142 번 : 연구소 3 백트래킹으로 활성화 할 바이러스의 조합을 만들었고, 이를 BFS 로 최소 시간을 구하는 방법으로 풀이했다. #include #include #include #include using namespace std; int N, M, cnt_0, ans; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { -1, 0, 1, 0 }; vector map; vector visited; vector virus, active; void bfs() { int y, x, time; queue q; int cnt_copy = cnt_0; if (cnt_0 == 0) { ans = 0; return; } visited.assign(N + 2, vector(N + 2, fa..

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 여도, 한 변이 비어있을 수 있어 고민했었는데, 문제를 다시 읽어보니 네 꼭짓저머이 드..