반응형 코딩46 백준 13460번 - 구슬 탈출 2 (C++) 문제 해결 방법 DFS를 사용해서 해결했다... (덕분에 해결 시간은 매우 높다) 실행 방식은 그냥 평범한 DFS... 라서 더 설명할 것이 없다. 구슬의 이동은 따로 구슬의 좌표들을 미리 저장해 구슬을 매번 찾는 손해는 없도록 하였으며, 구현은 그냥 반복을 통하여 이동/탐색하며 빈칸이 아닌 공간을 찾고, 막혀있는 공간을 만난다면 그 바로 이전 칸으로 이동하게끔 하였다. 예외적으로 구멍인 O는 만나면 이동이 아니라 구슬이 삭제되게끔 하였다. 아쉬웠던 점 보자마자 감이 와서 바로 푼 문제인데, BFS로 풀어야 하는데 아무 생각없이 브루트포스(전체탐색)이니 간단한 DFS로 해야겠다~ 라는 안일한 생각을 했다. 사실 최단거리 구하는거면 당연히 BFS를 생각했어야 했는데 수련이 부족한듯 ㅜㅠㅠ 코드 1 2 3 .. 2021. 10. 26. 백준 2252번 - 줄 세우기 (C++) 문제 해결 방법 위상 정렬을 사용하는 대표적인 문제이다. 정점기준 보내주는 간선들의 숫자, 받은 간선의 횟수를 저장하는 배열을 만들어서 이를 기반으로 큐를 사용하여 위상정렬을 했다. 아쉬웠던 점 초기에 큐에 넣는 과정을 입력구간에서 어떻게 잘 해결할 수 있을 것 같기도 한데, 결국 받은 간선을 저장한 배열을 순회하며 그 숫자가 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 #include #include #include using namespace std; int m.. 2021. 10. 8. 백준 9661번 - 돌 게임 7 (C++) 문제 해결 방법 이 게임은 다음사람이 4내면 1내고 / 1내면 4내서 0을 만들기때문에 남은 돌의 갯수를 5개 그리고 같은 이치로 남은 돌 갯수를 2개 만든 사람이 이긴다. 때문에 그냥 n%5해서 0이나 2가 남으면 후공이 이기고, 이 외의 경우에는 선공이 이긴다. 아쉬웠던 점 이게 골드2인게 아쉽다. 너무 날먹문제야... 코드 1 2 3 4 5 6 7 8 9 10 11 12 #include using namespace std; int main() { long long int n; cin >> n; n = n%5; if (n == 0 || n == 2) cout 2021. 10. 2. 백준 11438번 - LCA2 (C++) 문제 해결 방법 기존 LCA와 똑같이 풀이하되, 기존에는 공통 조상을 찾기 위하여 한칸한칸 전진하며 찾았지만, 데이터 범위가 늘어나 한칸한칸 전진하며 탐색하면 시간 초과가 나온다. 때문에 각 숫자별로 (2^0, 2^1, 2^2... 2^16)만큼 전진한 부모를 저장하여 2의 제곱수만큼 전진하며 탐색한다. 'Parents[i][j] = 2^j만큼 떨어진 i의 부모'이다. 2의 제곱수만큼 전진한 부모를 아는 방법은, "Parents[i][j + 1] = Parents[Parents[i][j]][j]"를 해주면 된다. 풀이를 하자면,나의 2^2+1(8칸)만큼 떨어진 부모는 나의 2^2(4칸)만큼 떨어진 부모의 2^2(4칸)만큼 떨어진 부모다. 즉 8칸=4칸+4칸, 2^3=2^2+2^2인것과 같은 원리다. (1.. 2021. 10. 2. 이전 1 2 3 4 5 6 7 ··· 12 다음 반응형
