초이로그

애증의 문제다... 문제만 보면 내가 전혀 못풀리 없어 보여서(??) 이 악물고 풀어봤지만 항상 시간 초과가 떴었다. 이 문제에서 시간초과를 줄이기 위해서는 순차탐색을 하며 1. i번째가 사이클인지 판별할때, 발견된 사이클은 다시 방문하지 않는다.(i를 포함하지 않는 사이클이라도) 2. 이미 방문한(하지만 사이클은 아닌) 경우도 방문하지 않는다. 두개로 시간을 줄여나가야하는데 BFS에만 매달렸던 나는 도저히 1번을 구현할 수가 없었다... 결국 bfs코드를 쫙 지워버리고 dfs로 풀었더니 구현과정에서 start와 next를 체크하는게 다소 헷갈렸지만 한번에 맞을 수 있었다.. 빠르게 정답에 맞는 솔루션을 선택하는 연습도 필요한것 같다 https://github.com/SuyeonChoi/Algorithm..

이전에 이미 내리막길(1520)을 풀었더니 쉽게 풀 수 있었다. 시간 초과 방지를 위해서 DFS + DP 로 푸는 문제였다. DFS을 통해 각 위치마다 판다의 최장 수명을 저장한다. 이때 visited 배열(DP배열)을 이용하여 이미 방문한적이 있는 경우, 해당 칸에서의 최장 수명을 반환함으로써 시간을 단축해주었다. github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/Simulation/p1937.java SuyeonChoi/Algorithms Personal Algorithm Study::solving BOJ, Programmers, and SW Expert Academy - SuyeonChoi/Algorithms github.com

작년엔 보고 헉 하고 넘겼던 문제 오늘도 보고 헉 하긴 함;; BFS ver. while (! queue.isEmpty()){ myPoint cur = queue.poll(); if(cur.x == cvs[N][0] && cur.y == cvs[N][1]) { isHappy = true; break; } for(int i = 0; i < N+1; i++){ int dist = calcDist(cur.x, cur.y, cvs[i][0], cvs[i][1]); if(!vis[i] && dist

1. DP 1부터 시작해서 N까지 배열을 채워나갔다. 이전 배열의 값(즉 1만큼 작은 값) + 1로 현재 i번째 값을 채우고 2또는 3으로 나누어 덜어지는 경우 i/2 또는 i/3 인덱스의 값과 비교해서 더 작은 값으로 업데이트했다. 나머지 두개의 경우는 숫자 N부터 시작했다. 2. BFS visited배열과 큐를 사용해서 3으로 나누었을때, 2로 나누었을때, 1을 뺐을때 0보다 크고 가능한 경우를 완전탐색하는 방식으로 해결 3. DFS 큐대신 재귀를 사용하였다. 재귀함수의 매개변수로 깊이를 줘서 가지치기를 해야 시간초과가 나지 않는다. 위에서부터 dfs, bfs, dp로 푼 결과 dp로 풀었을때가 제일 빠르게 나올줄 알았는데 bfs로 푼게 더 빨리 통과되었다.

1차 시도) 혹시 시간초과가 날까봐 한번에 bfs를 처리하려고 욕심을 부렸다. 1. 초기 외부 공기 좌표를 모두 큐에 삽입 2. bfs로 탐색 2-1) 치즈를 만나는 경우 이전 visited[nx][ny]=visited[x][y]+1 처리. 2-2) 구멍을 만나는 경우 새로운 큐(holeQueue)에 구멍 좌표를 넣고 새로운 큐에 대해 bfs 탐색 그런데 아무리 해도 틀렸다라는 답이 나오고 반례 생각하는데에 시간을 너무 많이써서 새로운 방법으로 다시 풀었다. 2차 시도) 1. 좌표가 0이 아닌 값으로 초기의 치즈 갯수 모두 카운트 2. 치즈가 모두 사라질때까지 (0,0)을 큐에 삽입하여 bfs탐색 시간초과가 안나다니 행복하다 github.com/SuyeonChoi/Algorithms/commit/c440..

그래프의 union-find알고리즘을 사용하여 해결하였다. 1. 친구의 수만큼 배열을 만들어 make(int N)함수로 N+1개만큼 parent정보를 담는 배열을 생성한다(처음에 부모는 나 자신) 2. 주어진 친구의 정보에 따라 union을 한다. 이때, 친구비용이 더 작은 친구를 그룹 대표(즉 부모)로 잡는다 3. 마지막에 모든 노드에 대해 findSet함수를 이용하여 최종 부모를 배열에 저장한다 4. HashSet을 사용하여 집합의 갯수만큼 친구를 사귈수 있는 비용을 모두 구하고 내가 가진 돈이랑 비교하면 끝! github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/%EA%B7%B8%EB%9E%98%ED%94%84/p16562.java SuyeonCh..