charminseok

세그먼트 트리 활용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 def seg_tree(nums, oper, b, c, tree): def init(start, end, node, a, tree): if start == end: tree[node] = a[start] return tree[node] mid = (start+end)//2 tree[node] = init(start, mid, node*2, a, tree) + init(mid + 1, end, node * 2 + 1, a, tree)..

색종이를 붙이는 최소값을 찾는 문제다. 백트래킹과 DFS를 사용하면 생각보다 간단히 풀 수 있다. 가장 큰 색종이부터 작은 색종이를 찾으면서 푼다(5 4 3 2 1) 크기 5부터 시작해서 DFS로 들어가서 그 크기에 맞는지 확인을 하고 붙일 수 없다면 함수를 종료한다. 만약 색종이를 붙일 수 있다면 값을 0으로 바꾸고, 1인 위치를 찾는다. map에 1이 없다면 ans와 현재 붙인 색종이 개수를 비교해 작은 값을 ans에 저장한다. 최소값을 저장 후 다음에 탐색할때, 최소값보다 붙인 색종이가 많아진다면 바로 함수를 종료한다.(백트래킹) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

bfs를 사용해 주변 배열의 크기를 비교해서 uni벡터에 연합의 번호를 저장하고 이때 con벡터에 그 나라의 인구수와 위치를 저장하였다. 그리고 연합에 나라의 수가 1이 아니라면 문제에 나와있는대로 인구를 이동했다. while문으로 인구가 이동하지 않을때 까지 반복해서 답을 구하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82..

그냥 단순히 시뮬레이션 문젠데 약간 복잡하다. 세포의 위치, 생명력, 상태, 시간을 구조체로 만들고, vector map으로 dfs,bfs에서 visited배열과 같은 역할을 해주었다. 세포의 시간이 생명력과 같아지면 활성 상태로 만들어주고, 생명력의 두배가 되면 죽은 상태로 바꿔주었다. 그리고 새로운 cell형 벡터를 두개 만들어 newC에선 새로 번식할 수 있는 모든 세포를 넣어주고, 생명력 내림차순으로 정렬해 생명력이 큰 세포가 번식할 수 있도록 해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49..

가장 위에 있는 벽돌에 구슬이 떨어지면서 벽돌의 숫자만큼 사방으로 깨진다. dfs를 이용한 백트레킹으로 큰 틀을 잡았고, 벽돌을 깨는 함수와 깬 이후 벽돌들을 맨 밑으로 이동시키는 함수를 작성하였다. 벽돌을 깰때, 벽돌이 0이 아니면 재귀함수를 통해 모든 벽돌을 깨고, 벽돌을 이동할 때는 큐를 사용해 배열의 맨 밑으로 쌓아주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74..

맨 뒤 글자가 맨 앞으로 이동하면서 키를 만든다. 여기서 n/4개씩 끊어서 set에 넣어줬다.(중복을 없애기 위해서) 그리고 set은 오름차순으로 들어가게 set strtmp; 맨 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include #include #include #include #include using namespace std; int n, k; set strtmp; vector ans; void rotate(string &str) { strin..

블록을 4방향으로 움직이는데 최대 5번 움직였을때 최댓값을 구하는 문제였다. DFS로 몇번 반복할 것인지 설정하고, 방향에 따라 숫자를 합해줬다. 처음에 숫자를 합칠때, 합쳐진것에서 또 합쳐질 수 있도록해서 틀렸는데, 고치니까 바로 맞았다.... 2 2 4 2가 왼쪽으로 합쳐진다고하면 4 4 2 가 되야되는데 8 2가 되버리게 한게 잘못이였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 ..

아기상어가 물고기를 먹으면서 움직인다. 1. 아기상어가 움직일 수 있는 칸으로 이동하고(BFS사용) 먹을 수 있는 물고기라면 tmp 벡터에 저장한다. 2. tmp 벡터를 이동시간, 위치에 따라 정렬한다. 3. tmp[0]에 있는 물고기를 먹고 아기상어의 위치를 옮긴다. 아기 상어의 정보를 따로 저장하였고, 먹은 물고기의 수가 크기와 같아지면 size++를 해주었다. bfs()의 반환값이 0(먹을 물고기가 없을때)이되면 while문을 종료하고 정답을 출력했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5..