초이로그

너무 복잡한 구현이었던 벽돌깨기!!! 스터디 문제였는데 당시에는 못풀고 드디어 풀었다!!! 1. makeSet(): 구슬을 떨어뜨리는 경우(N)만큼 선택할 수 있는 열의 경우의 수를 생성한다 (예제 1처럼 N=3, W=10인 경우, 10*10*10의 경우의 수를 생성) 1-1. copyArray(): 경우의 수마다 구슬을 쏴 테스트 하기 위해 주어진 벽돌 정보 배열을 복사한다 1-2. 생성된 경우의 수(N)대로 구슬을 쏜다. 1-2-1. findH(): 선택된 열의 가장 최상단 벽돌의 가로측 위치를 구한다.(즉 좌표 정보 획득!) 만약 해당 열에 벽돌이 없으면 continue; 1-2-2. shootMarvel(): 해당 좌표로 구슬을 쏜다. bfs를 이용하여 벽돌정보만큼 상하좌우로 터뜨린다. 1-2-2..

이전에 이미 내리막길(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..