구름톤챌린지

🧩 문제 16. 연합 > 배운 점 • 그래프 탐색 ⇨ BFS • 인접 행렬 활용 > 필요 변수 및 자료구조 - int[][] graph ⇨ 인접 행렬 - boolean[] visited / int[] visited ⇨ 섬 방문 여부 확인 & 연합 여부 확인 - Queue ⇨ BFS 수행용 > 느낀 점 - 연합 개수 = BFS 수행 횟수 - 나는 boolean[] visited로 풀었는데, int[] visited로 해서 while문 안에 현재 방문한 노드를 연합 번호에 할당하는 코드인 visited[now] = cnt; 를 넣어서 풀 수도 있다! > 헷갈렸던 점 - while문 안에 들어가는 if문에서 간선의 존재 여부를 확인할 때, graph[now][next]와 graph[next][now]로 양방향..

🧩 문제 19. 대체 경로 > 배운 점 • 그래프 탐색 - BFS / DFS (최단 경로니까 BFS 활용) - 최단 경로 찾는 문제 ➡ 방문 배열을 int형 배열로 받고, 큰 수로 초기화 > 느낀 점 방문 배열 visited를 처음에 boolean으로 했었는데, 이러면 결과 배열 int[] result를 따로 만들어야 하고 그렇다... 그래서 방문 배열 visited를 int형으로 만들고, 이걸 최단 거리 저장 배열로 만들고, 배열의 초기값은 큰 값으로 설정하는 것이다. 그리고 bfs에 왜 idx 값을 가져가야 하냐면, "i일 뒤 i번 도시로 이동하면 안 된다"는 조건을 만족시키기 위해 몇 번 도시인지 도시 위치 값을 기억하기 위해서다. 만약 A(현재 위치로 가는 최단 경로 값 + 1) 헷갈렸던 점 • ..

🧩 문제 14. 작은 노드 > 배운 점 • 그래프 탐색 • 인접 리스트 vs 인접 행렬 ◻ 인접 리스트 👍 공간 복잡도 면에서 효율적 (실제 연결된 정점의 정보만 저장하므로) 👎 두 정점을 연결하는 간선이 존재하는지 빠르게 확인은 불가능 ◻ 인접 행렬 👍 어떤 정점끼리 연결되어있는지 빠르게 확인 가능 (시간 복잡도 : O(1)) 👎 - 공간 복잡도가 너무 큼 (∵ 주어지는 정점 개수의 제곱에 비례하는 크기의 배열을 선언해야 하므로) - 인접 정점의 정보를 알기 위해 O(N)의 시간을 투자해야 함 > 느낀 점 DFS나 BFS 활용하면 쉽게 풀리겠지 하고 만만하게(?) 보고 BFS로 풀었는데 BFS문의 반복문 안에 break를 넣지 않아서 자꾸 틀렸었고 이것 떄문에 시간을 많이 잡아먹었다ㅠㅠ > 헷갈렸던 점..

🧩 문제 11. 통증 (2) > 배운 점 • 그리디 알고리즘의 반례를 생각해봤을 때 안 됨 ➡ DP 문제 • 이전에 구했던 답 재활용하는 방식 = 메모이제이션 - 최소 개수 찾는 문제 ➡ 큰 수로 초기화 - 최대 개수 찾는 문제 ➡ 작은 수로 초기화 > 느낀 점 : dp는 역시.... 점화식 찾기가 쉽지 않은 것 같다....ㅋㅋㅋㅋㅠ DP[ i ] : 통증 수치가 i일 때, 통증 수치를 0으로 만들기 위해 필요한 아이템의 최소 개수 - i - A >= 0 이고 MAX_VALUE가 아닌 경우, DP[i] = DP[i - A] + 1 - i - B >= 0 이고 MAX_VALUE가 아닌 경우, DP[i] = DP[i - B] + 1 > 헷갈렸던 점 : 점화식을 찾는 과정이 헷갈렸다..... 1 2 3 4 5..

🧩 문제 9. 폭탄 구현하기 (2) > 배운 점 : 완전탐색 / 시뮬레이션 / 행렬 - 2차원 배열에서의 탐색 > 느낀 점 입력받은 폭탄이 떨어지는 위치를 큐에 추가해서 BFS로 쉽게 풀 수 있겠군 했는데 원래 좌표 값 갱신하는 부분에서 조금 헤매다가 시간을 생각보다 더 지체하게 되었다는 슬픈 이야기..🥺 > 헷갈렸던 점 탐색할 때 본인 원래 위치 좌표는 어떻게 값을 더하면서 갱신할까 고민했었는데 그냥 상하좌우를 선언하는 dx dy 배열에 본인 위치만 추가해주면 되는 것이었다,, (int[] dx : {0,0,0,-1,1} / int[] dy : {0,1,-1,0,0}) 🧩 문제 10. GameJam https://goorm.notion.site/GameJam-Java-896c9778997a47a185f..

🧩 문제 6. 문자열 나누기 > 배운 점 문자열을 분리하는 모든 경우의 수를 조합으로 탐색하는 방법 (완전탐색) - 문자열 길이가 최대 100으로 크기가 작으니까 완전 탐색으로 해결 가능 ( 보통 조합은 재귀 함수로 구함) > 느낀 점 [문제 해결 단계]를 먼저 손으로 꼭 써보고 코드로 작성하자. 1. 가능한 부분 문자열을 찾고, 정렬해 점수판 만듦 2. 완전탐색으로 문자열을 자를 수 있는 모든 경우의 수 찾음 3. 점수판을 이용해 모든 경우의 수 中 최대 점수를 찾음 (코드 참고 : https://goorm.notion.site/Java-8df05c32e4574e0f87c6c0a846a387af) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

🧩 문제 4. 완벽한 햄버거 만들기 > 배운 점 : 정렬을 활용해 주어지는 값들이 올바르게 배치되어 있는지 확인하는 문제 // 리스트에서 최대값과 그 인덱스 찾는 방법 int maxIdx = list.indexOf(Collections.max(list)); // 좌측/우측 리스트 생성 ArrayList left = new ArrayList(list.subList(0, maxIdx)); ArrayList right = new ArrayList(list.subList(maxIdx, N)); > 느낀 점 문제 의도를 제대로 파악하지 않고 문제를 풀었다고 한다... 무작정 일단 최댓값을 찾는 걸 먼저하고,정렬은 하지 않고그걸 기준으로 왼쪽 배열이 오름차순인지, 오른쪽 배열은 내림차순으로 진행하지 확인하는 식으로..

🧩 문제 1. 운동 중독 플레이어 > 배운 점 : 소수점 처리 방식! > 느낀 점 - 계산식은 문제에 나온 공식 그대로 작성하면 되어서 어렵진 않았다. - 그런데 이제 소수점 처리를 제대로 알고 하지 않으면 어디서 왜 틀렸는지 모를 수 있는.. > 헷갈렸던 점 (int)(W * (1 + (double)R / 30) [소수점 처리] : R / 30을 할 때, 현재 R과 30은 정수이며 이들의 나눗셈 결과는 정수다. 하지만 소수 부분까지 정확한 계산을 위해, 적어도 하나의 피연산자를 실수로 변환해야 한다. 따라서 실수 결과를 받기 위해 R에 (double)형 처리했다. 1RM을 출력할 때는 소수점 이하를 버려야 했기 때문에 전체 결과에 대해 (int)형 처리를 했다. 저기서 R에 double형 처리를 안 해..