짱아의 개발 기록장

역대급 구현문제이다.....ㅎㅎ... 생각보다 구현하는 데에 오래거렸다...(물론 중간에 어이없이 빼먹은 부분 때문에 더더) *중요한 포인트* 1. 행이나 열이 타일로 가득찬 경우, 지우고 내리고 지우고 내리는 것이 아니라 한 꺼번에 지우고 내리면 된다. 2. 블록은 떨어질 때 블록 단위로! 떨어진다. (마구잡이로 떨어지는 것이 아니라) 2번 포인트를 위해서 글쓴이는 green, blue 2차원 배열에 블록을 저장할 때에 블록의 번호를 저장했다. 그리고 인접한 곳에 같은 번호를 가진 칸이 있다면 하나의 블록으로 간주했다. 위에 2가지 포인트만 잡고 코드를 설계하고 구현하면 될 것 같다. 구현은 끈기를 가지고 푼다면 풀 수 있는 문제이다. 코드 첨부(매우 김 주의) 1 2 3 4 5 6 7 8 9 10 1..

정말 말 그대로 문제에서 봄, 여름, 가을, 겨울에 해당하는 조건들을 다 구현해주면 되는 구현문제이다. 다만, 어떠한 자료구조에 나무의 상태, 양분의 상태를 저장할지 코드를 설계하는 초반 작업이 중요하다고 생각된다. 글쓴이는 vector tree[11][11]; 에 나무의 상태를 저장했다. (한 칸에도 여러 그루의 나무가 있을 수 있기 때문) 그리고 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 ..

비교적? 간단한 bfs문제이다. 지뢰가 없는 곳을 방문하고 그와 인접한 8곳 중에서도 지뢰가 없다면 bfs로 방문처리를 한다. 그리고 최종적으로 방문하지 못한 곳 중 지뢰가 없는 곳을 세어주면 값을 구할 수 있다. 코드 첨부 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 83 84 85 86 87 88 89 90 // 1868. 파핑..

아이디어가 생각나지 않아 다른 분의 아이디어를 참고하여 유니온파인드로 구현했다. 핵심 아이디어는 3번 게이트로 들어오게 되면, 3->2를 가리키도록 union해주어야 한다. 따라서, 다시 한 번 3번 게이트로 다른 비행기가 들어오면 바로 3의 Parent인 2에 넣어줄 수 있게 된다. 만약 Parent값이 게이트 범위 안에 있지 않다면, 바로 공항은 폐쇄된다. 코드 첨부 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 // 공항 #include #include using namespace std; int g, p, n; vector airp..

각 정점마다의 최단 경로를 저장하기 위한 heap벡터(내림차순), 다익스트라 알고리즘 사용을 위한 pq벡터(오름차순)를 사용하여 전체적인 로직을 구현했다. 핵심은 heap벡터에 k개의 원소가 있지 않으면 계속 원소를 넣어주고 k개의 원소가 이미 차있는 상태라면, heap[i].top()과 cost값을 비교해주어 top의 값이 더 크다면 pop해주고 cost값을 새롭게 넣어주면 된다. 설명의 이해를 위해 간단히 필기해둔 것을 아래에 첨부했다. *이때, 빼먹기 쉬운 부분* 1->1로 가는 첫 번째 최단 경로는 무조건 0이다! 따라서, dijkstra()함수 초반에 heap[1].push(0);을 해주었다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

모든 점을 연결하는 최소 비용을 구하는 문제이다. 따라서 MST알고리즘을 사용해야한다. 글쓴이는 그 중 kruskal 알고리즘을 사용하여 문제를 풀었다. 벡터에 {두 점을 연결하는 비용, {점1, 점2}}의 형태로 정보를 저장해주었다. 그리고 벡터를 비용순으로 sort한다. 모든 점을 하나씩 union하면서 최소 비용을 찾는다. 코드 첨부 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 // 별자리 만들기(MST-..

bfs와 kruskal 알고리즘을 사용해야 하는 매우 괜찮은 문제이다. 총 3단계로 생각해볼 수 있다. 1) bfs로 이동할 수 있는 영역을 숫자로 check이차원 배열에 표시해두었다. 2) 그 후, 각 영역간에 필요한 사다리의 비용을 {사다리 비용, {영역1, 영역2}}의 형태로 vector에 저장했다. 3) MST를 구현하기 위해 kruskal을 사용하여 각 영역을 최소 비용으로 연결해주었다. MST로 구현해야 한다는 것을 쉽게 생각해내지 못해서 좀 헤맸던 것 같다. (어떻게 최소 비용으로 연결해주지..? 이 생각만 30분 넘게 했던 것 같...다....ㅎ) 코드 첨부 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..

약간 생각의 전환이 필요한 이분탐색 문제였다. mid값을 '돌사이의 최솟값'이라고 잠정적으로 잡아놓은 후에, mid값보다 (현재 돌 위치-이전 돌 위치)값이 더 작으면, 돌을 없애고 더 크면, 돌을 살려둔다. 그 후, 없앤 돌의 수가 n보다 작거나 같다면 mid(돌 사이의 최솟값)이 충분히 작다는 의미니 low = mid+1을 해주고 n보다 크다면 mid값이 너무 크다는 의미니 high = mid-1로 해준다. .....이런식으로 이분탐색을 진행하면 된다. 이 문제도 그림으로 설명하면 좋을 것 같아서 추후 첨부해보겠다. 코드 첨부 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..